Articles

Graf koła

Matematyka dyskretna > Teoria grafów > Grafy proste > Grafy stożkowe >
Matematyka dyskretna > Teoria grafów > Grafy proste. > Grafy wdzięczne >
Matematyka dyskretna > Teoria grafów > Grafy proste > Grafy całkowe >

DOWNLOAD Mathematica NotebookWheelGraphs

Jak zdefiniowano w tej pracy, graf kołowy W_n rzędu n, czasami nazywany po prostu nkołem (Harary 1994, s. 46; Pemmaraju i Skiena 2003, s. 248; Tutte 2005, s. 78), jest grafem, który zawiera cykl rzędu n-1 i dla którego każdy wierzchołek grafu w cyklu jest połączony z jednym innym wierzchołkiem grafu zwanym piastą. Krawędzie koła, które obejmują piastę, nazywamy szprychami (Skiena 1990, s. 146). Koło W_n może być zdefiniowane jako graf połączony K_1+C_(n-1), gdzie K_1 jest grafem singletonowym, a C_n jest grafem cyklu, co czyni go grafem (n,1)stożkowym.

Zauważ, że istnieją dwie konwencje indeksowania dla grafów kołowych, przy czym niektórzy autorzy (np., Gallian 2007), przyjmują konwencję, że W_n oznacza graf kołowy na n+1 węzłach.

Graf tetraedryczny (tj. K_4) jest izomorficzny do W_4, a W_5 jest izomorficzny do kompletnego grafu trójdzielnego K_(1,2,2). W ogólności, graf nkołowy jest szkieletem (n-1)piramidy.

W_5 jest jednym z dwóch grafów otrzymanych przez usunięcie dwóch krawędzi z grafu pentatopowego K_5, drugim jest graf domu X.

Grafy kołowe są wdzięczne (Frucht 1979).

Graf kołowy W_n ma wymiar grafu 2 dla n=7 (a więc jest jednostkowy) i wymiar 3 w pozostałych przypadkach (a więc nie jest jednostkowy) (Erdős et al. 1965, Buckley i Harary 1988).

Dowolny graf kołowy jest grafem samodualnym.

Grafy kołowe można skonstruować w języku Wolfram Language za pomocą WheelGraph. Wstępnie obliczone własności pewnej liczby grafów kołowych są dostępne za pomocą GraphData.

WheelGraphCycles4WheelGraphCycles5

Liczba cykli grafu w grafie kołowym W_n jest dana przez n^2-3n+3, lub 7, 13, 21, 31, 43, 57, … (OEIS A002061) dla n=4, 5, ….

W grafie kołowym piasta ma stopień n-1, a pozostałe węzły mają stopień 3. Grafy kołowe są 3-połączone. W_4=K_4, gdzie K_4 jest grafem zupełnym czwartego rzędu. Liczba chromatyczna grafu W_n wynosi

 chi(W_n)={3 for n odd; 4 for n even.
(1)

Graf kołowy W_n ma stopień n-1. graf kołowy W_n ma wielomian chromatyczny

 pi(x)=x.
(2)

.