Twierdzenie Petersena

Idealne dopasowanie (czerwone krawędzie) na wykresie Petersena . Ponieważ graf Petersena jest sześcienny i bezmostkowy , spełnia warunki twierdzenia Petersena.

Sześcienny (ale nie bezmostkowy) wykres bez idealnego dopasowania, pokazujący, że warunku bezmostkowego w twierdzeniu Petersena nie można pominąć

W matematycznej dyscyplinie teorii grafów twierdzenie Petersena , nazwane na cześć Juliusa Petersena , jest jednym z najwcześniejszych wyników w teorii grafów i można je sformułować w następujący sposób:

Twierdzenie Petersena. Każdy graf sześcienny bez mostków zawiera idealne dopasowanie .

Innymi słowy, jeśli graf ma dokładnie trzy krawędzie w każdym wierzchołku i każda krawędź należy do cyklu, to ma zbiór krawędzi, które stykają się z każdym wierzchołkiem dokładnie raz.

Dowód

Pokazujemy, że dla każdego sześciennego, bezmostkowego grafu G = ( V , E ) mamy to, że dla każdego zbioru U ⊆ V liczba spójnych składowych grafu indukowanego przez V − U o nieparzystej liczbie wierzchołków jest co najwyżej licznością u . Następnie według twierdzenia Tutte G zawiera idealne dopasowanie.

Niech G _i będzie składową o nieparzystej liczbie wierzchołków w grafie indukowanym przez zbiór wierzchołków V − U . Niech V _i oznacza wierzchołki G _i i niech m _i oznacza liczbę krawędzi G z jednym wierzchołkiem w V _i i jednym wierzchołkiem w U . Za pomocą prostego argumentu podwójnego liczenia mamy to

${\ Displaystyle \ suma \ nolimits _ {v \ w V_ {i}} \ stopień _ {G} (v) = 2 | E_ {i} | + m_ {i},}$

gdzie E _i jest zbiorem krawędzi G _i z obydwoma wierzchołkami w V _i . Od

${\ Displaystyle \ suma \ nolimits _ {v \ w V_ {i}} \ deg _ {G} (v) = 3 | V_ {i} |}$

jest liczbą nieparzystą i 2| ja _{_} | jest liczbą parzystą, to m _i musi być liczbą nieparzystą. Ponadto, ponieważ G jest bezmostkowy, to m _i ≥ 3 .

Niech m będzie liczbą krawędzi w G z jednym wierzchołkiem w U i jednym wierzchołkiem w grafie indukowanym przez V − U . Każda składowa o nieparzystej liczbie wierzchołków ma co najmniej 3 krawędzie do m , a te są unikalne, dlatego liczba takich składowych wynosi co najwyżej m /3 . W najgorszym przypadku każda krawędź z jednym wierzchołkiem w U przyczynia się do m , a zatem m ≤ 3| U | . dostajemy

${\ Displaystyle | U | \ geq {\ Frac {1} {3}} m \ geq |\ {{\ tekst {komponenty o nieparzystej liczbie wierzchołków}} \} |,}$

co pokazuje, że warunek twierdzenia Tutte'a jest spełniony.

Historia

Twierdzenie pochodzi od Juliusa Petersena , duńskiego matematyka. Można to uznać za jeden z pierwszych wyników w teorii grafów . Twierdzenie to pojawia się po raz pierwszy w artykule z 1891 r. „ Die Theorie der regulären graphs ”. Według dzisiejszych standardów dowód twierdzenia Petersena jest skomplikowany. Seria uproszczeń dowodu zakończyła się dowodami Frinka (1926) i Königa (1936) .

We współczesnych podręcznikach twierdzenie Petersena jest omawiane jako zastosowanie twierdzenia Tutte'a .

Aplikacje

• W grafie sześciennym z doskonałym dopasowaniem krawędzie, które nie są idealnie dopasowane, tworzą dwuczynnikowy . Orientując współczynnik 2, krawędzie idealnego dopasowania można rozszerzyć do ścieżek o długości trzy, powiedzmy , biorąc krawędzie skierowane na zewnątrz. To pokazuje, że każdy sześcienny, bezmostkowy graf rozkłada się na rozłączne ścieżki o długości trzech.
• Twierdzenie Petersena można również zastosować do pokazania, że ​​każdy maksymalny graf planarny można rozłożyć na zbiór rozłącznych krawędziowo ścieżek o długości trzech. W tym przypadku graf dualny jest sześcienny i bezmostkowy, więc zgodnie z twierdzeniem Petersena ma dopasowanie, które na oryginalnym wykresie odpowiada parowaniu sąsiednich ścian trójkąta. Każda para trójkątów daje ścieżkę o długości trzy, która obejmuje krawędź łączącą trójkąty razem z dwiema z czterech pozostałych krawędzi trójkąta.
• Stosując twierdzenie Petersena do podwójnego wykresu siatki trójkątów i łącząc pary trójkątów, które nie są dopasowane, można rozłożyć siatkę na cykliczne paski trójkątów . Po kilku dalszych przekształceniach można go przekształcić w pojedynczy pasek, a tym samym daje metodę przekształcania siatki trójkątów w taki sposób, że jej podwójny wykres staje się hamiltonowski .

Rozszerzenia

Liczba doskonałych dopasowań w sześciennych grafach bez mostków

Lovász i Plummer przypuszczali , że liczba doskonałych dopasowań zawartych w grafie sześciennym bez mostków jest wykładnicza względem liczby wierzchołków grafu n . Hipoteza została po raz pierwszy udowodniona dla dwudzielnych , sześciennych, bezmostkowych grafów przez Voorhoeve (1979) , później dla płaskich , sześciennych, bezmostkowych grafów przez Chudnovsky'ego i Seymoura (2012) . Ogólny przypadek został rozstrzygnięty przez Espereta i in. (2011) $co$ wykazano, że każdy sześcienny wykres bez mostków zawiera .

