alt=Rysunki kół o 4, 5, 6, 7, 8 i 9 wierzchołkach|mały|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 wierzchołkach oznacza się symbolem .
Koło o wierzchołkach jest grafem ostrosłupa o podstawie -kąta.
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 .
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.
Wszystkie koła są planarne. Każde koło jest izomorficzne ze swoim grafem dualnym.
Każde koło jest grafem hamiltonowskim. Co więcej, graf zawiera dokładnie cykli Hamiltona.
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.
Dla każdego wszystkie grafy 3-spójne o odpowiednio wielu wierzchołkach zawierają lub jako minor.
Przypisy
Linki zewnętrzne
Kategoria:Klasy grafów