Poznane już Twierdzenie Forda-Fulkersona orzeka, że w sieciach wartość maksymalnego przepływu i przepustowości minimalnego przekroju są sobie równe. Przyjrzymy się teraz dokładniej związkom tego typu, tzn. takim, w których maksymalizacja pewnej wartości jest równoważna minimalizacji innej. Związki takie są użyteczne, gdyż poszukiwanie jednej można zastąpić poszukiwaniem drugiej, co w praktyce może okazać się łatwiejsze. Zaczniemy od bliższego przyjrzenia się skojarzeniom i bardzo mocno z nimi związanym pokryciom grafu: wierzchołkowym i krawędziowym.
Skojarzenie w grafie G=(V,E) to taki zbiór krawędzi M⊆E, w którym żadne dwie nie są incydentne z tym samym wierzchołkiem.
Skojarzenie maksymalne to skojarzenie o maksymalnej liczności.
Liczność maksymalnego skojarzenia w grafie G oznaczamy przez ν(G).
Skojarzenie doskonałe to skojarzenie wykorzystujące wszystkie wierzchołki grafu.
Pokrycie krawędziowe grafu G=(V,E) to taki podzbiór jego krawędzi E0⊆E, że każdy wierzchołek grafu G jest incydentny z co najmniej jedną krawędzią w E0.
Minimalne pokrycie krawędziowe to pokrycie krawędziowe wykorzystujące najmniejszą możliwą liczbę krawędzi. Liczbę krawędzi w minimalnym pokryciu krawędziowym oznaczamy przez ρ(G).
Pokrycie wierzchołkowe grafu G=(V,E) to taki podzbiór jego wierzchołków V0⊆V, że każda krawędź grafu G jest incydentna z co najmniej jednym wierzchołkiem z V0.
Minimalne pokrycie wierzchołkowe to najmniej liczne pokrycie wierzchołkowe. Liczność minimalnego pokrycia wierzchołkowego grafu G oznaczamy przez τ(G).
Zbiór niezależny w grafie G=(V,E) to taki zbiór wierzchołków I, że graf indukowany G|I jest antykliką, tzn. E(G|I)=∅. Innymi słowy, zbiór niezależny składa się z wierzchołków niepołączonych.
Maksymalny zbiór niezależny to najbardziej liczny zbiór niezależny. Jego moc oznaczamy przez α(G).
Twierdzenie 1.1 [T. Gallai 1959]
Dla grafu G zachodzą:
Dowód <
Dla dowodu punktu pierwszego niech Cv będzie minimalnym pokryciem wierzchołkowym. Gdyby w zbiorze V(G)−Cv istniały wierzchołki u,v połączone krawędzią, to taka krawędź uv nie byłaby incydentna z żadnym wierzchołkiem z Cv, co przeczy temu, że Cv jest pokryciem. A zatem zbiór V(G)−Cv jest niezależny i można go więc oszacować
|V(G)|−τ(G)=|V(G)−Cv|≤α(G),
co daje |V(G)|≤τ(G)+α(G). Z drugiej strony, jeśli I jest maksymalnym zbiorem niezależnym, to V(G)−I jest pokryciem wierzchołkowym. Tak więc
τ(G)≤|V(G)−I|=|V(G)|−α(G)
i w konsekwencji τ(G)+α(G)≤|V(G)|.
Dla dowodu punktu drugiego niech Ce będzie minimalnym pokryciem krawędziowym grafu G. Bez trudu można zauważyć, że pokrycie takie jest lasem (bo z każdego cyklu można usunąć jakąś krawędź i reszta dalej będzie pokryciem), w którym każda składowa spójna jest gwiazdą (bo z każdej ścieżki o długości co najmniej 3 można usunąć jedną wewnętrzna krawędź). Niech więc Ce składa się z s gwiazd. Wybierzmy z każdej gwiazdy po jednej krawędzi, konstruując w ten sposób jakieś skojarzenie M o mocy s. Każda gwiazda ma o jeden więcej wierzchołków niż krawędzi, tak więc |V(G)|=|Ce|+s, skąd natychmiast
|V(G)|=|Ce|+s=|Ce|+|M|≤ρ(G)+ν(G).
Z drugiej strony, jeśli M′ jest maksymalnym skojarzeniem w G, czyli |M′|=ν(G), to zbiór I′=V(G)−V(M) jest zbiorem niezależnym i ma |V(G)|−2⋅ν(G) elementów. Ponieważ G nie ma punktów izolowanych, to każdy wierzchołek z I′ jest połączony krawędzią z jakimś wierzchołkiem ze zbioru V(M). Dla każdego wierzchołka v∈I′ wybierzmy krawędź incydentną z v. Tak powstały zbiór krawędzi w sumie z M tworzy pokrycie krawędziowe C′e grafu G. W C′e jest ν(G) krawędzi ze skojarzenia M′ oraz |V(G)|−2⋅ν(G) krawędzi incydentnych z elementami I′. A zatem
ν(G)+(|V(G)|−2⋅ν(G))=|C′e|≥ρ(G),
i w konsekwencji ρ(G)+ν(G)≤|V(G)|.
Twierdzenie 1.2
Jesli G jest grafem prostym, to:
Dowód
Dla dowodu pierwszej równoważności zauważmy, jak w dowodzie Twierdzenia 1.1, że minimalne pokrycie C o ρ(G) krawędziach składa się z gwiazd. W każdej gwieździe krawędzi jest o jedną mniej niż wierzchołków. Tak więc, na mocy Twierdzenia 1.1, liczba gwiazd jest równa |V(G)|−ρ(G)=ν(G). Wybierając teraz z każdej gwiazdy po jednej krawędzi dostaniemy ich dostatecznie dużo, by stanowiły skojarzenie maksymalne.
Dla dowodu implikacji odwrotnej znów skorzystamy z faktu, że pokrycie C, jako minimalne w sensie inkluzji, składa się z gwiazd. A zatem, gdy C zawiera jakieś maksymalne skojarzenie M′, to i M′ musi zawierać po dokładnie jednej krawędzi z każdej gwiazdy pokrycia C. Istotnie, gdyby jakaś gwiazda nie zawierała krawędzi z M′, to M′ nie było by maksymalne, a gdyby w gwieździe były dwie krawędzie z M′, to M′ nie byłoby skojarzeniem. Tak więc C składa się z ν(G) gwiazd. Ponieważ w każdej gwieździe krawędzi jest o jedną mniej niż wierzchołków, to pokrycie C ma |V(G)|−ν(G)=ρ(G) krawędzi, co kończy dowód.
Analogiczny dowód punktu drugiego pozostawiamy jako ćwiczenie 4.
Warunek Hall'a na istnienie pełnych skojarzeń w grafach dwudzielnych G=(V1∪V2,E) wykorzystuje funkcję Φ:P(V1)⟶P(V2) zdefiniowaną przez Φ(A)={v2∈V2: v1v2∈E \rm i v1∈V1}. Innymi słowy, Φ(A) to zbiór tych wierzchołków z V2, które sąsiadują z przynajmniej jednym wierzchołkiem w A⊆V1. Przypomnijmy poznane już (z dowodem) Twierdzenie Hall'a.
Twierdzenie 1.3 [o skojarzeniach w grafie dwudzielnym P. Hall 1935]
Niech G=(V1∪V2,E) będzie grafem dwudzielnym. Wówczas pełne skojarzenie V1 z V2 istnieje wtedy i tylko wtedy, gdy |A|≤|Φ(A)| dla każdego podzbioru A zbioru V1.
Twierdzenie 1.4 [D. Konig 1931]
W grafie dwudzielnym G liczba wierzchołków w minimalnym pokryciu wierzchołkowym jest równa maksymalnej liczności skojarzenia, tzn.
τ(G)=ν(G).
Dowód
Niech M będzie maksymalnym skojarzeniem, a Cv minimalnym pokryciem wierzchołkowym w grafie G. Każda krawędź w M jest incydentna z jakimś wierzchołkiem pokrycia Cv. Ponadto, każdy wierzchołek z Cv jest incydentny z co najwyżej jedną krawędzią skojarzenia M. Tak więc
ν(G)≤τ(G).
Dla dowodu odwrotnej nierówności zauważmy najpierw, że jeśli A⊆V1∩Cv, to |A|≤|Φ(A)−Cv|. Istotnie, inaczej zbiór (Cv∪Φ(A))−A byłby pokryciem wierzchołkowym o mocy istotnie mniejszej niż minimalne pokrycie Cv. Tak więc Twierdzenie (Hall'a) 1.3 daje nam jakieś skojarzenie M1 zbioru V1∩Cv z V2−Cv. Analogicznie otrzymamy jakieś skojarzenie M2 zbioru V2∩Cv z V1−Cv. W efekcie zbiór M′=M1∪M2 jest skojarzenie, wykorzystującym wszystkie punkty z Cv. Ponadto, każda krawędź z M′ jest incydentna z co najwyżej jednym wierzchołkiem z Cv, co daje już pożądaną nierówność odwrotną
τ(G)=|Cv|=|M′|≤ν(G).
Twierdzenie 1.5 [F.G.Frobenius, 1917]
Graf dwudzielny G=(V1∪V2,E) ma skojarzenie doskonałe wtedy i tylko wtedy, gdy |V1|=|V2| oraz |A|≤|Φ(A)| dla każdego podzbioru A zbioru V1.
Dowód
Załóżmy najpierw, że M jest jakimś skojarzeniem doskonałym w grafie G. Oczywiście wierzchołki ze zbioru A⊆V1 mogą być kojarzone tylko z własnymi sąsiadami, czyli z wierzchołkami ze zbioru Φ(A). A zatem |A|≤|Φ(A)|. Ponadto z faktu, że każdy element z V1 jest skojarzony przez M z dokładnie jednym elementem z V2, przy czym każdy wierzchołek z V2 jest wykorzystany, otrzymujemy |V1|=|V2|.
Dla dowodu implikacji odwrotnej ustalmy jakieś minimalne pokrycie wierzchołkowe Cv grafu G, czyli pokrycie o τ(G) wierzchołkach. W grafie dwudzielnym zbiór V1 jest też pokryciem, więc |Cv|≤|V1|. Z drugiej strony, aby krawędzie incydentne z wierzchołkami z V1−Cv były pokryte przez Cv, zbiór Φ(V1−Cv) musi zawierać się w Cv. Tak więc
|V1−Cv|≤|Φ(V1−Cv)|≤|V2∩Cv|,
co implikuje, że
|V1|=|V1−Cv|+|V1∩Cv|≤|V2∩Cv|+|V1∩Cv|=|Cv|.
Twierdzenie Koniga 1.4 daje teraz
ν(G)=τ(G)=|Cv|=|V1|=|V2|,
czyli dostarcza maksymalnego skojarzenia o |V1|=|V2| krawędziach. Skojarzenie takie musi być wobec tego doskonałe.
Pokazaliśmy jak wyprowadzić Twierdzienie Frobeniusa z Twierdzenia K{o}niga, a wcześniej jak otrzymać Twierdzenie K{o}niga z Twierdzenia Hall'a. Na zakończenie wykładu, wyprowadzimy Twierdzenie Hall'a z Twierdzenia Frobeniusa, pokazując tym samym, że w istocie te trzy twierdzenia mówią to samo.
Dowód [Inny dowód Twierdzenia Hall'a 1.3]
Niech G=(V1∪V2,E) będzie grafem dwudzielnym. Załóżmy najpierw, że w G istnieje pełne skojarzenie V1 z V2. W takim razie dla dowolnego zbioru A⊆V1, zbiór Φ(A) zawiera |A| różnych elementów skojarzonych odpowiednio z elementami z A. A zatem |A|≤|Φ(A)|.
Ciekawsza jest oczywiście implikacja odwrotna. Załóżmy więc, że
W szczególności |V1|≤|Φ(V1)|≤|V2|.
Jeśli |V1|=|V2|, to Twierdzenie Frobenius'a daje natychmiast jakieś skojarzenie doskonałe, a zatem pełne. Niech więc |V1|<|V2|. Do grafu G dodajmy zbiór nowych wierzchołków W o mocy |V2|−|V1| łącząc je ze wszystkimi elementami V2. Otrzymamy w ten sposób nowy graf dwudzielny G′=(V′1∪V′2,E′), gdzie V′1=V1∪W oraz V′2=V2. Jeśli A′⊆V′1 zawiera jakiś wierzchołek z nowo dodanego W, to Φ(A′)=V2=V′2, co pociąga za sobą, że |A′|≤|Φ(A′)|. Jeżeli zaś A′ jest rozłączny z W, czyli A′⊆V1, to Φ(A′)=Φ(A′)∩Φ(V1), a więc na mocy (∗) dostajemy, że |A′|≤|Φ(A′)|.
To, wraz z oczywistą równością |V′1|=|V′2| czyni graf G′ podatnym na Twierdzenie Frobenius'a. Tym samym graf G′ ma jakieś skojarzenie doskonałe M′. Usuwając teraz ze skojarzenia M′ krawędzie incydentne z wierzchołkami w W dostajemy pożądane pełne skojarzenie V1 z V2 w grafie G.