Koło (teoria grafów)

Koło – w teorii grafów, graf powstały z cyklu poprzez dodanie nowego wierzchołka połączonego krawędzią z każdym wierzchołkiem tego cyklu. Koło o wierzchołkach oznacza się symbolem [1].

Rysunki kół o 4, 5, 6, 7, 8 i 9 wierzchołkach
Przykłady kół

Koło o wierzchołkach jest grafem ostrosłupa o podstawie -kąta[2].

Graf ma wierzchołków i krawędzi. Koło o czterech wierzchołkach jest izomorficzne z grafem pełnym o tej samej liczbie wierzchołków. Z kolei jest izomorficzne z pełnym grafem trójdzielnym [2].

Własności

edytuj

Koła o nieparzystej liczbie wierzchołków są 3-chromatyczne, a koła o parzystej liczbie wierzchołków mają liczbę chromatyczną równą 4[1].

Wszystkie koła są planarne. Każde koło jest izomorficzne ze swoim grafem dualnym[1].

Każde koło jest grafem hamiltonowskim. Co więcej, graf   zawiera dokładnie   cykli Hamiltona[3].

Graf   jest jedynym kołem, które można narysować na płaszczyźnie tak, aby każda krawędź była jednostkowej długości. Przy zachowaniu tej reguły, pozostałe koła można narysować w przestrzeni trójwymiarowej[4].

Dla każdego   wszystkie grafy 3-spójne o odpowiednio wielu wierzchołkach zawierają   lub   jako minor[5][6].

Przypisy

edytuj
  1. a b c Robin Wilson, Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, 2012, s. 31, 104, 111, ISBN 978-83-01-15066-2 (pol.).
  2. a b Eric W. Weisstein, Wheel Graph [online], Wolfram MathWorld [dostęp 2024-04-30] (ang.).
  3. Eric W. Weisstein, Hamiltonian Cycle [online], Wolfram MathWorld [dostęp 2024-04-30] (ang.).
  4. Fred Buckley, Frank Harary, On the euclidean dimension of a wheel, „Graphs and Combinatorics”, 4 (1), 1988, s. 23–30, DOI10.1007/BF01864150, ISSN 0911-0119 [dostęp 2024-04-30] (ang.).
  5. B. Oporowski, J. Oxley, R. Thomas, Typical Subgraphs of 3- and 4-Connected Graphs, „Journal of Combinatorial Theory, Series B”, 57 (2), 1993, s. 239–257, DOI10.1006/jctb.1993.1019, ISSN 0095-8956 [dostęp 2024-04-30] (ang.).
  6. Reinhard Diestel, Graph Theory, Berlin: Springer, 2017, s. 301, ISBN 978-3-662-53621-6 (ang.).

Linki zewnętrzne

edytuj

Eric W. Weisstein, Wheel Graph, [w:] MathWorld, Wolfram Research [dostęp 2024-04-30] (ang.).