Twierdzenie Tutte'a

W matematycznej dyscyplinie teorii grafów twierdzenie Tutte'a , nazwane na cześć Williama Thomasa Tutte'a , jest charakterystyką skończonych grafów z doskonałymi dopasowaniami . Jest to uogólnienie twierdzenia Halla o małżeństwie z grafów dwudzielnych na dowolne. ^{[ wymagane wyjaśnienie ]} Jest to szczególny przypadek wzoru Tutte-Berge .

Intuicja

Naszym celem jest scharakteryzowanie wszystkich wykresów, które nie mają idealnego dopasowania. Zacznijmy od najbardziej oczywistego przypadku grafu bez idealnego dopasowania: grafu z nieparzystą liczbą wierzchołków. W takim grafie każde dopasowanie pozostawia co najmniej jeden niedopasowany wierzchołek, więc nie może być doskonały.

Nieco bardziej ogólnym przypadkiem jest graf rozłączony, w którym jeden lub więcej elementów ma nieparzystą liczbę wierzchołków (nawet jeśli całkowita liczba wierzchołków jest parzysta). Takie składowe nazwijmy nieparzystymi . W dowolnym dopasowaniu każdy wierzchołek można dopasować tylko do wierzchołków w tym samym komponencie. Dlatego każde dopasowanie pozostawia co najmniej jeden niedopasowany wierzchołek w każdym nieparzystym komponencie, więc nie może być idealne.

Następnie rozważmy graf G z wierzchołkiem u takim, że jeśli usuniemy z G wierzchołek u i przylegające do niego krawędzie, pozostały graf (oznaczony $G - u$ ) ma dwa lub więcej nieparzystych składników. Jak powyżej, każde dopasowanie pozostawia, w każdym nieparzystym komponencie, co najmniej jeden wierzchołek, który nie jest dopasowany do innych wierzchołków w tym samym komponencie. Taki wierzchołek można dopasować tylko do u . Ale ponieważ istnieją dwa lub więcej niedopasowanych wierzchołków i tylko jeden z nich może być dopasowany do u , co najmniej jeden inny wierzchołek pozostaje niedopasowany, więc dopasowanie nie jest idealne.

Na koniec rozważmy graf G ze zbiorem wierzchołków $U$ taki, że jeśli usuniemy z G wierzchołki w $U$ i wszystkie przylegające do nich krawędzie, pozostały graf (oznaczony jako $G - U$ ) ma więcej niż $| U |$ dziwne komponenty. Jak wyjaśniono powyżej, każde dopasowanie pozostawia co najmniej jeden niedopasowany wierzchołek w każdym nieparzystym komponencie, a te można dopasować tylko do wierzchołków U $-$ ale nie ma wystarczającej liczby wierzchołków na $U$ dla wszystkich tych niedopasowanych wierzchołków, więc dopasowanie nie jest idealne.

Doszliśmy do warunku koniecznego : jeśli G ma doskonałe dopasowanie, to dla każdego podzbioru wierzchołków $U$ w G graf $G - U$ ma co najwyżej $| U |$ dziwne komponenty.

Twierdzenie Tutte'a mówi, że warunek ten jest zarówno konieczny, jak i wystarczający do istnienia idealnego dopasowania.

Twierdzenie Tutte'a

Wykres $G (V, E)$ $= - U$ ma idealne dopasowanie wtedy i tylko wtedy , gdy dla każdego podzbioru $U$ z $V$ podgraf G ma co najwyżej $| U |$ nieparzyste komponenty ( połączone komponenty mające nieparzystą liczbę wierzchołków ).

Dowód

Najpierw piszemy warunek:

{\ Displaystyle (*) \ qquad \ for all U \ subseteq V \ quad nieparzysty (GU) \ równoważnik | U |}

gdzie $nieparzystych$ składowych podgrafu indukowanych przez $}$ .

Konieczność (∗): Rozważmy graf $G$ , z doskonałym dopasowaniem. Niech $U$ będzie dowolnym podzbiorem $V$ . Usuń $U.$ _ Niech $C$ będzie dowolnym nieparzystym składnikiem w $G - U$ . Ponieważ $G$ ma doskonałe dopasowanie, co najmniej jeden wierzchołek w $C$ musi być dopasowany do wierzchołka w $U$ . Stąd każdy nieparzysty składnik ma co najmniej jeden wierzchołek dopasowany do wierzchołka w $U$ . Ponieważ każdy wierzchołek w $U$ może być w tej relacji z co najwyżej jednym połączonym komponentem (ponieważ jest dopasowany co najwyżej raz w idealnym dopasowaniu), $nieparzysty (G - U) \leq | U |$ .

Wystarczalność (∗): Niech $G$ będzie dowolnym wykresem bez idealnego dopasowania. Znajdziemy gwałciciela Tutte , czyli podzbiór $S$ od $V$ taki, że $| S | < nieparzysty (G - S)$ . Możemy założyć, że $G$ jest krawędziowo-maksymalne, tj. $G + e$ ma idealne dopasowanie dla każdej krawędzi $e,$ której nie ma już w $G.$ Rzeczywiście, jeśli znajdziemy gwałciciela Tutte $S$ na grafie maksymalnym krawędzi $G$ , to $S$ jest również gwałcicielem Tutte w każdym rozpinającym się podgrafie $G$ , ponieważ każdy nieparzysty składnik $G - S$ zostanie podzielony na prawdopodobnie więcej składników, z których przynajmniej jeden będzie ponownie nieparzysty.

