Matematyka dyskretna 2/Wykład 1: 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 $\mathbf{𝐆}=(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{𝐆}$ oznaczamy przez $\nu \left(\mathbf{𝐆}\right)$.

Skojarzenie doskonałe to skojarzenie wykorzystujące wszystkie wierzchołki grafu.

[!h]

{minmax_matching} {Skojarzenie niemaksymalne (a),maksymalne ale niedoskonałe (b) i skojarzenie doskonałe (c) [Rysunek z pliku: minmaxmatching.eps]}

Pokrycie krawędziowe grafu $\mathbf{𝐆}=(V,E)$ to taki podzbiór jego krawędzi $E_0\subseteq E$, że każdy wierzchołek grafu $\mathbf{𝐆}$ 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 \left(\mathbf{𝐆}\right)$.

[!h]

{minmax_edge_covering} {Krawędzie nie pokrywające grafu (a), nieminimalne pokrycie krawędziowe (b) oraz minimalne pokrycie krawędziowe (c) [Rysunek z pliku: minmaxedgecovering.eps]}

Pokrycie wierzchołkowe grafu $\mathbf{𝐆}=(V,E)$ to taki podzbiór jego wierzchołków $V_0\subseteq V$, że każda krawędź grafu $\mathbf{𝐆}$ 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{𝐆}$ oznaczamy przez $\tau \left(\mathbf{𝐆}\right)$.

[!h]

{minmax_vertex_covering} {Zbiór wierzchołków nie pokrywający grafu (a), nieminimalne pokrycie wierzchołkowe (b) oraz minimalne pokrycie wierzchołkowe (c) [Rysunek z pliku: minmaxvertexcovering.eps]}

Zbiór niezależny w grafie $\mathbf{𝐆}=(V,E)$ to taki zbiór wierzchołków $I$, że graf indukowany $\mathbf{𝐆}{|}_I$ jest antykliką, tzn. Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf E}\!\left(G|_I\right)=\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 \left(\mathbf{𝐆}\right)$.

[!h]

{minmax_independent} {Zbiór wierzchołków nie będący niezależnym (a), niemaksymalny zbiór niezależny (b) oraz maksymalny zbiór niezależny (c) [Rysunek z pliku: minmaxindependent.eps]}

Twierdzenie T. Gallai 1959

Dla grafu $\mathbf{𝐆}$ zachodzą:

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \alpha\left( \mathbf{G} \right)+\tau\left( \mathbf{G} \right)=\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert} ,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \nu\left( \mathbf{G} \right)+\rho\left( \mathbf{G} \right)=\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert} ,

o ile graf $\mathbf{𝐆}$ nie posiada punktów izolowanych.

Dowód

Dla dowodu punktu pierwszego niech $C_v$ będzie minimalnym pokryciem wierzchołkowym. Gdyby w zbiorze Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf V}\!\left(\mathbf{G}\right)- 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf V}\!\left(\mathbf{G}\right)- C_v} jest niezależny i można go więc oszacować

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-\tau\left( \mathbf{G} \right)=\left\vert {\sf V}\!\left(\mathbf{G}\right)- C_v \right\vert\leq \alpha\left( \mathbf{G} \right), }

co daje Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert\leq\tau\left( \mathbf{G} \right)+ \alpha\left( \mathbf{G} \right). } Z drugiej strony, jeśli $I$ jest maksymalnym zbiorem niezależnym, to Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf V}\!\left(\mathbf{G}\right) - I} jest pokryciem wierzchołkowym. Tak więc

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \tau\left( \mathbf{G} \right)\leq\left\vert {\sf V}\!\left(\mathbf{G}\right) - I \right\vert=\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-\alpha\left( \mathbf{G} \right) }

i w konsekwencji Parser nie mógł rozpoznać (błąd składni): {\displaystyle \tau\left( \mathbf{G} \right)+ \alpha\left( \mathbf{G} \right)\leq\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert. }

