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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
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 to taki zbiór krawędzi , 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 to taki podzbiór jego krawędzi , że każdy wierzchołek grafu jest incydentny z co najmniej jedną krawędzią w .


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 .

Pokrycie wierzchołkowe grafu to taki podzbiór jego wierzchołków , że każda krawędź grafu jest incydentna z co najmniej jednym wierzchołkiem z .

Minimalne pokrycie wierzchołkowe to najmniej liczne pokrycie wierzchołkowe. Liczność minimalnego pokrycia wierzchołkowego grafu oznaczamy przez .

Zbiór niezależny w grafie to taki zbiór wierzchołków , że graf indukowany jest antykliką, tzn. . 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ą:

  • ,
  • , o ile graf nie posiada punktów izolowanych.

Dowód

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



co daje Z drugiej strony, jeśli jest maksymalnym zbiorem niezależnym, to jest pokryciem wierzchołkowym. Tak więc



i w konsekwencji

Dla dowodu punktu drugiego niech 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 można usunąć jedną wewnętrzna krawędź). Niech więc składa się z gwiazd. Wybierzmy z każdej gwiazdy po jednej krawędzi, konstruując w ten sposób jakieś skojarzenie o mocy . Każda gwiazda ma o jeden więcej wierzchołków niż krawędzi, tak więc , skąd natychmiast



Z drugiej strony, jeśli jest maksymalnym skojarzeniem w , czyli , to zbiór jest zbiorem niezależnym i ma elementów. Ponieważ nie ma punktów izolowanych, to każdy wierzchołek z jest połączony krawędzią z jakimś wierzchołkiem ze zbioru . Dla każdego wierzchołka wybierzmy krawędź incydentną z . Tak powstały zbiór krawędzi w sumie z tworzy pokrycie krawędziowe grafu . W jest krawędzi ze skojarzenia oraz krawędzi incydentnych z elementami . A zatem



i w konsekwencji .

End of proof.gif

Twierdzenie 1.2

Jesli jest grafem prostym, to:

  • minimalne w sensie inkluzji pokrycie krawędziowe grafu jest najmniej liczne wtedy i tylko wtedy, gdy zawiera jakieś maksymalne skojarzenie w ,
  • maksymalne w sensie inkluzji skojarzenie grafu jest najbardziej liczne wtedy i tylko wtedy, gdy 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 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 . 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 , jako minimalne w sensie inkluzji, składa się z gwiazd. A zatem, gdy zawiera jakieś maksymalne skojarzenie , to i musi zawierać po dokładnie jednej krawędzi z każdej gwiazdy pokrycia . Istotnie, gdyby jakaś gwiazda nie zawierała krawędzi z , to nie było by maksymalne, a gdyby w gwieździe były dwie krawędzie z , to nie byłoby skojarzeniem. Tak więc składa się z gwiazd. Ponieważ w każdej gwieździe krawędzi jest o jedną mniej niż wierzchołków, to pokrycie ma krawędzi, co kończy dowód.

Analogiczny dowód punktu drugiego pozostawiamy jako ćwiczenie 4.

End of proof.gif

Warunek Hall'a na istnienie pełnych skojarzeń w grafach dwudzielnych wykorzystuje funkcję zdefiniowaną przez . Innymi słowy, to zbiór tych wierzchołków z , które sąsiadują z przynajmniej jednym wierzchołkiem w . Przypomnijmy poznane już (z dowodem) Twierdzenie Hall'a.

Twierdzenie 1.3 [o skojarzeniach w grafie dwudzielnym P. Hall 1935]

Niech będzie grafem dwudzielnym. Wówczas pełne skojarzenie z istnieje wtedy i tylko wtedy, gdy dla każdego podzbioru zbioru .

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 będzie maksymalnym skojarzeniem, a minimalnym pokryciem wierzchołkowym w grafie . Każda krawędź w jest incydentna z jakimś wierzchołkiem pokrycia . Ponadto, każdy wierzchołek z jest incydentny z co najwyżej jedną krawędzią skojarzenia . Tak więc



Dla dowodu odwrotnej nierówności zauważmy najpierw, że jeśli , to . Istotnie, inaczej zbiór byłby pokryciem wierzchołkowym o mocy istotnie mniejszej niż minimalne pokrycie . Tak więc Twierdzenie (Hall'a) 1.3 daje nam jakieś skojarzenie zbioru z . Analogicznie otrzymamy jakieś skojarzenie zbioru z . W efekcie zbiór jest skojarzenie, wykorzystującym wszystkie punkty z . Ponadto, każda krawędź z jest incydentna z co najwyżej jednym wierzchołkiem z , co daje już pożądaną nierówność odwrotną



End of proof.gif

Twierdzenie 1.5 [F.G.Frobenius, 1917]

Graf dwudzielny ma skojarzenie doskonałe wtedy i tylko wtedy, gdy oraz dla każdego podzbioru zbioru .

Dowód

Załóżmy najpierw, że jest jakimś skojarzeniem doskonałym w grafie . Oczywiście wierzchołki ze zbioru mogą być kojarzone tylko z własnymi sąsiadami, czyli z wierzchołkami ze zbioru . A zatem . Ponadto z faktu, że każdy element z jest skojarzony przez z dokładnie jednym elementem z , przy czym każdy wierzchołek z jest wykorzystany, otrzymujemy .

Dla dowodu implikacji odwrotnej ustalmy jakieś minimalne pokrycie wierzchołkowe grafu , czyli pokrycie o wierzchołkach. W grafie dwudzielnym zbiór jest też pokryciem, więc . Z drugiej strony, aby krawędzie incydentne z wierzchołkami z były pokryte przez , zbiór musi zawierać się w . Tak więc



co implikuje, że



Twierdzenie Koniga 1.4 daje teraz



czyli dostarcza maksymalnego skojarzenia o krawędziach. Skojarzenie takie musi być wobec tego doskonałe.

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 będzie grafem dwudzielnym. Załóżmy najpierw, że w istnieje pełne skojarzenie z . W takim razie dla dowolnego zbioru , zbiór zawiera różnych elementów skojarzonych odpowiednio z elementami z . A zatem .

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

dla każdego.

W szczególności .

Jeśli , to Twierdzenie Frobenius'a daje natychmiast jakieś skojarzenie doskonałe, a zatem pełne. Niech więc . Do grafu dodajmy zbiór nowych wierzchołków o mocy łącząc je ze wszystkimi elementami . Otrzymamy w ten sposób nowy graf dwudzielny , gdzie oraz . Jeśli zawiera jakiś wierzchołek z nowo dodanego , to , co pociąga za sobą, że . Jeżeli zaś jest rozłączny z , czyli , to , a więc na mocy dostajemy, że .

To, wraz z oczywistą równością czyni graf podatnym na Twierdzenie Frobenius'a. Tym samym graf ma jakieś skojarzenie doskonałe . Usuwając teraz ze skojarzenia krawędzie incydentne z wierzchołkami w dostajemy pożądane pełne skojarzenie z w grafie .

End of proof.gif