Wykres bez trójkątów

W matematycznym obszarze teorii grafów graf bez trójkątów to graf nieskierowany, w którym żadne trzy wierzchołki nie tworzą trójkąta o krawędziach. Grafy bez trójkątów można równoważnie zdefiniować jako grafy z liczbą klik ≤ 2, grafy z obwodem ≥ 4, grafy bez indukowanych 3 cykli lub grafy lokalnie niezależne .

Grafy bez trójkątów z największą liczbą wierzchołków są zrównoważonymi kompletnymi grafami dwudzielnymi . Wiele grafów bez trójkątów nie jest dwudzielnych, na przykład dowolny wykres cyklu C _n dla nieparzystego n > 3.

Zgodnie z twierdzeniem Turána graf bez trójkątów n -wierzchołków z maksymalną liczbą krawędzi jest kompletnym grafem dwudzielnym, w którym liczba wierzchołków po każdej stronie dwupodziału jest możliwie równa.

Problem ze znalezieniem trójkąta

Problem znalezienia trójkąta to problem określenia, czy graf jest pozbawiony trójkątów, czy nie. Gdy wykres zawiera trójkąt, algorytmy są często wymagane do wyprowadzenia trzech wierzchołków, które tworzą trójkąt na grafie.

Można sprawdzić, czy graf o m krawędziach jest pozbawiony trójkątów w czasie O ( m ^1,41 ) . Innym ³ podejściem jest znalezienie śladu A , gdzie A jest macierzą sąsiedztwa grafu. Ślad jest równy zero wtedy i tylko wtedy, gdy wykres nie zawiera trójkątów. W przypadku gęstych grafów efektywniejsze jest użycie tego prostego algorytmu, który opiera się na mnożeniu macierzy , ponieważ zmniejsza złożoność czasową do O ( n ^2,373 ) , gdzie n jest liczbą wierzchołków.

Jak wykazali Imrich, Klavžar i Mulder (1999) , rozpoznawanie grafów bez trójkątów jest równoważne pod względem złożoności rozpoznawaniu grafów medianowych ; jednak obecnie najlepsze algorytmy rozpoznawania wykresów median wykorzystują wykrywanie trójkątów jako podprogram, a nie odwrotnie.

Złożoność drzewa decyzyjnego lub złożoność zapytania problemu, gdy zapytania są kierowane do wyroczni przechowującej macierz sąsiedztwa grafu, wynosi Θ( n ² ) . Jednak w przypadku algorytmów kwantowych najlepiej znaną dolną granicą jest Ω( n ) , ale najbardziej znanym algorytmem jest O ( n ^5/4 ) .

Liczba niezależności i teoria Ramseya

Niezależny zestaw √ n wierzchołków w grafie pozbawionym trójkątów n -wierzchołków jest łatwy do znalezienia: albo istnieje wierzchołek z więcej niż √ n sąsiadami (w takim przypadku sąsiedzi są niezależnym zbiorem) lub wszystkie wierzchołki mają mniej niż √ n sąsiadów (w takim przypadku dowolny maksymalny niezależny zbiór musi mieć co najmniej √ n wierzchołków). To ograniczenie można nieco zacieśnić: w każdym grafie bez trójkątów istnieje niezależny zbiór ${\ Displaystyle \ Omega ({\ sqrt {n \ log n}})}$ wierzchołków, aw niektórych grafach bez trójkątów każdy niezależny zestaw ma ${\ Displaystyle O ({\ sqrt {n \ log n}})}$ wierzchołków. Jednym ze sposobów generowania grafów bez trójkątów, w których wszystkie niezależne zbiory są małe, jest proces bez trójkątów, w którym generuje się maksymalny wykres bez trójkątów poprzez wielokrotne dodawanie losowo wybranych krawędzi, które nie uzupełniają trójkąta. Z dużym prawdopodobieństwem proces ten tworzy graf o liczbie niezależności ${\ Displaystyle O ({\ sqrt {n \ log n}})}$ . Możliwe jest również znalezienie grafów regularnych o tych samych właściwościach.