Wersje algorytmiczne

Biedl i in. (2001) omawiają wydajne wersje twierdzenia Petersena. Na podstawie dowodu Frinka uzyskują O ( n log ⁴ n ) do obliczania idealnego dopasowania w grafie sześciennym bez mostków o n wierzchołkach. Jeśli graf jest ponadto płaski, ta sama praca podaje algorytm O ( n ) . Ich O ( n log ⁴ n ) ograniczenie czasowe można poprawić na podstawie kolejnych ulepszeń czasu utrzymywania zestawu mostów na wykresie dynamicznym. Dalsze ulepszenia, skracające czas związany z O ( n log ² n ) lub (z dodatkowymi losowymi strukturami danych ) O ( n log n (log log n ) ³ ) , podali Diks i Stańczyk (2010) .

Wyższy stopień

Jeśli G jest regularnym grafem stopnia d , którego łączność krawędzi wynosi co najmniej d - 1, a G ma parzystą liczbę wierzchołków, to ma idealne dopasowanie. Co więcej, każda krawędź G należy do co najmniej jednego doskonałego dopasowania. Warunek dotyczący liczby wierzchołków można pominąć w tym wyniku, gdy stopień jest nieparzysty, ponieważ w takim przypadku (na mocy lematu o uzgadnianiu ) liczba wierzchołków jest zawsze parzysta.

Notatki

•   Biedl, Teresa C .; Bose, Prosenjit ; Demaine, Erik D .; Lubiw, Anna (2001), „Wydajne algorytmy dla twierdzenia Petersena o dopasowaniu”, Journal of Algorithms , 38 (1): 110–134, doi : 10.1006 / jagm.2000.1132 , MR 1810434
•   Bouchet, Andrzej; Fouquet, Jean-Luc (1983), „Trois types de décompositions d'un graphe en chaines”, w: C. Berge, P. Camion, D. Bresson; Sterboul, F. (red.), Combinatorial Mathematics: Proceedings of the International Colloquium on Graph Theory and Combinatoryics (Marseille-Luminy, 1981) , North-Holland Mathematics Studies (w języku francuskim), tom. 75, Holandia Północna, s. 131–141, doi : 10.1016/S0304-0208(08)73380-2 , MR 0841287
•   Czudnowski, Maria ; Seymour, Paul (2012), „Doskonałe dopasowania w płaskich grafach sześciennych”, Combinatorica , 32 (4): 403–424, doi : 10.1007 / s00493-012-2660-9 , MR 2965284
• Dyks, Krzysztof; Stańczyk, Piotr (2010), "Idealne dopasowanie do bispójnych grafów sześciennych w O( n log ² n ) ", w: van Leeuwen, Jan ; Muscholl, Anka ; Peleg, Dawid ; Pokorny, Jaroslav; Rumpe, Bernhard (red.), SOFSEM 2010: 36th Conference on Current Trends in Theory and Practice of Computer Science, Szpindlerowy Młyn, Czechy, 23–29 stycznia 2010, Proceedings , Lecture Notes in Computer Science, tom. 5901, Springer, s. 321–333, doi : 10.1007/978-3-642-11266-9_27
•   Esperet, Ludwik; Kardoš, František; Król, Andrzej D.; Králʼ, Daniel ; Norine, Serguei (2011), „Wykładniczo wiele doskonałych dopasowań w grafach sześciennych”, Advances in Mathematics , 227 (4): 1646–1664, arXiv : 1012,2878 , doi : 10,1016/j.aim.2011.03.015 , MR 2799808
• Frink, Orrin (1926), „Dowód twierdzenia Petersena”, Annals of Mathematics , druga seria, 27 (4): 491–493, doi : 10,2307/1967699
•   Häggkvist, Roland; Johansson, Robert (2004), „Uwaga na temat rozkładów krawędzi grafów planarnych”, Discrete Mathematics , 283 (1–3): 263–266, doi : 10.1016/j.disc.2003.11.017 , MR 2061501
• König, Dénes (1936), Theorie der endlichen und unendlichen Graphen; kombinatorische Topologie der Streckenkocomplexe.
•    Lovász, László ; Plummer, MD (1986), Matching Theory , Annals of Discrete Mathematics, tom. 29, Holandia Północna, ISBN 0-444-87916-1 , MR 0859549
• Meenakshisundaram, Gopi; Eppstein, David (2004), „Triangulacja jednopasmowa rozmaitości o dowolnej topologii”, Proc. 25 Konferencja Eur. doc. za grafikę komputerową (Eurographics '04) , Forum Grafiki Komputerowej, cz. 23, s. 371–379, arXiv : cs.CG/0405036 , doi : 10.1111/j.1467-8659.2004.00768.x
•   Naddef, D.; Pulleyblank, WR (1981), „Matchings in regular graphs”, Discrete Mathematics , 34 (3): 283–291, doi : 10.1016/0012-365X (81) 90006-6 , MR 0613406 .
• Petersen, Julius (1891), „Die Theorie der regulären graphs”, Acta Mathematica , 15 : 193–220, doi : 10.1007 / BF02392606
•    Thorup, Mikkel (2000), „Niemal optymalna, w pełni dynamiczna łączność grafów”, Proc. 32. Sympozjum ACM na temat teorii informatyki , s. 343–350, doi : 10.1145/335305.335345 , ISBN 1-58113-184-4 , MR 2114549
•   Voorhoeve, Marc (1979), „Dolna granica stałych pewnych (0,1) -macierzy”, Indagationes Mathematicae , 82 (1): 83–86, doi : 10,1016 / 1385-7258 (79) 90012-X , MR 0528221