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 $𝐆 = (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 $𝐆$ oznaczamy przez $ν (𝐆)$ .

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

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

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

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

Twierdzenie 1.1 [T. Gallai 1959]

Dla grafu $𝐆$ zachodzą:

$α (𝐆) + τ (𝐆) = | V (𝐆) |$ ,

$ν (𝐆) + ρ (𝐆) = | V (𝐆) |$ , o ile graf $𝐆$ nie posiada punktów izolowanych.

Dowód

Dla dowodu punktu pierwszego niech $C_{v}$ będzie minimalnym pokryciem wierzchołkowym. Gdyby w zbiorze $V (𝐆) - C_{v}$ istniały wierzchołki $u, v$ połączone krawędzią, to taka krawędź $u v$ nie byłaby incydentna z żadnym wierzchołkiem z $C_{v}$ , co przeczy temu, że $C_{v}$ jest pokryciem. A zatem zbiór $V (𝐆) - C_{v}$ jest niezależny i można go więc oszacować

| V (𝐆) | - τ (𝐆) = | V (𝐆) - C_{v} | \leq α (𝐆)

,

co daje $| V (𝐆) | \leq τ (𝐆) + α (𝐆)$ Z drugiej strony, jeśli $I$ jest maksymalnym zbiorem niezależnym, to $V (𝐆) - I$ jest pokryciem wierzchołkowym. Tak więc

τ (𝐆) \leq | V (𝐆) - I | = | V (𝐆) | - α (𝐆)

i w konsekwencji $τ (𝐆) + α (𝐆) \leq | V (𝐆) |$

Dla dowodu punktu drugiego niech $C_{e}$ będzie minimalnym pokryciem krawędziowym grafu $𝐆$ . 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 $| V (𝐆) | = | C_{e} | + s$ , skąd natychmiast

| V (𝐆) | = | C_{e} | + s = | C_{e} | + | M | \leq ρ (𝐆) + ν (𝐆)

Z drugiej strony, jeśli $M^{'}$ jest maksymalnym skojarzeniem w $𝐆$ , czyli $| M^{'} | = ν (𝐆)$ , to zbiór $I^{'} = V (𝐆) - V (M)$ jest zbiorem niezależnym i ma $| V (𝐆) | - 2 \cdot ν (𝐆)$ elementów. Ponieważ $𝐆$ 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 $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 $𝐆$ . W ${C_{e}}^{'}$ jest $ν (𝐆)$ krawędzi ze skojarzenia $M^{'}$ oraz $| V (𝐆) | - 2 \cdot ν (𝐆)$ krawędzi incydentnych z elementami $I^{'}$ . A zatem

ν (𝐆) + (| V (𝐆) | - 2 \cdot ν (𝐆)) = | {C_{e}}^{'} | \geq ρ (𝐆)

,

i w konsekwencji $ρ (𝐆) + ν (𝐆) \leq | V (𝐆) |$ .

Twierdzenie 1.2

Jesli $𝐆$ jest grafem prostym, to:

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

Dowód

Dla dowodu pierwszej równoważności zauważmy, jak w dowodzie Twierdzenia 1.1, że minimalne pokrycie $C$ o $ρ (𝐆)$ 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 (𝐆) | - ρ (𝐆) = ν (𝐆)$ . 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 $ν (𝐆)$ gwiazd. Ponieważ w każdej gwieździe krawędzi jest o jedną mniej niż wierzchołków, to pokrycie $C$ ma $| V (𝐆) | - ν (𝐆) = ρ (𝐆)$ 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 $𝐆 = (V_{1} \cup V_{2}, E)$ wykorzystuje funkcję $Φ : 𝒫 (V_{1}) ⟶ 𝒫 (V_{2})$ zdefiniowaną przez $Φ (A) = {v_{2} \in V_{2} : v_{1} v_{2} \in E i v_{1} \in V_{1}}$ . Innymi słowy, $Φ (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 $𝐆 = (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 $| A | \leq | Φ (A) |$ dla każdego podzbioru $A$ zbioru $V_{1}$ .

Twierdzenie 1.4 [D. Konig 1931]

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

τ (𝐆) = ν (𝐆)

Dowód

Niech $M$ będzie maksymalnym skojarzeniem, a $C_{v}$ minimalnym pokryciem wierzchołkowym w grafie $𝐆$ . 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

ν (𝐆) \leq τ (𝐆)

Dla dowodu odwrotnej nierówności zauważmy najpierw, że jeśli $A \subseteq V_{1} \cap C_{v}$ , to $| A | \leq | Φ (A) - C_{v} |$ . Istotnie, inaczej zbiór $(C_{v} \cup Φ (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ą

τ (𝐆) = | C_{v} | = | M^{'} | \leq ν (𝐆)

Twierdzenie 1.5 [F.G.Frobenius, 1917]

Graf dwudzielny $𝐆 = (V_{1} \cup V_{2}, E)$ ma skojarzenie doskonałe wtedy i tylko wtedy, gdy $| V_{1} | = | V_{2} |$ oraz $| A | \leq | Φ (A) |$ dla każdego podzbioru $A$ zbioru $V_{1}$ .

Dowód

Załóżmy najpierw, że $M$ jest jakimś skojarzeniem doskonałym w grafie $𝐆$ . 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 $Φ (A)$ . A zatem $| A | \leq | Φ (A) |$ . 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 $| V_{1} | = | V_{2} |$ .

Dla dowodu implikacji odwrotnej ustalmy jakieś minimalne pokrycie wierzchołkowe $C_{v}$ grafu $𝐆$ , czyli pokrycie o $τ (𝐆)$ wierzchołkach. W grafie dwudzielnym zbiór $V_{1}$ jest też pokryciem, więc $| C_{v} | \leq | V_{1} |$ . Z drugiej strony, aby krawędzie incydentne z wierzchołkami z $V_{1} - C_{v}$ były pokryte przez $C_{v}$ , zbiór $Φ (V_{1} - C_{v})$ musi zawierać się w $C_{v}$ . Tak więc

| V_{1} - C_{v} | \leq | Φ (V_{1} - C_{v}) | \leq | V_{2} \cap C_{v} |

,

co implikuje, że

| V_{1} | = | V_{1} - C_{v} | + | V_{1} \cap C_{v} | \leq | V_{2} \cap C_{v} | + | V_{1} \cap C_{v} | = | C_{v} |

Twierdzenie Koniga 1.4 daje teraz

ν (𝐆) = τ (𝐆) = | C_{v} | = | V_{1} | = | V_{2} |,

czyli dostarcza maksymalnego skojarzenia o $| V_{1} | = | V_{2} |$ 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 $𝐆 = (V_{1} \cup V_{2}, E)$ będzie grafem dwudzielnym. Załóżmy najpierw, że w $𝐆$ istnieje pełne skojarzenie $V_{1}$ z $V_{2}$ . W takim razie dla dowolnego zbioru $A \subseteq V_{1}$ , zbiór $Φ (A)$ zawiera $| A |$ różnych elementów skojarzonych odpowiednio z elementami z $A$ . A zatem $| A | \leq | Φ (A) |$ .

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

$(*)$ $| A | \leq | Φ (A) |$ dla każdego $A \subseteq V_{1}$ .

W szczególności $| V_{1} | \leq | Φ (V_{1}) | \leq | V_{2} |$ .

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

To, wraz z oczywistą równością $| {V_{1}}^{'} | = | {V_{2}}^{'} |$ czyni graf $𝐆^{'}$ podatnym na Twierdzenie Frobenius'a. Tym samym graf $𝐆^{'}$ 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$ .

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

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia