Matematyka dyskretna 2/Wykład 1: Zagadnienia Mini-Maksowe w grafach

Skojarzenie niemaksymalne (a),maksymalne ale niedoskonałe (b) i skojarzenie doskonałe (c)

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} =\left(V,E\right)$ 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 \left(\mathbf {G} \right)$.

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

Pokrycie krawędziowe grafu $\mathbf {G} =\left(V,E\right)$ 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}$.

[[File:Minmax edge covering.svg|250x100px|thumb|left|Krawędzie nie pokrywające grafu (a), nieminimalne pokrycie krawędziowe (b) oraz minimalne pokrycie krawędziowe (c)

Zbiór wierzchołków nie pokrywający grafu (a), nieminimalne pokrycie wierzchołkowe (b) oraz minimalne pokrycie wierzchołkowe (c)

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)

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 {G} \right)$.

Pokrycie wierzchołkowe grafu $\mathbf {G} =\left(V,E\right)$ 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 \left(\mathbf {G} \right)$.

Zbiór niezależny w grafie $\mathbf {G} =\left(V,E\right)$ to taki zbiór wierzchołków $I$, że graf indukowany $\mathbf {G} |_{I}$ jest antykliką, tzn. ${\mathsf {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 {G} \right)$.

Twierdzenie 1.1 [T. Gallai 1959]

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

• $\alpha \left(\mathbf {G} \right)+\tau \left(\mathbf {G} \right)=\left\vert {\mathsf {V}}\!\left(\mathbf {G} \right)\right\vert$,

• $\nu \left(\mathbf {G} \right)+\rho \left(\mathbf {G} \right)=\left\vert {\mathsf {V}}\!\left(\mathbf {G} \right)\right\vert$, o ile graf $\mathbf {G}$ nie posiada punktów izolowanych.

Dowód

Dla dowodu punktu pierwszego niech $C_{v}$ będzie minimalnym pokryciem wierzchołkowym. Gdyby w zbiorze ${\mathsf {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 ${\mathsf {V}}\!\left(\mathbf {G} \right)-C_{v}$ jest niezależny i można go więc oszacować

$\left\vert {\mathsf {V}}\!\left(\mathbf {G} \right)\right\vert -\tau \left(\mathbf {G} \right)=\left\vert {\mathsf {V}}\!\left(\mathbf {G} \right)-C_{v}\right\vert \leq \alpha \left(\mathbf {G} \right),$

co daje $\left\vert {\mathsf {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 ${\mathsf {V}}\!\left(\mathbf {G} \right)-I$ jest pokryciem wierzchołkowym. Tak więc

$\tau \left(\mathbf {G} \right)\leq \left\vert {\mathsf {V}}\!\left(\mathbf {G} \right)-I\right\vert =\left\vert {\mathsf {V}}\!\left(\mathbf {G} \right)\right\vert -\alpha \left(\mathbf {G} \right)$

i w konsekwencji $\tau \left(\mathbf {G} \right)+\alpha \left(\mathbf {G} \right)\leq \left\vert {\mathsf {V}}\!\left(\mathbf {G} \right)\right\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 $\left\vert {\mathsf {V}}\!\left(\mathbf {G} \right)\right\vert =\left\vert C_{e}\right\vert +s$, skąd natychmiast

$\left\vert {\mathsf {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'$ jest maksymalnym skojarzeniem w $\mathbf {G}$, czyli $\left\vert M'\right\vert =\nu \left(\mathbf {G} \right)$, to zbiór $I'={\mathsf {V}}\!\left(\mathbf {G} \right)-{\mathsf {V}}\!\left(M\right)$ jest zbiorem niezależnym i ma $\left\vert {\mathsf {V}}\!\left(\mathbf {G} \right)\right\vert -2\cdot \nu \left(\mathbf {G} \right)$ 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 ${\mathsf {V}}\!\left(M\right)$. 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 \left(\mathbf {G} \right)$ krawędzi ze skojarzenia $M'$ oraz $\left\vert {\mathsf {V}}\!\left(\mathbf {G} \right)\right\vert -2\cdot \nu \left(\mathbf {G} \right)$ krawędzi incydentnych z elementami $I'$. A zatem

$\nu \left(\mathbf {G} \right)+\left(\left\vert {\mathsf {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 $\rho \left(\mathbf {G} \right)+\nu \left(\mathbf {G} \right)\leq \left\vert {\mathsf {V}}\!\left(\mathbf {G} \right)\right\vert$.

Twierdzenie 1.2

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

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

Dowód

Dla dowodu pierwszej równoważności zauważmy, jak w dowodzie Twierdzenia 1.1, że minimalne pokrycie $C$ o $\rho \left(\mathbf {G} \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 1.1, liczba gwiazd jest równa $\left\vert {\mathsf {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'$, 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 \left(\mathbf {G} \right)$ gwiazd. Ponieważ w każdej gwieździe krawędzi jest o jedną mniej niż wierzchołków, to pokrycie $C$ ma $\left\vert {\mathsf {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 4.

Warunek Hall'a na istnienie pełnych skojarzeń w grafach dwudzielnych $\mathbf {G} =\left(V_{1}\cup V_{2},E\right)$ wykorzystuje funkcję $\Phi :{\mathcal {P}}\!\left(V_{1}\right)\longrightarrow {\mathcal {P}}\!\left(V_{2}\right)$ zdefiniowaną przez $\Phi \!\left(A\right)=\left\lbrace v_{2}\in V_{2}:\ v_{1}v_{2}\in E{\mbox{ i }}v_{1}\in V_{1}\right\rbrace$. Innymi słowy, $\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 1.3 [o skojarzeniach w grafie dwudzielnym P. Hall 1935]

Niech $\mathbf {G} =\left(V_{1}\cup V_{2},E\right)$ będzie grafem dwudzielnym. Wówczas pełne skojarzenie $V_{1}$ z $V_{2}$ istnieje wtedy i tylko wtedy, gdy $\left\vert A\right\vert \leq \left\vert \Phi \!\left(A\right)\right\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 \left(\mathbf {G} \right)=\nu \left(\mathbf {G} \right).$

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 \left(\mathbf {G} \right)\leq \tau \left(\mathbf {G} \right).$

Dla dowodu odwrotnej nierówności zauważmy najpierw, że jeśli $A\subseteq V_{1}\cap C_{v}$, to $\left\vert A\right\vert \leq \left\vert \Phi \!\left(A\right)-C_{v}\right\vert$. Istotnie, inaczej zbiór $(C_{v}\cup \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) 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 \left(\mathbf {G} \right)=\left\vert C_{v}\right\vert =\left\vert M'\right\vert \leq \nu \left(\mathbf {G} \right).$

Twierdzenie 1.5 [F.G.Frobenius, 1917]

Graf dwudzielny $\mathbf {G} =\left(V_{1}\cup V_{2},E\right)$ ma skojarzenie doskonałe wtedy i tylko wtedy, gdy $\left\vert V_{1}\right\vert =\left\vert V_{2}\right\vert$ oraz $\left\vert A\right\vert \leq \left\vert \Phi \!\left(A\right)\right\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 \!\left(A\right)$. A zatem $\left\vert A\right\vert \leq \left\vert \Phi \!\left(A\right)\right\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 $\left\vert V_{1}\right\vert =\left\vert V_{2}\right\vert$.

Dla dowodu implikacji odwrotnej ustalmy jakieś minimalne pokrycie wierzchołkowe $C_{v}$ grafu $\mathbf {G}$, czyli pokrycie o $\tau \left(\mathbf {G} \right)$ wierzchołkach. W grafie dwudzielnym zbiór $V_{1}$ jest też pokryciem, więc $\left\vert C_{v}\right\vert \leq \left\vert V_{1}\right\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 \!\left(V_{1}-C_{v}\right)$ musi zawierać się w $C_{v}$. Tak więc

$\left\vert V_{1}-C_{v}\right\vert \leq \left\vert \Phi \!\left(V_{1}-C_{v}\right)\right\vert \leq \left\vert V_{2}\cap C_{v}\right\vert ,$

co implikuje, że

$\left\vert V_{1}\right\vert =\left\vert V_{1}-C_{v}\right\vert +\left\vert V_{1}\cap C_{v}\right\vert \leq \left\vert V_{2}\cap C_{v}\right\vert +\left\vert V_{1}\cap C_{v}\right\vert =\left\vert C_{v}\right\vert .$

Twierdzenie Koniga 1.4 daje teraz

$\nu \left(\mathbf {G} \right)=\tau \left(\mathbf {G} \right)=\left\vert C_{v}\right\vert =\left\vert V_{1}\right\vert =\left\vert V_{2}\right\vert ,$

czyli dostarcza maksymalnego skojarzenia o $\left\vert V_{1}\right\vert =\left\vert V_{2}\right\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} =\left(V_{1}\cup V_{2},E\right)$ 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 \!\left(A\right)$ zawiera $\left\vert A\right\vert$ różnych elementów skojarzonych odpowiednio z elementami z $A$. A zatem $\left\vert A\right\vert \leq \left\vert \Phi \!\left(A\right)\right\vert$.

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

$(*)$ $\left\vert A\right\vert \leq \left\vert \Phi \!\left(A\right)\right\vert$ dla każdego$A\subseteq V_{1}$.

W szczególności $\left\vert V_{1}\right\vert \leq \left\vert \Phi \!\left(V_{1}\right)\right\vert \leq \left\vert V_{2}\right\vert$.

Jeśli $\left\vert V_{1}\right\vert =\left\vert V_{2}\right\vert$, to Twierdzenie Frobenius'a daje natychmiast jakieś skojarzenie doskonałe, a zatem pełne. Niech więc $\left\vert V_{1}\right\vert <\left\vert V_{2}\right\vert$. Do grafu $\mathbf {G}$ dodajmy zbiór nowych wierzchołków $W$ o mocy $\left\vert V_{2}\right\vert -\left\vert V_{1}\right\vert$ łącząc je ze wszystkimi elementami $V_{2}$. Otrzymamy w ten sposób nowy graf dwudzielny $\mathbf {G} '=\left(V_{1}'\cup V_{2}',E'\right)$, 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 \!\left(A'\right)=V_{2}=V_{2}'$, co pociąga za sobą, że $\left\vert A'\right\vert \leq \left\vert \Phi \!\left(A'\right)\right\vert$. Jeżeli zaś $A'$ jest rozłączny z $W$, czyli $A'\subseteq V_{1}$, to $\Phi \!\left(A'\right)=\Phi \!\left(A'\right)\cap \Phi \!\left(V_{1}\right)$, a więc na mocy $(*)$ dostajemy, że $\left\vert A'\right\vert \leq \left\vert \Phi \!\left(A'\right)\right\vert$.

To, wraz z oczywistą równością $\left\vert V_{1}'\right\vert =\left\vert V_{2}'\right\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$.