Dla dowodu punktu drugiego niech $C_e$ będzie minimalnym pokryciem krawędziowym grafu $\mathbf{𝐆}$. 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert=\left\vert C_e \right\vert+s} , skąd natychmiast

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert=\left\vert C_e \right\vert+s=\left\vert C_e \right\vert+\left\vert M \right\vert\leq\rho\left( \mathbf{G} \right)+\nu\left( \mathbf{G} \right). }

Z drugiej strony, jeśli $M^{\prime }$ jest maksymalnym skojarzeniem w $\mathbf{𝐆}$, czyli $\left|M^{\prime }\right|=\nu \left(\mathbf{𝐆}\right)$, to zbiór Parser nie mógł rozpoznać (błąd składni): {\displaystyle I'={\sf V}\!\left(\mathbf{G}\right)- {\sf V}\!\left(M\right)} jest zbiorem niezależnym i ma Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-2\cdot\nu\left( \mathbf{G} \right)} elementów. Ponieważ $\mathbf{𝐆}$ nie ma punktów izolowanych, to każdy wierzchołek z $I^{\prime }$ jest połączony krawędzią z jakimś wierzchołkiem ze zbioru Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf V}\!\left(M\right)} . Dla każdego wierzchołka $v\in I^{\prime }$ wybierzmy krawędź incydentną z $v$. Tak powstały zbiór krawędzi w sumie z $M$ tworzy pokrycie krawędziowe ${C_e}^{\prime }$ grafu $\mathbf{𝐆}$. W ${C_e}^{\prime }$ jest $\nu \left(\mathbf{𝐆}\right)$ krawędzi ze skojarzenia $M^{\prime }$ oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-2\cdot\nu\left( \mathbf{G} \right)} krawędzi incydentnych z elementami $I^{\prime }$. A zatem

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \nu\left( \mathbf{G} \right)+\left( \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-2\cdot\nu\left( \mathbf{G} \right) \right) =\left\vert C_e' \right\vert\geq\rho\left( \mathbf{G} \right), }

i w konsekwencji Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rho\left( \mathbf{G} \right)+\nu\left( \mathbf{G} \right)\leq \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert} .

Twierdzenie

Jesli $\mathbf{𝐆}$ jest grafem prostym, to:

• minimalne w sensie inkluzji pokrycie krawędziowe $C$ grafu $\mathbf{𝐆}$

jest najmniej liczne wtedy i tylko wtedy, gdy $C$ zawiera jakieś maksymalne skojarzenie w $\mathbf{𝐆}$,

• maksymalne w sensie inkluzji skojarzenie $M$ grafu $\mathbf{𝐆}$

jest najbardziej liczne wtedy i tylko wtedy, gdy $M$ jest zawarte w jakimś minimalnym pokryciu krawędziowym $\mathbf{𝐆}$.

Dowód

Dla dowodu pierwszej równoważności zauważmy, jak w dowodzie Twierdzenia Uzupelnic th Gallai|, że minimalne pokrycie $C$ o $\rho \left(\mathbf{𝐆}\right)$ 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 Uzupelnic th Gallai|, liczba gwiazd jest równa Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-\rho\left( \mathbf{G} \right)=\nu\left( \mathbf{G} \right)} . 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^{\prime }$, to i $M^{\prime }$ 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^{\prime }$, to $M^{\prime }$ nie było by maksymalne, a gdyby w gwieździe były dwie krawędzie z $M^{\prime }$, to $M^{\prime }$ nie byłoby skojarzeniem. Tak więc $C$ składa się z $\nu \left(\mathbf{𝐆}\right)$ gwiazd. Ponieważ w każdej gwieździe krawędzi jest o jedną mniej niż wierzchołków, to pokrycie $C$ ma Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-\nu\left( \mathbf{G} \right)=\rho\left( \mathbf{G} \right)} krawędzi, co kończy dowód.

Analogiczny dowód punktu drugiego pozostawiamy jako ćwiczenie [ex][ex covering = matching].

