Wykres sześcienny

Graf Petersena jest grafem sześciennym.

Kompletny wykres dwudzielny jest przykładem wykresu dwusześciennego

{\ Displaystyle K_ {3,3}}

W matematycznej dziedzinie teorii grafów graf sześcienny to graf , w którym wszystkie wierzchołki mają stopień trzeci. Innymi słowy, graf sześcienny jest grafem 3-regularnym . Grafy sześcienne są również nazywane grafami trójwartościowymi .

Graf dwusześcienny to graf dwudzielny sześcienny .

Symetria

W 1932 roku Ronald M. Foster zaczął zbierać przykłady sześciennych grafów symetrycznych , tworząc początek spisu ludności Fostera . Wiele dobrze znanych pojedynczych wykresów jest sześciennych i symetrycznych, w tym wykres użyteczności , wykres Petersena , wykres Heawood , wykres Möbiusa – Kantora , wykres Pappusa , wykres Desargues , wykres Nauru , wykres Coxetera , wykres Tutte – Coxeter wykres , wykres Dycka , wykres Fostera i wykres Biggsa-Smitha . WT Tutte sklasyfikował symetryczne grafy sześcienne według najmniejszej liczby całkowitej s , tak że każde dwie zorientowane ścieżki o długości s można odwzorować na siebie dokładnie o jedną symetrię grafu. Pokazał, że s wynosi co najwyżej 5 i przedstawił przykłady wykresów z każdą możliwą wartością s od 1 do 5.

Półsymetryczne wykresy sześcienne obejmują wykres Graya (najmniejszy półsymetryczny wykres sześcienny), wykres Ljubljana i 12-klatkowy Tutte .

Graf Fruchta jest jednym z pięciu najmniejszych grafów sześciennych bez symetrii: posiada tylko jeden automorfizm grafu , automorfizm tożsamościowy.

Kolorowanki i samodzielne zestawy

Zgodnie z twierdzeniem Brooksa każdy spójny graf sześcienny inny niż pełny graf K ₄ ma kolorowanie wierzchołków co najwyżej trzema kolorami. Dlatego każdy spójny graf sześcienny inny niż K ₄ ma niezależny zbiór co najmniej n /3 wierzchołków, gdzie n jest liczbą wierzchołków w grafie: na przykład największa klasa kolorów w 3-kolorowaniu ma co najmniej tyle wierzchołki.

Zgodnie z twierdzeniem Vizinga każdy graf sześcienny potrzebuje trzech lub czterech kolorów do pokolorowania krawędzi . Kolorowanie 3-krawędziowe jest znane jako kolorowanie Taita i tworzy podział krawędzi grafu na trzy idealne dopasowania . Zgodnie z twierdzeniem Kőniga o kolorowaniu linii każdy graf dwusześcienny ma kolorowanie Taita.

Bezmostkowe grafy sześcienne, które nie mają zabarwienia Taita, są znane jako snarki . Obejmują one wykres Petersena , wykres Tietze , snark Blanušy , snark kwiatu , snark podwójnej gwiazdy , snark Szekeresa i snark Watkinsa . Istnieje nieskończona liczba różnych snarków.

Topologia i geometria

Wykresy sześcienne powstają naturalnie w topologii na kilka sposobów. Na przykład, jeśli ktoś uważa graf za 1-wymiarowy kompleks CW , grafy sześcienne są ogólne , ponieważ większość map łączących 1 komórkę jest rozłączna z 0-szkieletem grafu. Grafy sześcienne są również tworzone jako wykresy prostych wielościanów w trzech wymiarach, wielościanów, takich jak dwunastościan foremny z właściwością spotykania się trzech ścian w każdym wierzchołku.

Reprezentacja płaskiego osadzania jako mapy zakodowanej w postaci wykresu

Dowolny wykres osadzony na dwuwymiarowej powierzchni może być reprezentowany jako sześcienna struktura grafu, znana jako mapa zakodowana w grafie . W tej strukturze każdy wierzchołek grafu sześciennego reprezentuje flagę osadzania, wzajemnie incydentalną trójkę wierzchołka, krawędzi i powierzchni powierzchni. Trzej sąsiedzi każdej flagi to trzy flagi, które można z niej uzyskać, zmieniając jednego z członków tej wzajemnie incydentalnej trójki i pozostawiając niezmienione pozostałe dwa elementy.

hamiltonowość

