Wykres Goldnera-Harary'ego
| Wykres Goldnera-Harary'ego | |
|---|---|
 | |
| Nazwany po |
A. Goldner, Frank Harary |
| Wierzchołki | 11 |
| Krawędzie | 27 |
| Promień | 2 |
| Średnica | 2 |
| Obwód | 3 |
| Automorfizmy | 12 ( D 6 ) |
| Liczba chromatyczna | 4 |
| Indeks chromatyczny | 8 |
| Nieruchomości |
Wielościenna planarna akordowa Idealna szerokość drzewa 3 |
| Tabela wykresów i parametrów | |
W matematycznej dziedzinie teorii grafów wykres Goldnera -Harary'ego jest prostym grafem nieskierowanym z 11 wierzchołkami i 27 krawędziami. Został nazwany na cześć A. Goldnera i Franka Harary'ego , którzy w 1975 roku udowodnili, że jest to najmniejszy niehamiltonowski maksymalny planarny graf . Ten sam wykres został już podany jako przykład niehamiltonowskiego wielościanu uproszczonego przez Branko Grünbauma w 1967 roku.
Nieruchomości
Wykres Goldnera-Harary'ego jest grafem planarnym : można go narysować na płaszczyźnie tak, aby żadna z jego krawędzi się nie przecinała. Po narysowaniu na płaszczyźnie wszystkie jego ściany są trójkątne, co czyni go maksymalnym grafem planarnym . Jak każdy maksymalny graf planarny, jest on również spójny w 3 wierzchołkach : usunięcie dowolnych dwóch jego wierzchołków pozostawia podgraf spójny .
Wykres Goldnera-Harary'ego jest również niehamiltonowski . Najmniejsza możliwa liczba wierzchołków dla niehamiltonowskiego wielościennego wynosi 11. Dlatego graf Goldnera-Harary'ego jest minimalnym przykładem grafów tego typu. Jednak graf Herschela , inny wielościan niehamiltonowski z 11 wierzchołkami, ma mniej krawędzi.
Jako niehamiltonowski maksymalny graf planarny, wykres Goldnera-Harary'ego stanowi przykład wykresu planarnego o grubości książki większej niż dwa. Opierając się na istnieniu takich przykładów, Bernhart i Kainen przypuszczali, że grubość księgi grafów planarnych może być dowolnie duża, ale później wykazano, że wszystkie grafy planarne mają grubość księgi co najwyżej cztery.
Ma grubość książki 3, liczbę chromatyczną 4, indeks chromatyczny 8, obwód 3, promień 2, średnicę 2 i jest grafem 3-krawędziowym .
Jest to również 3-drzewo , a zatem ma szerokość drzewa 3. Jak każde k -drzewo, jest to graf akordowy . Jako planarne 3-drzewo stanowi przykład sieci apollińskiej .
Geometria
Zgodnie z twierdzeniem Steinitza , wykres Goldnera-Harary'ego jest grafem wielościennym : jest płaski i połączony w 3, więc istnieje wypukły wielościan, którego szkieletem jest wykres Goldnera- Harary'ego .
Z geometrycznego punktu widzenia wielościan reprezentujący wykres Goldnera-Harary'ego można utworzyć przez przyklejenie czworościanu do każdej ściany trójkątnej dwupiramidy , podobnie do sposobu, w jaki tworzy się ośmiościan triakis przez przyklejenie czworościanu do każdej ściany ośmiościanu . Oznacza to, że jest to Kleetope trójkątnej dypiramidy. Podwójny wykres wykresu Goldnera-Harary'ego jest reprezentowany geometrycznie przez obcięcie trójkątnego pryzmatu .
Właściwości algebraiczne
Grupa automorfizmów wykresu Goldnera-Harary'ego jest rzędu 12 i jest izomorficzna z grupą dwuścienną D 6 , grupą symetrii regularnego sześciokąta , obejmującą zarówno obroty, jak i odbicia.
Charakterystyczny wielomian wykresu Goldnera-Harary'ego to : .
Linki zewnętrzne