Koło (teoria grafów)

Ten artykuł dotyczy klasy grafów. Zobacz też: inne znaczenia tego słowa.
Rysunki kół o 4, 5, 6, 7, 8 i 9 wierzchołkach
Przykłady kół

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

Koło o n {\displaystyle n} wierzchołkach jest grafem ostrosłupa o podstawie ( n − 1 ) {\displaystyle (n-1)} -kąta[2].

Graf W n {\displaystyle W_{n}} ma n {\displaystyle n} wierzchołków i 2 ( n − 1 ) {\displaystyle 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 {\displaystyle W_{5}} jest izomorficzne z pełnym grafem trójdzielnym K 1 , 2 , 2 {\displaystyle 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 {\displaystyle W_{n}} zawiera dokładnie n − 1 {\displaystyle n-1} cykli Hamiltona[3].

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

Przypisy

  1. ↑ 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.).
  2. ↑ a b 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.).

Linki zewnętrzne

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