Definiujemy $S$ jako zbiór wierzchołków o stopniu $| V | - 1$ . Najpierw rozważymy przypadek, w którym wszystkie składowe $G - S$ są grafami pełnymi. Wtedy $S$ musi być gwałcicielem Tutte, ponieważ jeśli $nieparzyste (G - S) \leq | S |$ , wtedy moglibyśmy znaleźć idealne dopasowanie, dopasowując jeden wierzchołek z każdego nieparzystego składnika do wierzchołka z $S$ i łącząc w pary wszystkie inne wierzchołki (to zadziała, chyba że $| V |$ jest nieparzyste, ale wtedy $\emptyset$ jest gwałcicielem Tutte).

Załóżmy teraz, że $K$ jest składową $G - S$ oraz $x, y \in K$ są wierzchołkami takimi, że $xy \notin E$ . Niech $x, a, b \in K$ będą pierwszymi wierzchołkami najkrótszej $x, y$ -ścieżki w $K$ . Zapewnia to, że $xa, ab \in E$ i $xb \notin E$ . Od $a \notin S$ , istnieje wierzchołek $c$ taki, że $ac \notin E$ . Na podstawie maksymalności krawędzi $G$ , definiujemy $M 1$ jako idealne dopasowanie w $G + xb$ i $M 2$ jako idealne dopasowanie w $G + ac$ . Zauważ, że na pewno $xb \in M 1$ i $ac \in M 2$ .

Niech $P$ będzie maksymalną ścieżką w $G$ , która zaczyna się od $c$ z krawędzią z $M 1$ i której krawędzie zmieniają się między $M 1$ i $M 2$ . Jak może $P$ ? Dopóki nie dojdziemy do „specjalnego” wierzchołka, takiego jak $x, a$ lub $b$ , zawsze możemy kontynuować: $c$ jest $M 2$ -dopasowane przez $ca$ , więc pierwsza krawędź $P$ nie jest w $M 2$ , zatem drugi wierzchołek jest $M 2$ dopasowany inną krawędzią i kontynuujemy w ten sposób.

Niech $v$ oznacza ostatni wierzchołek $P$ . Jeśli ostatnia krawędź $P$ jest w $M 1$ , to $v$ musi być $a$ , ponieważ w przeciwnym razie moglibyśmy kontynuować z krawędzią z $M 2$ (nawet dochodząc do $x$ lub $b$ ). W tym przypadku definiujemy $C := P + ac$ . Jeśli ostatnia krawędź $P$ jest w $M 2$ , to z pewnością $v \in {x, b$ } z analogicznego powodu i definiujemy $C := P + va + ac$ .

Teraz $C$ jest cyklem w $G + ac$ o parzystej długości z każdą inną krawędzią w $M 2$ . Możemy teraz zdefiniować $M := M 2 Δ C$ (gdzie $Δ$ jest różnicą symetryczną ) i otrzymujemy dopasowanie w $G$ , sprzeczność.

Równoważność ze wzorem Tutte-Berge

Wzór ${\ Displaystyle \ min _ {U \ subseteq V} \ lewo (| U | - \ nazwa operatora {nieparzyste} (GU) + | V | \ prawej) / 2}$ -Berge $U$ rozmiar równy . Równocześnie liczba niedopasowane wierzchołki w maksymalnym dopasowaniu równa się ${\ Displaystyle \ max _ {U \ subseteq V} \ lewo (\ nazwa operatora {nieparzysty} (GU) - | U |\prawo)}$ .

Ten wzór wynika z twierdzenia Tutte'a wraz z obserwacją, że $(k)}}$ dopasowanie rozmiaru $k$ $,$ gdy wykres otrzymane przez dodanie $wierzchołki , z$ $których każdy jest połączony z każdym$ wierzchołkiem mają idealne dopasowanie. Ponieważ dowolny zestaw ${\ displaystyle X}$ co oddziela ${\ Displaystyle G ^ {(k)}}$ na więcej niż ${\ Displaystyle | X |}$ składniki muszą zawierać wszystkie nowe wierzchołki, (*) jest spełnione dla ${\ Displaystyle G ^ {(k)}}$ wtedy i tylko wtedy, gdy ${\ Displaystyle k \ równoważnik \ min _ {U \ subseteq V} \ lewo (| U | - \ operatorname {nieparzysty} (GU) + | V | \ prawo) / 2}$ .

W nieskończonych grafach

W przypadku połączonych nieskończonych grafów, które są lokalnie skończone (każdy wierzchołek ma skończony stopień), obowiązuje uogólnienie warunku Tutte'a: takie grafy mają doskonałe dopasowania wtedy i tylko wtedy, gdy nie ma skończonego podzbioru, którego usunięcie tworzy większą liczbę skończonych nieparzystych składników niż rozmiar podzbioru.

Zobacz też

Linki zewnętrzne

Sunil Chandran, twierdzenie Tutte'a o istnieniu idealnego dopasowania (w YouTube).
Wyprowadź twierdzenie Halla z twierdzenia Tutte'a (w Math StackExchange).

Notatki

Bondy, JA; Murty, USR (1976). Teoria grafów z zastosowaniami . Nowy Jork: amerykański pub Elsevier. Co ISBN 0-444-19451-7 .
Lovász, László ; Plummer, lekarz medycyny (1986). Teoria dopasowania . Amsterdam: Holandia Północna. ISBN 0-444-87916-1 .