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 $n$ wierzchołkach oznacza się symbolem $W_{n}$ ^[1].

Koło o $n$ wierzchołkach jest grafem ostrosłupa o podstawie $(n-1)$ -kąta^[2].

Graf $W_{n}$ ma $n$ wierzchołków i $2(n-1)$ krawędzi. Koło o czterech wierzchołkach jest izomorficzne z grafem pełnym o tej samej liczbie wierzchołków. Z kolei $W_{5}$ jest izomorficzne z pełnym grafem trójdzielnym $K_{1,2,2}$ ^[2].

Własności

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 $W_{n}$ zawiera dokładnie $n-1$ cykli Hamiltona^[3].

Graf $W_{7}$ 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 $k,$ wszystkie grafy 3-spójne o odpowiednio wielu wierzchołkach zawierają $W_{k}$ lub $K_{3,k}$ jako minor^[5]^[6].

Przypisy

↑ ^a ^b ^c RobinR. Wilson RobinR., Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, 2012, s. 31, 104, 111, ISBN 978-83-01-15066-2 (pol.).
↑ ^a ^b Eric W.E.W. Weisstein Eric W.E.W., Wheel Graph [online], Wolfram MathWorld [dostęp 2024-04-30] (ang.).
↑ Eric W.E.W. Weisstein Eric W.E.W., Hamiltonian Cycle [online], Wolfram MathWorld [dostęp 2024-04-30] (ang.).
↑ FredF. Buckley FredF., FrankF. Harary FrankF., 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.B. Oporowski B.B., J.J. Oxley J.J., R.R. Thomas R.R., 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.).
↑ ReinhardR. Diestel ReinhardR., Graph Theory, Berlin: Springer, 2017, s. 301, ISBN 978-3-662-53621-6 (ang.).

Linki zewnętrzne

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

[:0-1] RobinR. Wilson RobinR., Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, 2012, s. 31, 104, 111, ISBN 978-83-01-15066-2 (pol.).

[:1-2] Eric W.E.W. Weisstein Eric W.E.W., Wheel Graph [online], Wolfram MathWorld [dostęp 2024-04-30] (ang.).

[3] Eric W.E.W. Weisstein Eric W.E.W., Hamiltonian Cycle [online], Wolfram MathWorld [dostęp 2024-04-30] (ang.).

[4] FredF. Buckley FredF., FrankF. Harary FrankF., 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.).

[5] B.B. Oporowski B.B., J.J. Oxley J.J., R.R. Thomas R.R., 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.).

[6] ReinhardR. Diestel ReinhardR., Graph Theory, Berlin: Springer, 2017, s. 301, ISBN 978-3-662-53621-6 (ang.).

[1]

[2]

[3]

[4]

[5]

[6]