Było wiele badań nad hamiltonicznością grafów sześciennych. W 1880 roku PG Tait przypuszczał, że każdy sześcienny graf wielościenny ma obwód Hamiltona . William Thomas Tutte dostarczył kontrprzykładu dla hipotezy Taita , graf Tutte z 46 wierzchołkami , w 1946 r. W 1971 r. Tutte przypuszczał, że wszystkie grafy dwusześcienne są hamiltonowskie. Jednak Joseph Horton dostarczył kontrprzykładu dla 96 wierzchołków, wykresu Hortona . Później Mark Ellingham skonstruował jeszcze dwa kontrprzykłady: wykresy Ellinghama – Hortona . Hipoteza Barnette'a , wciąż otwarta kombinacja hipotezy Taita i Tutte'a, stwierdza, że każdy dwusześcienny graf wielościenny jest hamiltonowski. Gdy graf sześcienny jest hamiltonowski, notacja LCF pozwala na jego zwięzłe przedstawienie.

Jeśli graf sześcienny zostanie losowo wybrany jednostajnie spośród wszystkich grafów sześciennych n -wierzchołków, to jest bardzo prawdopodobne, że będzie hamiltonowski: odsetek grafów sześciennych n -wierzchołków, które są hamiltonowskie, dąży do jednego w granicy, gdy n dąży do nieskończoności.

David Eppstein przypuszczał, że każdy n -wierzchołkowy graf sześcienny ma co najwyżej 2 ^{n / 3} (w przybliżeniu 1,260 ⁿ ) różnych cykli Hamiltona i podał przykłady grafów sześciennych z taką liczbą cykli. Najlepszym sprawdzonym oszacowaniem liczby różnych cykli Hamiltona jest ${\ Displaystyle O ({1,276} ^ {n})}$ .

Inne właściwości

Nierozwiązany problem z matematyki :

Jaka jest największa możliwa szerokość ścieżki sześciennego wykresu wierzchołków ${\ displaystyle n}$ ?

(więcej nierozwiązanych problemów z matematyki)

Szerokość ścieżki dowolnego wykresu sześciennego o n wierzchołkach wynosi co najwyżej n /6. Najbardziej znana dolna granica szerokości ścieżki grafów sześciennych wynosi 0,082 n . Nie wiadomo, jak zmniejszyć tę różnicę między tą dolną granicą a górną granicą n /6.

Z lematu dotyczącego uzgadniania , udowodnionego przez Leonharda Eulera w 1736 r. w ramach pierwszego artykułu na temat teorii grafów, wynika, że każdy graf sześcienny ma parzystą liczbę wierzchołków.

Twierdzenie Petersena mówi, że każdy graf sześcienny bez mostków ma idealne dopasowanie . Lovász i Plummer przypuszczali, że każdy graf sześcienny bez mostków ma wykładniczą liczbę doskonałych dopasowań. Hipoteza została niedawno udowodniona, pokazując, że każdy sześcienny graf bezmostkowy z n wierzchołkami ma co najmniej 2 ^n/3656 doskonałych dopasowań.

Algorytmy i złożoność

Kilku badaczy badało złożoność algorytmów czasu wykładniczego ograniczonych do grafów sześciennych. Na przykład, stosując programowanie dynamiczne do dekompozycji ścieżki wykresu, Fomin i Høie pokazali, jak znaleźć swoje maksymalne zbiory niezależne w czasie 2 ^{n /6 + o( n )} . Problem komiwojażera w grafach sześciennych można rozwiązać w czasie O(1,2312 ⁿ ) i przestrzeni wielomianowej.

Kilka ważnych problemów optymalizacji grafów jest APX trudnych , co oznacza, że chociaż mają algorytmy aproksymacji , których współczynnik aproksymacji jest ograniczony przez stałą, nie mają schematów aproksymacji w czasie wielomianowym , których współczynnik aproksymacji dąży do 1, chyba że P=NP . Należą do nich problemy znalezienia minimalnego pokrycia wierzchołków , maksymalnego zbioru niezależnego , minimalnego zbioru dominującego i maksymalnego cięcia . Liczba przecięć (minimalna liczba krawędzi, które przecinają się na dowolnym rysunku wykresu ) grafu sześciennego jest również NP-trudna dla grafów sześciennych, ale można ją przybliżyć. Udowodniono , że problem komiwojażera na wykresach sześciennych jest NP-trudny do przybliżenia do dowolnego czynnika mniejszego niż 1153/1152.

Zobacz też

Tabela prostych wykresów sześciennych

Linki zewnętrzne

Royle, Gordon. „Symetryczne wykresy sześcienne (spis Fostera)” . Zarchiwizowane od oryginału w dniu 2011-10-23.
Weisstein, Eric W. „Wykres dwusześcienny” . MathWorld .
Weisstein, Eric W. „Wykres sześcienny” . MathWorld .