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 \( \mathbf{G}=( V,E ) \) to taki zbiór krawędzi \( M\subseteq 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 \( \mathbf{G} \) oznaczamy przez \( \nu( \mathbf{G} ) \).
Skojarzenie doskonałe to skojarzenie wykorzystujące wszystkie wierzchołki grafu.
Pokrycie krawędziowe grafu \( \mathbf{G}=( V,E ) \) to taki podzbiór jego krawędzi \( E_0\subseteq E \), że każdy wierzchołek grafu \( \mathbf{G} \) jest incydentny z co najmniej jedną krawędzią w \( E_0 \).
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 \( \rho( \mathbf{G} ) \).
Pokrycie wierzchołkowe grafu \( \mathbf{G}=( V,E ) \) to taki podzbiór jego wierzchołków \( V_0\subseteq V \), że każda krawędź grafu \( \mathbf{G} \) jest incydentna z co najmniej jednym wierzchołkiem z \( V_0 \).
Minimalne pokrycie wierzchołkowe to najmniej liczne pokrycie wierzchołkowe. Liczność minimalnego pokrycia wierzchołkowego grafu \( \mathbf{G} \) oznaczamy przez \( \tau( \mathbf{G} ) \).
Zbiór niezależny w grafie \( \mathbf{G}=( V,E ) \) to taki zbiór wierzchołków \( I \), że graf indukowany \( \mathbf{G}|_I \) jest antykliką, tzn. \( {\sf E}\!(G|_I)=\emptyset \). 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 \( \alpha( \mathbf{G} ) \).
Twierdzenie 1.1 [T. Gallai 1959]
Dla grafu \( \mathbf{G} \) zachodzą:
Dowód <
Dla dowodu punktu pierwszego niech \( C_v \) będzie minimalnym pokryciem wierzchołkowym. Gdyby w zbiorze \( {\sf V}\!(\mathbf{G})- C_v \) istniały wierzchołki \( u,v \) połączone krawędzią, to taka krawędź \( uv \) nie byłaby incydentna z żadnym wierzchołkiem z \( C_v \), co przeczy temu, że \( C_v \) jest pokryciem. A zatem zbiór \( {\sf V}\!(\mathbf{G})- C_v \) jest niezależny i można go więc oszacować
\( \vert {\sf V}\!(\mathbf{G}) \vert-\tau( \mathbf{G} )=\vert {\sf V}\!(\mathbf{G})- C_v \vert\leq \alpha( \mathbf{G} ), \)
co daje \( \vert {\sf V}\!(\mathbf{G}) \vert\leq\tau( \mathbf{G} )+ \alpha( \mathbf{G} ). \) Z drugiej strony, jeśli \( I \) jest maksymalnym zbiorem niezależnym, to \( {\sf V}\!(\mathbf{G}) - I \) jest pokryciem wierzchołkowym. Tak więc
\( \tau( \mathbf{G} )\leq\vert {\sf V}\!(\mathbf{G}) - I \vert=\vert {\sf V}\!(\mathbf{G}) \vert-\alpha( \mathbf{G} ) \)
i w konsekwencji \( \tau( \mathbf{G} )+ \alpha( \mathbf{G} )\leq\vert {\sf V}\!(\mathbf{G}) \vert. \)
Dla dowodu punktu drugiego niech \( C_e \) będzie minimalnym pokryciem krawędziowym grafu \( \mathbf{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 \( C_e \) 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 \( \vert {\sf V}\!(\mathbf{G}) \vert=\vert C_e \vert+s \), skąd natychmiast
\( \vert {\sf V}\!(\mathbf{G}) \vert=\vert C_e \vert+s=\vert C_e \vert+\vert M \vert\leq\rho( \mathbf{G} )+\nu( \mathbf{G} ). \)
Z drugiej strony, jeśli \( M' \) jest maksymalnym skojarzeniem w \( \mathbf{G} \), czyli \( \vert M' \vert=\nu( \mathbf{G} ) \), to zbiór \( I'={\sf V}\!(\mathbf{G})- {\sf V}\!(M) \) jest zbiorem niezależnym i ma \( \vert {\sf V}\!(\mathbf{G}) \vert-2\cdot\nu( \mathbf{G} ) \) elementów. Ponieważ \( \mathbf{G} \) nie ma punktów izolowanych, to każdy wierzchołek z \( I' \) jest połączony krawędzią z jakimś wierzchołkiem ze zbioru \( {\sf V}\!(M) \). Dla każdego wierzchołka \( v\in 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 \( \mathbf{G} \). W \( C_e' \) jest \( \nu( \mathbf{G} ) \) krawędzi ze skojarzenia \( M' \) oraz \( \vert {\sf V}\!(\mathbf{G}) \vert-2\cdot\nu( \mathbf{G} ) \) krawędzi incydentnych z elementami \( I' \). A zatem
\( \nu( \mathbf{G} )+( \vert {\sf V}\!(\mathbf{G}) \vert-2\cdot\nu( \mathbf{G} ) ) =\vert C_e' \vert\geq\rho( \mathbf{G} ), \)
i w konsekwencji \( \rho( \mathbf{G} )+\nu( \mathbf{G} )\leq \vert {\sf V}\!(\mathbf{G}) \vert \).
Twierdzenie 1.2
Jesli \( \mathbf{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 \( \rho( \mathbf{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 \( \vert {\sf V}\!(\mathbf{G}) \vert-\rho( \mathbf{G} )=\nu( \mathbf{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 \( \nu( \mathbf{G} ) \) gwiazd. Ponieważ w każdej gwieździe krawędzi jest o jedną mniej niż wierzchołków, to pokrycie \( C \) ma \( \vert {\sf V}\!(\mathbf{G}) \vert-\nu( \mathbf{G} )=\rho( \mathbf{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 \( \mathbf{G}=( V_1\cup V_2,E ) \) wykorzystuje funkcję \( \Phi: \mathscr{P}\!( V_1 ) \longrightarrow \mathscr{P}\!( V_2 ) \) zdefiniowaną przez \( \Phi\!(A)=\lbrace v_2\in V_2:\ v_1 v_2\in E \mbox{ \rm i } v_1\in V_1 \rbrace \). Innymi słowy, \( \Phi\!(A) \) to zbiór tych wierzchołków z \( V_2 \), które sąsiadują z przynajmniej jednym wierzchołkiem w \( A\subseteq V_1 \). Przypomnijmy poznane już (z dowodem) Twierdzenie Hall'a.
Twierdzenie 1.3 [o skojarzeniach w grafie dwudzielnym P. Hall 1935]
Niech \( \mathbf{G}=( V_1\cup V_2, E ) \) będzie grafem dwudzielnym. Wówczas pełne skojarzenie \( V_1 \) z \( V_2 \) istnieje wtedy i tylko wtedy, gdy \( \vert A \vert \leq\vert \Phi\!(A) \vert \) dla każdego podzbioru \( A \) zbioru \( V_1 \).
Twierdzenie 1.4 [D. Konig 1931]
W grafie dwudzielnym \( \mathbf{G} \) liczba wierzchołków w minimalnym pokryciu wierzchołkowym jest równa maksymalnej liczności skojarzenia, tzn.
\( \tau( \mathbf{G} )=\nu( \mathbf{G} ). \)
Dowód
Niech \( M \) będzie maksymalnym skojarzeniem, a \( C_v \) minimalnym pokryciem wierzchołkowym w grafie \( \mathbf{G} \). Każda krawędź w \( M \) jest incydentna z jakimś wierzchołkiem pokrycia \( C_v \). Ponadto, każdy wierzchołek z \( C_v \) jest incydentny z co najwyżej jedną krawędzią skojarzenia \( M \). Tak więc
\( \nu( \mathbf{G} )\leq \tau( \mathbf{G} ). \)
Dla dowodu odwrotnej nierówności zauważmy najpierw, że jeśli \( A\subseteq V_1\cap C_v \), to \( \vert A \vert \leq\vert \Phi\!(A)- C_v \vert \). Istotnie, inaczej zbiór \( (C_v\cup\Phi\!(A))- A \) byłby pokryciem wierzchołkowym o mocy istotnie mniejszej niż minimalne pokrycie \( C_v \). Tak więc Twierdzenie (Hall'a) 1.3 daje nam jakieś skojarzenie \( M_1 \) zbioru \( V_1\cap C_v \) z \( V_2- C_v \). Analogicznie otrzymamy jakieś skojarzenie \( M_2 \) zbioru \( V_2\cap C_v \) z \( V_1- C_v \). W efekcie zbiór \( M'=M_1\cup M_2 \) jest skojarzenie, wykorzystującym wszystkie punkty z \( C_v \). Ponadto, każda krawędź z \( M' \) jest incydentna z co najwyżej jednym wierzchołkiem z \( C_v \), co daje już pożądaną nierówność odwrotną
\( \tau( \mathbf{G} ) = \vert C_v \vert = \vert M' \vert \leq \nu( \mathbf{G} ). \)
Twierdzenie 1.5 [F.G.Frobenius, 1917]
Graf dwudzielny \( \mathbf{G}=( V_1\cup V_2, E ) \) ma skojarzenie doskonałe wtedy i tylko wtedy, gdy \( \vert V_1 \vert=\vert V_2 \vert \) oraz \( \vert A \vert \leq\vert \Phi\!(A) \vert \) dla każdego podzbioru \( A \) zbioru \( V_1 \).
Dowód
Załóżmy najpierw, że \( M \) jest jakimś skojarzeniem doskonałym w grafie \( \mathbf{G} \). Oczywiście wierzchołki ze zbioru \( A\subseteq V_1 \) mogą być kojarzone tylko z własnymi sąsiadami, czyli z wierzchołkami ze zbioru \( \Phi\!(A) \). A zatem \( \vert A \vert \leq\vert \Phi\!(A) \vert \). Ponadto z faktu, że każdy element z \( V_1 \) jest skojarzony przez \( M \) z dokładnie jednym elementem z \( V_2 \), przy czym każdy wierzchołek z \( V_2 \) jest wykorzystany, otrzymujemy \( \vert V_1 \vert=\vert V_2 \vert \).
Dla dowodu implikacji odwrotnej ustalmy jakieś minimalne pokrycie wierzchołkowe \( C_v \) grafu \( \mathbf{G} \), czyli pokrycie o \( \tau( \mathbf{G} ) \) wierzchołkach. W grafie dwudzielnym zbiór \( V_1 \) jest też pokryciem, więc \( \vert C_v \vert\leq\vert V_1 \vert \). Z drugiej strony, aby krawędzie incydentne z wierzchołkami z \( V_1- C_v \) były pokryte przez \( C_v \), zbiór \( \Phi\!(V_1- C_v) \) musi zawierać się w \( C_v \). Tak więc
\( \vert V_1- C_v \vert\leq\vert \Phi\!(V_1- C_v) \vert\leq\vert V_2\cap C_v \vert, \)
co implikuje, że
\( \vert V_1 \vert=\vert V_1- C_v \vert+\vert V_1\cap C_v \vert\leq\vert V_2\cap C_v \vert+\vert V_1\cap C_v \vert=\vert C_v \vert. \)
Twierdzenie Koniga 1.4 daje teraz
\( \nu( \mathbf{G} )=\tau( \mathbf{G} )=\vert C_v \vert=\vert V_1 \vert=\vert V_2 \vert, \)
czyli dostarcza maksymalnego skojarzenia o \( \vert V_1 \vert=\vert V_2 \vert \) 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 \( \mathbf{G}=( V_1\cup V_2, E ) \) będzie grafem dwudzielnym. Załóżmy najpierw, że w \( \mathbf{G} \) istnieje pełne skojarzenie \( V_1 \) z \( V_2 \). W takim razie dla dowolnego zbioru \( A\subseteq V_1 \), zbiór \( \Phi\!(A) \) zawiera \( \vert A \vert \) różnych elementów skojarzonych odpowiednio z elementami z \( A \). A zatem \( \vert A \vert \leq\vert \Phi\!(A) \vert \).
Ciekawsza jest oczywiście implikacja odwrotna. Załóżmy więc, że
W szczególności \( \vert V_1 \vert\leq\vert \Phi\!(V_1) \vert\leq \vert V_2 \vert \).
Jeśli \( \vert V_1 \vert=\vert V_2 \vert \), to Twierdzenie Frobenius'a daje natychmiast jakieś skojarzenie doskonałe, a zatem pełne. Niech więc \( \vert V_1 \vert < \vert V_2 \vert \). Do grafu \( \mathbf{G} \) dodajmy zbiór nowych wierzchołków \( W \) o mocy \( \vert V_2 \vert-\vert V_1 \vert \) łącząc je ze wszystkimi elementami \( V_2 \). Otrzymamy w ten sposób nowy graf dwudzielny \( \mathbf{G}'=( V_1'\cup V_2',E' ) \), gdzie \( V_1'=V_1\cup W \) oraz \( V_2'=V_2 \). Jeśli \( A'\subseteq V_1' \) zawiera jakiś wierzchołek z nowo dodanego \( W \), to \( \Phi\!(A')=V_2=V_2' \), co pociąga za sobą, że \( \vert A' \vert\leq\vert \Phi\!(A') \vert \). Jeżeli zaś \( A' \) jest rozłączny z \( W \), czyli \( A'\subseteq V_1 \), to \( \Phi\!(A')=\Phi\!(A')\cap \Phi\!(V_1) \), a więc na mocy \( (*) \) dostajemy, że \( \vert A' \vert \leq\vert \Phi\!(A') \vert \).
To, wraz z oczywistą równością \( \vert V_1' \vert=\vert V_2' \vert \) czyni graf \( \mathbf{G}' \) podatnym na Twierdzenie Frobenius'a. Tym samym graf \( \mathbf{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 \( V_1 \) z \( V_2 \) w grafie \( G \).