Warunek Hall'a na istnienie pełnych skojarzeń w grafach dwudzielnych $\mathbf{𝐆}=(V_1\cup V_2,E)$ wykorzystuje funkcję Parser nie mógł rozpoznać (błąd składni): {\displaystyle \Phi: \mathscr{P}\!\left( V_1 \right) \longrightarrow \mathscr{P}\!\left( V_2 \right)} zdefiniowaną przez Parser nie mógł rozpoznać (błąd składni): {\displaystyle \Phi\!\left(A\right)=\left\lbrace v_2\in V_2:\ v_1 v_2\in E \mbox{ \rm i } v_1\in V_1 \right\rbrace} . Innymi słowy, $\mathrm{\Phi }\left(A\right)$ 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 o skojarzeniach w grafie dwudzielnym, P. Hall 1935

Niech $\mathbf{𝐆}=(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 $\left|A\right|\le \left|\mathrm{\Phi }\left(A\right)\right|$ dla każdego podzbioru $A$ zbioru $V_1$.

Twierdzenie D. K{o}nig 1931

W grafie dwudzielnym $\mathbf{𝐆}$ liczba wierzchołków w minimalnym pokryciu wierzchołkowym jest równa maksymalnej liczności skojarzenia, tzn.

$\tau \left(\mathbf{𝐆}\right)=\nu \left(\mathbf{𝐆}\right).$

Dowód

Niech $M$ będzie maksymalnym skojarzeniem, a $C_v$ minimalnym pokryciem wierzchołkowym w grafie $\mathbf{𝐆}$. 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 \left(\mathbf{𝐆}\right)\le \tau \left(\mathbf{𝐆}\right).$

Dla dowodu odwrotnej nierówności zauważmy najpierw, że jeśli $A\subseteq V_1\cap C_v$, to $\left|A\right|\le |\mathrm{\Phi }\left(A\right)-C_v|$. Istotnie, inaczej zbiór $(C_v\cup \mathrm{\Phi }\left(A\right))-A$ byłby pokryciem wierzchołkowym o mocy istotnie mniejszej niż minimalne pokrycie $C_v$. Tak więc Twierdzenie (Hall'a) Uzupelnic th Hall 2| 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^{\prime }=M_1\cup M_2$ jest skojarzenie, wykorzystującym wszystkie punkty z $C_v$. Ponadto, każda krawędź z $M^{\prime }$ jest incydentna z co najwyżej jednym wierzchołkiem z $C_v$, co daje już pożądaną nierówność odwrotną

$\tau \left(\mathbf{𝐆}\right)=\left|C_v\right|=\left|M^{\prime }\right|\le \nu \left(\mathbf{𝐆}\right).$

Twierdzenie F.G.Frobenius, 1917

Graf dwudzielny $\mathbf{𝐆}=(V_1\cup V_2,E)$ ma skojarzenie doskonałe wtedy i tylko wtedy, gdy $\left|V_1\right|=\left|V_2\right|$ oraz $\left|A\right|\le \left|\mathrm{\Phi }\left(A\right)\right|$ dla każdego podzbioru $A$ zbioru $V_1$.

Dowód

Załóżmy najpierw, że $M$ jest jakimś skojarzeniem doskonałym w grafie $\mathbf{𝐆}$. 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 $\mathrm{\Phi }\left(A\right)$. A zatem $\left|A\right|\le \left|\mathrm{\Phi }\left(A\right)\right|$. 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 $\left|V_1\right|=\left|V_2\right|$.

Dla dowodu implikacji odwrotnej ustalmy jakieś minimalne pokrycie wierzchołkowe $C_v$ grafu $\mathbf{𝐆}$, czyli pokrycie o $\tau \left(\mathbf{𝐆}\right)$ wierzchołkach. W grafie dwudzielnym zbiór $V_1$ jest też pokryciem, więc $\left|C_v\right|\le \left|V_1\right|$. Z drugiej strony, aby krawędzie incydentne z wierzchołkami z $V_1-C_v$ były pokryte przez $C_v$, zbiór $\mathrm{\Phi }(V_1-C_v)$ musi zawierać się w $C_v$. Tak więc

$|V_1-C_v|\le \left|\mathrm{\Phi }(V_1-C_v)\right|\le |V_2\cap C_v|,$

co implikuje, że

$\left|V_1\right|=|V_1-C_v|+|V_1\cap C_v|\le |V_2\cap C_v|+|V_1\cap C_v|=\left|C_v\right|.$

Twierdzenie K{o}niga Uzupelnic th Konig| daje teraz

$\nu \left(\mathbf{𝐆}\right)=\tau \left(\mathbf{𝐆}\right)=\left|C_v\right|=\left|V_1\right|=\left|V_2\right|,$

czyli dostarcza maksymalnego skojarzenia o $\left|V_1\right|=\left|V_2\right|$ 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 Uzupelnic th Hall 2|.

Niech $\mathbf{𝐆}=(V_1\cup V_2,E)$ będzie grafem dwudzielnym. Załóżmy najpierw, że w $\mathbf{𝐆}$ istnieje pełne skojarzenie $V_1$ z $V_2$. W takim razie dla dowolnego zbioru $A\subseteq V_1$, zbiór $\mathrm{\Phi }\left(A\right)$ zawiera $\left|A\right|$ różnych elementów skojarzonych odpowiednio z elementami z $A$. A zatem $\left|A\right|\le \left|\mathrm{\Phi }\left(A\right)\right|$.

Ciekawsza jest oczywiście implikacja odwrotna. Załóżmy więc, że

$(*)$

$\left|A\right|\le \left|\mathrm{\Phi }\left(A\right)\right|$ dla każdego$A\subseteq V_1$.

W szczególności $\left|V_1\right|\le \left|\mathrm{\Phi }\left(V_1\right)\right|\le \left|V_2\right|$.

Jeśli $\left|V_1\right|=\left|V_2\right|$, to Twierdzenie Frobenius'a daje natychmiast jakieś skojarzenie doskonałe, a zatem pełne. Niech więc $\left|V_1\right|<\left|V_2\right|$. Do grafu $\mathbf{𝐆}$ dodajmy zbiór nowych wierzchołków $W$ o mocy $\left|V_2\right|-\left|V_1\right|$ łącząc je ze wszystkimi elementami $V_2$. Otrzymamy w ten sposób nowy graf dwudzielny ${\mathbf{𝐆}}^{\prime }=({V_1}^{\prime }\cup {V_2}^{\prime },E^{\prime })$, gdzie ${V_1}^{\prime }=V_1\cup W$ oraz ${V_2}^{\prime }=V_2$. Jeśli $A^{\prime }\subseteq {V_1}^{\prime }$ zawiera jakiś wierzchołek z nowo dodanego $W$, to $\mathrm{\Phi }\left(A^{\prime }\right)=V_2={V_2}^{\prime }$, co pociąga za sobą, że $\left|A^{\prime }\right|\le \left|\mathrm{\Phi }\left(A^{\prime }\right)\right|$. Jeżeli zaś $A^{\prime }$ jest rozłączny z $W$, czyli $A^{\prime }\subseteq V_1$, to $\mathrm{\Phi }\left(A^{\prime }\right)=\mathrm{\Phi }\left(A^{\prime }\right)\cap \mathrm{\Phi }\left(V_1\right)$, a więc na mocy $(*)$ dostajemy, że $\left|A^{\prime }\right|\le \left|\mathrm{\Phi }\left(A^{\prime }\right)\right|$.

To, wraz z oczywistą równością $\left|{V_1}^{\prime }\right|=\left|{V_2}^{\prime }\right|$ czyni graf ${\mathbf{𝐆}}^{\prime }$ podatnym na Twierdzenie Frobenius'a. Tym samym graf ${\mathbf{𝐆}}^{\prime }$ ma jakieś skojarzenie doskonałe $M^{\prime }$. Usuwając teraz ze skojarzenia $M^{\prime }$ krawędzie incydentne z wierzchołkami w $W$ dostajemy pożądane pełne skojarzenie $V_1$ z $V_2$ w grafie $G$.