Wyniki te można również interpretować jako dające asymptotyczne granice liczb Ramseya R (3, t ) postaci ${\ Displaystyle \ Theta ({\ tfrac {t ^ {2}}} {\ log t}})}$ : jeśli krawędzie pełnego wykresu na ${\ Displaystyle \ Omega ({\ tfrac {t ^ {2}} {\ log t}})}$ wierzchołki są pokolorowane na czerwono i niebiesko, to albo czerwony wykres zawiera trójkąt, albo, jeśli nie zawiera trójkątów, musi mieć niezależny zestaw o rozmiarze t odpowiadający kliki o tej samej wielkości na niebieskim wykresie.

Kolorowanie wykresów bez trójkątów

Graf Grötzscha to graf bez trójkątów, którego nie można pokolorować mniej niż czterema kolorami

Wiele badań dotyczących grafów bez trójkątów koncentrowało się na kolorowaniu grafów . Każdy graf dwudzielny (to znaczy każdy 2-kolorowy graf) jest pozbawiony trójkątów, a twierdzenie Grötzscha mówi, że każdy graf planarny bez trójkątów może być 3-kolorowy. Jednak niepłaskie grafy bez trójkątów mogą wymagać znacznie więcej niż trzech kolorów.

Pierwsza konstrukcja trójkątnych grafów swobodnych o dowolnie wysokiej liczbie chromatycznej jest dziełem Tutte (piszącego jako Blanche Descartes ). Ta konstrukcja rozpoczęła się od wykresu z pojedynczym wierzchołkiem, powiedzmy, $}}$ skonstruowana indukcyjnie z $Displaystyle G_ {k +$ jako ${\ Displaystyle G_ {1}}$ następująco: niech mają ${\ displaystyle n} sol k {\ displaystyle G_ {$$}$${$$}$ zbiór wierzchołków i dla każdego podzbioru $X$ z $}$${\$ o rozmiarze $G_$ rozłączną kopię ${k}}$$dopasowaniem$ i połącz ją z . Z zasady przegródki indukcyjnie wynika z tego, że nie można pokolorować $+ 1$ ponieważ przynajmniej jeden ze zbiorów musi być pokolorowany monochromatycznie, jeśli wolno nam tylko ${\ displaystyle$$G_ {$ używać k kolorów. Mycielski (1955) zdefiniował konstrukcję, zwaną obecnie Mycielską , służącą do tworzenia nowego grafu bez trójkątów z innego grafu bez trójkątów. Jeśli graf ma liczbę chromatyczną k , to jego mycielskian ma liczbę chromatyczną k + 1, więc tej konstrukcji można użyć do pokazania, że ​​​​do pokolorowania niepłaskich grafów bez trójkątów może być potrzebna dowolnie duża liczba kolorów. W szczególności graf Grötzscha , graf 11-wierzchołkowy utworzony przez wielokrotne zastosowanie konstrukcji Mycielskiego, jest grafem bez trójkątów, którego nie można pokolorować mniej niż czterema kolorami i jest najmniejszym grafem o tej właściwości. Gimbel i Thomassen (2000) oraz Nilli (2000) wykazali, że liczba kolorów potrzebnych do pokolorowania dowolnego wykresu bez trójkątów o krawędzi m wynosi

${\ Displaystyle O \ lewo ({\ Frac {m ^ {1/3}} {(\ log m) ^ {2/3}}} \ prawo )}$

i że istnieją grafy bez trójkątów, które mają liczby chromatyczne proporcjonalne do tej granicy.

Było również kilka wyników dotyczących kolorowania do minimalnego stopnia na grafach bez trójkątów. Andrásfai, Erdős i Sós (1974) udowodnili, że dowolny graf bez trójkątów n -wierzchołków, w którym każdy wierzchołek ma więcej niż 2 n /5 sąsiadów, musi być dwudzielny. Jest to najlepszy możliwy wynik tego typu, ponieważ cykl 5 wymaga trzech kolorów, ale ma dokładnie 2 n /5 sąsiadów na wierzchołek. Zmotywowani tym wynikiem, Erdős i Simonovits (1973) przypuszczali, że każdy n -wierzchołkowy graf bez trójkątów, w którym każdy wierzchołek ma co najmniej n /3 sąsiadów można pokolorować tylko trzema kolorami; jednak Häggkvist (1981) obalił to przypuszczenie, znajdując kontrprzykład, w którym każdy wierzchołek grafu Grötzscha jest zastąpiony niezależnym zbiorem o starannie dobranym rozmiarze. Jin (1995) wykazał, że dowolny graf bez trójkątów n -wierzchołków, w którym każdy wierzchołek ma więcej niż 10 n /29 sąsiadów, musi być trójkolorowy; jest to najlepszy możliwy wynik tego typu, ponieważ graf Häggkvista wymaga czterech kolorów i ma dokładnie 10 n /29 sąsiadów na wierzchołek. Wreszcie, Brandt i Thomassé (2006) udowodnił, że dowolny graf bez trójkątów n -wierzchołków, w którym każdy wierzchołek ma więcej niż n /3 sąsiadów, musi być 4-kolorowalny. Dodatkowe wyniki tego typu nie są możliwe, ponieważ Hajnal znalazł przykłady grafów bez trójkątów z dowolnie dużą liczbą chromatyczną i minimalnym stopniem (1/3 − ε) n dla dowolnego ε > 0.

Zobacz też

• Graf Andrásfai , rodzina grafów cyrkulacyjnych bez trójkątów o średnicy dwa
• Wykres Hensona , graf bez nieskończonych trójkątów, który zawiera wszystkie grafy bez trójkątów skończonych jako indukowane podgrafy
• Wykres przesunięcia , rodzina grafów bez trójkątów o dowolnie wysokiej liczbie chromatycznej
• K sol ${$$1}$ \
• trójkąta monochromatycznego , problem podziału krawędzi danego grafu na dwa grafy bez trójkątów
• Problem Ruzsy – Szemerédiego na wykresach, w których każda krawędź należy do dokładnie jednego trójkąta

Źródła

notatek

•    Alon, Noga ; Ben-Szimon, Sonny; Krivelevich, Michael (2010), „Uwaga na temat regularnych wykresów Ramseya”, Journal of Graph Theory , 64 (3): 244–249, arXiv : 0812,2386 , doi : 10,1002/jgt.20453 , MR 2674496 , S2CID 1784886 .
• Alon, N .; Yuster, R.; Zwick, U. (1994), „Znajdowanie i liczenie cykli o podanej długości”, Proceedings of the 2nd European Symposium on Algorithms, Utrecht, Holandia , s. 354–364 .
• Andrasfai, B.; Erdős, P. ; Sós, VT (1974), „O związku między liczbą chromatyczną, maksymalną kliką i minimalnym stopniem wykresu” (PDF) , Discrete Mathematics , 8 (3): 205–218, doi : 10,1016 / 0012-365X (74) 90133-2 .
•    Belovs, Aleksandrs (2012), „Rozpiętość programów dla funkcji z certyfikatami 1 o stałej wielkości”, Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC '12) , Nowy Jork, NY, USA: ACM, s. 77–84, arXiv : 1105.4024 , doi : 10.1145/2213977.2213985 , ISBN 978-1-4503-1245-5 , S2CID 18771464 .
•    Bohman, Tom (2009), „Proces bez trójkąta”, Postępy matematyki , 221 (5): 1653–1677, arXiv : 0806,4375 , doi : 10,1016/j.aim.2009.02.018 , MR 2522430 , S2CID 17701040 .
•    Boppana, Ravi; Halldórsson, Magnús M. (1992), „Przybliżanie maksymalnych niezależnych zbiorów przez wyłączenie podgrafów”, BIT , 32 (2): 180–196, doi : 10.1007/BF01994876 , MR 1172185 , S2CID 123335474 .
• Brandt S.; Thomassé, S. (2006), Gęste wykresy bez trójkątów są czterokolorowe: rozwiązanie problemu Erdősa – Simonovitsa (PDF) .
•   Chiba, N.; Nishizeki, T. (1985), „Algorytmy arboryczności i list podgrafów” , SIAM Journal on Computing , 14 (1): 210–223, doi : 10.1137/0214017 , S2CID 207051803 .
• Kartezjusz, Blanche (kwiecień 1947), „Problem trzech kolorów”, Eureka , 21 .
• Kartezjusz, Blanche (1954), „Rozwiązanie zaawansowanego problemu nr 4526”, Amer. Matematyka Miesięczny , 61 : 352 .
• Chvátal, Vašek (1974), „Minimalność wykresu Mycielskiego”, Grafy i kombinatoryka (Proc. Capital Conf., George Washington Univ., Washington, DC, 1973) , Lecture Notes in Mathematics, tom. 406, Springer-Verlag, s. 243–246 .
• Erdős, P. ; Simonovits, M. (1973), „O problemie walencyjnym w ekstremalnej teorii grafów”, Discrete Mathematics , 5 (4): 323–334, doi : 10.1016 / 0012-365X (73) 90126-X .
• Erdős, P. ; Suen S.; Winkler, P. (1995), „O wielkości losowego wykresu maksymalnego”, Random Structures and Algorithms , 6 (2–3): 309–318, doi : 10.1002 / rsa.3240060217 .
• Gimbel, Jan; Thomassen, Carsten (2000), „Kolorowanie wykresów bez trójkątów o stałym rozmiarze”, Discrete Mathematics , 219 (1–3): 275–277, doi : 10.1016 / S0012-365X (00) 00087-X .
• Grötzsch, H. (1959), "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel", Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe , 8 , s. 109–120 .
• Häggkvist, R. (1981), „Nieparzyste cykle o określonej długości w grafach niedwudzielnych”, Graph Theory (Cambridge, 1981) , tom. 62, s. 89–99, doi : 10.1016/S0304-0208(08)73552-7 .
•    Imrich, Wilfried; Klavžar, Sandi; Mulder, Henry Martyn (1999), „Wykresy mediany i wykresy bez trójkątów” , SIAM Journal on Discrete Mathematics , 12 (1): 111–118, doi : 10.1137 / S0895480197323494 , MR 1666073 , S2CID 14364050 .
• Itai, A.; Rodeh, M. (1978), „Znajdowanie minimalnego obwodu na wykresie”, SIAM Journal on Computing , 7 (4): 413–423, doi : 10,1137/0207033 .
• Jin, G. (1995), „Trójkątne wykresy czterochromatyczne bez trójkątów”, Discrete Mathematics , 145 (1–3): 151–170, doi : 10.1016/0012-365X (94) 00063-O .
•   Kim, JH (1995), „Liczba Ramseya ma rząd wielkości ${\ Displaystyle R (3, t)}$${\ Displaystyle {\ tfrac {t ^ {2}}} \log t}}}$ " , Struktury losowe i algorytmy , 7 (3): 173–207, doi : 10.1002/rsa.3240070302 , S2CID 16658980 .
•    Le Gall, François (październik 2014), „Ulepszony algorytm kwantowy do znajdowania trójkątów za pomocą argumentów kombinatorycznych”, Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS 2014) , IEEE, s. 216–225, arXiv : 1407,0085 , doi : 10.1109/focs.2014.31 , ISBN 978-1-4799-6517-5 , S2CID 5760574 .
•   Lee, Troja; Magniez, Fryderyk; Santha, Miklos (2013), „Ulepszone algorytmy zapytań kwantowych do wyszukiwania trójkątów i testowania asocjatywności” , Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013) , Nowy Orlean, Luizjana, s. 1486–1502, ISBN 978-1-611972-51-1 .
• Mycielski, J. (1955), "Sur le coloriage des graphes", Colloq. Matematyka , 3 (2): 161–162, doi : 10,4064/cm-3-2-161-162 .
• Nilli, A. (2000), „Wykresy bez trójkątów z dużymi liczbami chromatycznymi”, Matematyka dyskretna , 211 (1–3): 261–262, doi : 10.1016/S0012-365X (99) 00109-0 .
• Shearer, JB (1983), „Uwaga na temat liczby niezależności grafów bez trójkątów”, Discrete Mathematics , 46 (1): 83–87, doi : 10,1016 / 0012-365X (83) 90273-X .
• Thomassen, C. (1994), „Twierdzenie o 3 kolorach Grötzscha”, Journal of Combinatorial Theory , Seria B , 62 (2): 268–279, doi : 10.1006 / jctb.1994.1069 .

Linki zewnętrzne

• „Klasa wykresu: bez trójkątów” , System informacji o klasach wykresów i ich inkluzjach