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

From Studia Informatyczne



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.



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. {\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{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 {\sf V}\!\left(\mathbf{G}\right) \right\vert,
  • \nu\left( \mathbf{G} \right)+\rho\left( \mathbf{G} \right)=\left\vert {\sf 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 {\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 {\sf V}\!\left(\mathbf{G}\right)- C_v jest niezależny i można go więc oszacować


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


\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 \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{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 {\sf V}\!\left(\mathbf{G}\right) \right\vert=\left\vert C_e \right\vert+s, skąd natychmiast


\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' jest maksymalnym skojarzeniem w \mathbf{G}, czyli \left\vert M' \right\vert=\nu\left( \mathbf{G} \right), to zbiór I'={\sf V}\!\left(\mathbf{G}\right)- {\sf V}\!\left(M\right) jest zbiorem niezależnym i ma \left\vert {\sf 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 {\sf 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 {\sf 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 {\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 \rho\left( \mathbf{G} \right)+\nu\left( \mathbf{G} \right)\leq \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert.

image:End_of_proof.gif

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 {\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', 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 {\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 4.

image:End_of_proof.gif

Warunek Hall'a na istnienie pełnych skojarzeń w grafach dwudzielnych \mathbf{G}=\left( V_1\cup V_2,E \right) wykorzystuje funkcję \Phi: \mathscr{P}\!\left( V_1 \right) \longrightarrow \mathscr{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{ \rm 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).


image:End_of_proof.gif

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.

image:End_of_proof.gif

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żdegoA\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.

image:End_of_proof.gif