Loading [MathJax]/jax/output/HTML-CSS/jax.js

Zagadnienia Mini-Maksowe w grafach

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 ME, 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 E0E, ż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 V0V, ż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ą:

  • α(G)+τ(G)=|V(G)|,
  • ν(G)+ρ(G)=|V(G)|, o ile graf G nie posiada punktów izolowanych.

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 vI wybierzmy krawędź incydentną z v. Tak powstały zbiór krawędzi w sumie z M tworzy pokrycie krawędziowe Ce grafu G. W Ce 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))=|Ce|ρ(G),

i w konsekwencji ρ(G)+ν(G)|V(G)|.

Twierdzenie 1.2

Jesli G jest grafem prostym, to:

  • minimalne w sensie inkluzji pokrycie krawędziowe C grafu G jest najmniej liczne wtedy i tylko wtedy, gdy C zawiera jakieś maksymalne skojarzenie w G,
  • maksymalne w sensie inkluzji skojarzenie M grafu G jest najbardziej liczne wtedy i tylko wtedy, gdy M jest zawarte w jakimś minimalnym pokryciu krawędziowym G.

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=(V1V2,E) wykorzystuje funkcję Φ:P(V1)P(V2) zdefiniowaną przez Φ(A)={v2V2: v1v2E \rm i v1V1}. Innymi słowy, Φ(A) to zbiór tych wierzchołków z V2, które sąsiadują z przynajmniej jednym wierzchołkiem w AV1. Przypomnijmy poznane już (z dowodem) Twierdzenie Hall'a.

Twierdzenie 1.3 [o skojarzeniach w grafie dwudzielnym P. Hall 1935]

Niech G=(V1V2,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 AV1Cv, 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 V1Cv z V2Cv. Analogicznie otrzymamy jakieś skojarzenie M2 zbioru V2Cv z V1Cv. W efekcie zbiór M=M1M2 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=(V1V2,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 AV1 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 V1Cv były pokryte przez Cv, zbiór Φ(V1Cv) musi zawierać się w Cv. Tak więc

|V1Cv||Φ(V1Cv)||V2Cv|,

co implikuje, że

|V1|=|V1Cv|+|V1Cv||V2Cv|+|V1Cv|=|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=(V1V2,E) będzie grafem dwudzielnym. Załóżmy najpierw, że w G istnieje pełne skojarzenie V1 z V2. W takim razie dla dowolnego zbioru AV1, 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

() |A||Φ(A)| dla każdegoAV1.

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=(V1V2,E), gdzie V1=V1W oraz V2=V2. Jeśli AV1 zawiera jakiś wierzchołek z nowo dodanego W, to Φ(A)=V2=V2, co pociąga za sobą, że |A||Φ(A)|. Jeżeli zaś A jest rozłączny z W, czyli AV1, to Φ(A)=Φ(A)Φ(V1), a więc na mocy () dostajemy, że |A||Φ(A)|.

To, wraz z oczywistą równością |V1|=|V2| 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.