Wykres Heawood

Wykres Heawood

Reprezentacja wykresu Heawood.
Liczba wierzchołków 14
Liczba krawędzi 21
Dystrybucja stopni 3- regularne
Promień 3
Średnica 3
Siatka 6
Automorfizmy 336 (PGL (2,7))
Liczba chromatyczna 2
Indeks chromatyczny 3
Nieruchomości Cage
Cubic
Biparty
Cayley
Graph Moore
Hamiltonian Graph
Symmetric
Perfect

W teorii wykres The Heawood wykres jest symetryczny sześcienny wykres z wierzchołków 14 i 21 krawędzi. Swoją nazwę zawdzięcza Percy'emu Johnowi Heawoodowi , brytyjskiemu matematykowi urodzonemu w 1861 roku i zmarł w 1955 roku.

Nieruchomości

Właściwości ogólne

Graf Heawood to (3,6) - klatka , czyli minimalny wykres liczby wierzchołków o oczkach 6 i sześciennych . W rzeczywistości jest to wyjątkowa (3,6) -klatka, a jej rozmiar pokrywa się z ograniczeniem Moore'a, dolnym ograniczeniem liczby wierzchołków, które może mieć klatka. Taki wykres nazywa się wykresem Moore'a .

Zarówno średnica wykresu Heawood, jak i jego promień są równe 3. Oznacza to, że wszystkie jego wierzchołki należą do jego środka.

Graf Heawood jest połączony 3 wierzchołkami i 3 krawędziami , to znaczy jest połączony i aby był rozłączony, musi być pozbawiony co najmniej 3 wierzchołków lub 3 krawędzi. Ponieważ jest to regularna liczba stopni 3, liczba ta jest optymalna. Wykres Heawood jest zatem wykresem optymalnie połączonym.

Jest również hamiltonianem , to znaczy ma cykl przechodzący przez wszystkie wierzchołki raz i tylko raz.

Dipsy

Wykres Heawood nie jest planarny . W rzeczywistości, aby narysować go na płaszczyźnie, konieczne jest przecięcie kilku krawędzi. Można go narysować tylko 3 skrzyżowaniami, a liczba ta jest minimalna. W rzeczywistości, według Pegga i Exoo, wykres Heawood z 14 wierzchołkami byłby najmniejszym wykresem sześciennym wymagającym narysowania 3 przecięć na płaszczyźnie.

Z drugiej strony, wykres Heawood można zanurzyć na toroidzie , dlatego jest to wykres toroidalny .

Kolorowanie

Liczba chromatyczna wykresu Heawood wynosi 2. Oznacza to, że można go pokolorować 2 kolorami, tak aby dwa wierzchołki połączone krawędzią miały zawsze różne kolory. Ta liczba jest minimalna.

Chromatycznej wskaźnik wykresu Heawood to 3. Nie jest więc 3-barwienie krawędzi grafu, tak że dwie krawędzie incydent ten sam wierzchołek zawsze są w różnych kolorach. Ta liczba jest minimalna.

Można policzyć różne kolory wykresu Heawood. Daje to funkcję zależną od liczby dozwolonych kolorów. Jest to funkcja wielomianowa, a związany z nią wielomian nazywany jest wielomianem chromatycznym . Ten wielomian stopnia 14 przyjmuje jako pierwiastki wszystkie dodatnie lub zerowe liczby całkowite ściśle mniejsze niż 2. Jest równy:

Właściwości algebraiczne

Graf Heawood jest symetryczny , to znaczy, że jego grupa automorfizmów działa przejściowo na jego krawędziach, wierzchołkach i łukach. Jej grupa automorfizmów jest rzędu 336 i jest izomorficzna z liniową grupą rzutową PGL (2,7). Jest to jedyny symetryczny graf sześcienny z 14 wierzchołkami, stąd jego nazwa F014A w Foster Census klasyfikująca wszystkie symetryczne wykresy sześcienne.

Wielomian charakterystyczny z matrycy przylegania z Heawood wykresie oznacza: . Jest to jedyny wykres z tym charakterystycznym wielomianem, który sprawia, że ​​jest to wykres jednoznacznie określony przez jego widmo , to znaczy zbiór wartości własnych macierzy sąsiedztwa .

Galeria

Bibliografia

  1. (w) Weisstein, Eric W. „Heawood Graph” Z MathWorld - A Wolfram Web Resource
  2. (en) Gordon Royle F014A
  3. (en) Rectilinear Drawings of Famous Graphs to strona główna Geoffrey Exoo
  4. (in) Pegg i Exoo AND G. „Wykresy liczb krzyżowych”. Mathematica J. 11, 2009
  5. (w) JA Bondy i USR Murty , Graph Theory with Applications , Nowy Jork, Północna Holandia,1976( ISBN  978-0-444-19451-0 , czytaj online ) , str.  237
  6. (w) Gordon Royle, Marston Conder, Brendan McKay i Peter Dobscanyi, Sześcienne wykresy symetryczne (The Foster Census)