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].
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
edytujKoł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- ↑ 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.).
- ↑ a b Eric W. Weisstein , Wheel Graph [online], Wolfram MathWorld [dostęp 2024-04-30] (ang.).
- ↑ Eric W. Weisstein , Hamiltonian Cycle [online], Wolfram MathWorld [dostęp 2024-04-30] (ang.).
- ↑ Fred Buckley , Frank Harary , On the euclidean dimension of a wheel, „Graphs and Combinatorics”, 4 (1), 1988, s. 23–30, DOI: 10.1007/BF01864150, ISSN 0911-0119 [dostęp 2024-04-30] (ang.).
- ↑ 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, DOI: 10.1006/jctb.1993.1019, ISSN 0095-8956 [dostęp 2024-04-30] (ang.).
- ↑ Reinhard Diestel , Graph Theory, Berlin: Springer, 2017, s. 301, ISBN 978-3-662-53621-6 (ang.).
Linki zewnętrzne
edytujEric W. Weisstein , Wheel Graph, [w:] MathWorld, Wolfram Research [dostęp 2024-04-30] (ang.).