Konstrukcja Hajós

W teorii grafów , gałęzi matematyki, konstrukcja Hajósa jest operacją na grafach nazwanych na cześć György Hajósa ( 1961 ), której można użyć do skonstruowania dowolnego wykresu krytycznego lub dowolnego wykresu, którego liczba chromatyczna jest co najmniej pewnym określonym progiem.

Konstrukcja

Zastosowanie konstrukcji Hajósa do dwóch kopii K ₄ poprzez identyfikację wierzchołka z każdej kopii w jeden wierzchołek (pokazany obydwoma kolorami), usunięcie krawędzi incydentnej z połączonym wierzchołkiem w każdym podgrafie (przerywana) i dodanie nowej krawędzi łączącej punkty końcowe usuniętych krawędzi (gruba zieleń), tworzy wrzeciono Mosera .

Niech G i H będą dwoma grafami nieskierowanymi , vw będzie krawędzią G , a xy będzie krawędzią H. Następnie konstrukcja Hajósa tworzy nowy graf, który łączy dwa grafy, identyfikując wierzchołki v i x w jeden wierzchołek, usuwając dwie krawędzie vw i xy i dodając nową krawędź wy .

Na przykład niech G i H będą pełnymi grafami K ₄ na czterech wierzchołkach; ze względu na symetrię tych wykresów wybór krawędzi do wybrania z każdego z nich jest nieistotny. W tym przypadku wynikiem zastosowania konstrukcji Hajósa jest wrzeciono Mosera , wykres jednostkowej odległości z siedmioma wierzchołkami , który wymaga czterech kolorów.

Jako inny przykład, jeśli G i H są odpowiednio wykresami cykli o długości p i q , to wynikiem zastosowania konstrukcji Hajósa jest sam wykres cyklu o długości p + q - 1 .

Konstruowalne wykresy

O grafie G mówi się, że jest k - konstruowalny (lub Hajósk- k - konstruowalny), gdy tworzy się na jeden z następujących trzech sposobów:

• Pełny graf K _k jest k -konstrukcyjny.
• Niech G i H będą dowolnymi dwoma k -konstrukcyjnymi grafami. Wtedy graf utworzony przez zastosowanie konstrukcji Hajósa do G i H jest k -konstrukcyjny.
• Niech G będzie dowolnym k -konstrukcyjnym grafem i niech u i v będą dowolnymi dwoma niesąsiadującymi wierzchołkami w G . Wtedy graf utworzony przez połączenie u i v w jeden wierzchołek jest również k -konstrukcyjny. Równoważnie, ten wykres można utworzyć przez dodanie krawędzi uv do wykresu, a następnie skrócenie go.

Połączenie z kolorowaniem

Łatwo sprawdzić, czy każdy k -konstrukcyjny graf wymaga co najmniej k kolorów w każdym odpowiednim grafie . Rzeczywiście, jest to jasne dla pełnego grafu K _k , a efektem zidentyfikowania dwóch nieprzylegających wierzchołków jest wymuszenie, aby miały one ten sam kolor w dowolnym zabarwieniu, co nie zmniejsza liczby kolorów. W samej konstrukcji Hajós nowa krawędź wy wymusza, aby co najmniej jeden z dwóch wierzchołków w i y miał inny kolor niż połączony wierzchołek dla v i x , więc każde odpowiednie pokolorowanie połączonego wykresu prowadzi do odpowiedniego pokolorowania jednego z dwóch mniejszych grafów, z których został utworzony, co ponownie powoduje, że wymaga on k kolorów.

Hajós udowodnił silniej, że graf wymaga co najmniej k kolorów w dowolnym odpowiednim zabarwieniu wtedy i tylko wtedy, gdy zawiera k -konstruowalny graf jako podgraf. Równoważnie, każdy k - graf krytyczny (graf, który wymaga k kolorów, ale dla którego każdy właściwy podgraf wymaga mniej kolorów) jest k -konstrukcyjny. Alternatywnie, każdy wykres, który wymaga k kolory mogą być tworzone przez połączenie konstrukcji Hajósa, operacji identyfikowania dowolnych dwóch nieprzylegających wierzchołków oraz operacji dodawania wierzchołka lub krawędzi do danego grafu, zaczynając od pełnego grafu K _k .

Podobną konstrukcję można zastosować do kolorowania listy zamiast kolorowania.

Konstruowalność grafów krytycznych

Dla k = 3 każdy graf k -krytyczny (czyli każdy cykl nieparzysty) można wygenerować jako k -konstrukcyjny graf taki, że wszystkie grafy utworzone w jego konstrukcji są również k -krytyczne. Dla k = 8 nie jest to prawdą: graf znaleziony przez Catlina (1979) jako kontrprzykład dla hipotezy Hajósa, że ​​grafy k -chromatyczne zawierają podpodział K _k , również służy jako kontrprzykład dla tego problemu. następnie k -krytyczne, ale nie k -konstruowalne grafy wyłącznie za pomocą k -krytycznych grafów zostały znalezione dla wszystkich k ≥ 4 . Dla k = 4 jednym z takich przykładów jest wykres otrzymany z wykresu dwunastościanu przez dodanie nowej krawędzi między każdą parą antypodalnych wierzchołków

Numer Hajósa

Ponieważ połączenie dwóch niesąsiadujących wierzchołków zmniejsza liczbę wierzchołków w grafie wynikowym, liczba operacji potrzebnych do przedstawienia danego grafu G przy użyciu operacji zdefiniowanych przez Hajósa może przekroczyć liczbę wierzchołków w G .

Dokładniej, Mansfield i Welsh (1982) definiują liczbę Hajósa h ( G ) grafu k -chromatycznego G jako minimalną liczbę kroków potrzebnych do skonstruowania G z K _k , gdzie każdy krok tworzy nowy graf przez połączenie dwóch poprzednich utworzonych grafów, łącząc dwa nieprzylegające wierzchołki wcześniej utworzonego grafu lub dodając wierzchołek lub krawędź do wcześniej utworzonego grafu. Pokazali, że dla n -wierzchołkowego grafu G z m krawędzie, h ( sol ) ≤ 2 ^{n 2 /3 - m + 1} - 1 . Jeśli każdy wykres ma wielomianową liczbę Hajósa, oznaczałoby to, że możliwe jest udowodnienie niekoloryzacji w niedeterministycznym czasie wielomianowym , a zatem oznaczałoby to, że NP = co-NP , wniosek uważany za mało prawdopodobny przez teoretyków złożoności. Jednak nie wiadomo, jak udowodnić nie-wielomianowe dolne granice liczby Hajósa bez przyjęcia pewnego założenia teoretycznego o złożoności, a gdyby takie ograniczenie można było udowodnić, oznaczałoby to również istnienie nie-wielomianowych granic na niektórych typach Fregego system w logice matematycznej .

Minimalny rozmiar drzewa wyrażenia opisującego konstrukcję Hajósa dla danego grafu G może być znacznie większy niż liczba Hajósa G , ponieważ najkrótsze wyrażenie dla G może wielokrotnie wykorzystywać te same wykresy, co jest niedozwolone w wyrażeniu drzewo. Istnieją grafy 3-chromatyczne, dla których najmniejsze takie drzewo wyrażeń ma rozmiar wykładniczy.

Inne aplikacje

Koester (1991) użył konstrukcji Hajósa do wygenerowania nieskończonego zestawu 4-krytycznych grafów wielościennych , z których każdy ma ponad dwa razy więcej krawędzi niż wierzchołków. Podobnie Liu i Zhang (2006) wykorzystali konstrukcję, zaczynając od wykresu Grötzscha , do wygenerowania wielu grafów bez trójkątów krytycznych 4 , które okazały się trudne do pokolorowania przy użyciu tradycyjnych algorytmów śledzenia wstecznego .

W kombinatoryce wielościennej Euler (2003) użył konstrukcji Hajósa do wygenerowania ścianek stabilnego zestawu polytope .

Notatki

• Catlin, PA (1979), „Przypuszczenie kolorowania wykresów Hajósa: wariacje i kontrprzykłady”, Journal of Combinatorial Theory , Seria B, 26 : 268–274, doi : 10.1016/0095-8956 (79) 90062-5 .
•   Diestel, Reinhard (2006), Graph Theory , Graduate Texts in Mathematics, tom. 173 (wyd. 3), Springer-Verlag, s. 117–118, ISBN 978-3-540-26183-4 .
•   Euler, Reinhardt (2003), „Konstrukcja Hajósa i polytopy”, Optymalizacja kombinatoryczna - Eureka, kurczysz się! , Notatki z wykładów z informatyki, tom. 2570, Berlin: Springer-Verlag, s. 39–47, doi : 10.1007/3-540-36478-1_6 , MR 2163949 .
•   Gravier, Sylvain (1996), „Twierdzenie podobne do Hajósa do kolorowania list”, Matematyka dyskretna , 152 (1–3): 299–302, doi : 10.1016/0012-365X (95) 00350-6 , MR 1388650 .
• Hajós, G. (1961), "Über eine Konstruktion nicht n -färbbarer Graphen", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe , 10 , s. 116–117 . Cytowane przez Jensena i Tofta (1994) .
•   Iwama, Kazuo ; Pitassi, Toniann (1995), „Wykładnicze dolne granice dla rachunku Hajósa przypominającego drzewo”, Information Processing Letters , 54 (5): 289–294, doi : 10.1016/0020-0190 (95) 00035-B , MR 1336013 .
•   Jensen, Tommy R.; Royle, Gordon F. (1999), „Konstrukcje Hajósa grafów krytycznych”, Journal of Graph Theory , 30 (1): 37–50, doi : 10,1002 / (SICI) 1097-0118 (199901) 30: 1 <37: :AID-JGT5>3.0.CO;2-V , MR 1658542 .
•   Jensen, Tommy R.; Toft, Bjarne (1994), Graph Coloring Problems (wyd. 2), John Wiley and Sons, ISBN 978-0-471-02865-9 .
•   Koester, Gerhard (1991), „Na 4-krytycznych grafach planarnych o dużej gęstości krawędzi”, Discrete Mathematics , 98 (2): 147–151, doi : 10.1016/0012-365X (91) 90039-5 , MR 1144633 .
•   Kubale, Marek (2004), Kolorystyka wykresów , Matematyka współczesna, t. 352, Amerykańskie Towarzystwo Matematyczne, s. 156, ISBN 978-0-8218-3458-9 .
• Liu, Sheng; Zhang, Jian (2006), „Używanie konstrukcji Hajósa do generowania twardych przypadków 3-kolorowalności wykresu”, Sztuczna inteligencja i obliczenia symboliczne , notatki z wykładów z informatyki, tom. 4120, Springer-Verlag, s. 211–225, doi : 10.1007/11856290_19 .
•   Mansfield, AJ; Welsh, DJA (1982), „Niektóre problemy z kolorowaniem i ich złożoność”, Teoria grafów (Cambridge, 1981) , North-Holland Math. Stud., tom. 62, Amsterdam: Holandia Północna, s. 159–170, MR 0671913 .
•    Pitassi, Toniann ; Urquhart, Alasdair (1995), „Złożoność rachunku Hajósa”, SIAM Journal on Discrete Mathematics , 8 (3): 464–483, CiteSeerX 10.1.1.30.5879 , doi : 10.1137/S089548019224024X , MR 1341550 .