Matematyka dyskretna 2/Ćwiczenia 1: Zagadnienia Mini-Maksowe w grafach
From Studia Informatyczne
Zagadnienia Mini-Maksowe w grafach
Ćwiczenie 1
Czy graf Petersena przedstawiony na rysunku 1 ma skojarzenie doskonałe? Odpowiedź uzasadnij.
Rozwiązanie
<flash>file=Cw minmax petersen match.swf|width=250|height=150</flash>
Doskonałe skojarzenie w grafie Petersena zostało przedstawione na Rysunku 2.
Ćwiczenie 2
Kostka -wymiarowa
to graf, którego wierzchołki są ciągami
, gdzie
,
a krawędzie łączą te ciągi, które różnią się na jednej tylko pozycji.
W kostce
znajdź
- maksymalne skojarzenie,
- minimalne pokrycie krawędziowe,
- minimalne pokrycie wierzchołkowe,
- maksymalny zbiór niezależny,
i podaj ich liczności.
Wskazówka
Kostka ma skojarzenie doskonałe.
Będzie ono więc też minimalnym pokryciem krawędziowym.
Ponieważ kostka
jest grafem dwudzielnym,
w poszukiwaniu minimalnego pokrycia wierzchołkowego
można użyć Twierdzenie Koniga 1.4.
Rozwiązanie
- Maksymalne skojarzenie:
.
Skojarzenie ciągu
z ciągiem
jest doskonałe i zawiera
krawędzi.
- Minimalne pokrycie krawędziowe:
.
Zdefiniowane wyżej skojarzenie maksymalne jest doskonałe, więc
jest pokryciem krawędziowym.
Na mocy Twierdzenia 1.2 wiemy,
że maksymalne skojarzenie zawiera się w jakimś minimalnym pokryciu krawędziowym.
Pokrycie krawędziowe
jest więc minimalne.
- Minimalne pokrycie wierzchołkowe:
.
Kostka jest grafem dwudzielnym,
więc korzystając z Twierdzenia Koniga 1.4
otrzymujemy, że minimalne pokrycie wierzchołkowe ma

elementów. Pozostaje jedynie wskazać takie pokrycie wierzchołkowe o elementach.
Pokażemy, że zbiór
wszystkich ciągów o nieparzystej liczbie jedynek
jest takim pokryciem. Każda krawędź
łączy ciągi o różnej parzystości jedynek, więc
jest incydentna z jakimś wierzchołkiem z
. Zbiór
jest więc pokryciem wierzchołkowym. Ciągów o parzystej liczbie jedynek jest dokładnie tyle, co o nieparzystej liczbie jedynek. A zatem
, czyli pokrycie wierzchołkowe
jest minimalne.
- Maksymalny zbiór niezależny:
.
Z Twierdzenia Gallai 1.1 wiemy, że

Wystarczy więc znaleźć zbiór niezależny o elementach.
Zbiór
jest oczywiście niezależny,
bo każda krawędź w kostce łączy ciągi różniące się parzystością jedynek.
Z drugiej strony, zbiór
realizuje wartość
,
więc jest maksymalnym zbiorem niezależnym.

Ćwiczenie 3
Wskaż minimalne pokrycie krawędziowe drzewa
z rysunku 3
oraz maksymalne skojarzenie
zawarte w tym pokryciu.
Wskazówka
Zauważ, że pokrycie jest rozłączną sumą gwiazd. Tak więc szukając maksymalengo skojarzenia wystarczy brać po jednej krawędzi z każdej gwiazdy stworzonej przez minimalne pokrycie.
Rozwiązanie
<flash>file=Cw minmax drzewo rozw.swf|width=250|height=200</flash>

Na rysunku 4 kolorami niebieskim i zielonym zostały zaznaczone krawędzie z minimalnego pokrycia, przy czym zielone krawędzie tworzą maksymalne skojarzenie.
Ćwiczenie 4
Pokaż, że w grafie prostym bez punktów izolowanych, maksymalne, w sensie inkluzji,
skojarzenie
jest najbardziej liczne wtedy i tylko wtedy, gdy
jest zawarte w jakimś minimalnym pokryciu krawędziowym
.
Wskazówka
Przeprowadź rozumowanie analogiczne do dowodu pierwszej części Twierdzenia 1.2.
Rozwiązanie
Niech będzie najliczniejszym skojarzeniem w grafie
,
czyli
.
Wtedy
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
.
Zbiór tak wybranych krawędzi w sumie z
tworzy pokrycie krawędziowe
grafu
.
W
jest
krawędzi ze skojarzenia
oraz
krawędzi incydentnych z elementami
.
A zatem
ma

elementów.
Dla dowodu implikacji odwrotnej niech skojarzenie zawiera się w minimalnym pokryciu krawędziowym
. Pokrycie krawędziowe
, jako minimalne, składa się z gwiazd.
A zatem, 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łoby maksymalne w sensie inkluzji, 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 skojarzenie
ma

krawędzi, co kończy dowód.
Ćwiczenie 5
Udowodnij, że w grafie prostym zachodzi:

Wskazówka
Niech będzie maksymalnym skojarzeniem,
a
minimalnym pokryciem wierzchołkowym w grafie
.
Co możesz powiedzieć o związku skojarzenia
z pokryciem
.
Ponadto, rozważ zbiór wszystkich wierzchołków incydentnych z którąś krawędzią z
.
Rozwiązanie
Niech będzie maksymalnym skojarzeniem, a
minimalnym pokryciem wierzchołkowym w grafie
. Oczywiście każda krawędź skojarzenia
, tak jak i każda krawędź grafu
jest incydentna z jakimś wierzchołkiem z
. Skoro jednak
jest skojarzeniem, to różne krawędzie z
nie mogą być incydentne z tym samym wierzchołkiem. A zatem:

Ponadto, każda krawędź jest incydentna z jakimś wierzchołkiem
ze zbioru
składającego się ze wszystkich końców krawędzi skojarzenia
.
Istotnie, gdyby krawędź
nie była incydentna z
,
to zbiór
powiększony o
przeczyłby o maksymalności skojarzenia
.
A zatem
jest pokryciem wierzchołkowym.
Z każdej krawędzi
otrzymał po dwa wierzchołki, więc

Ćwiczenie 6
Udowodnij, że w grafie dwudzielnym
bez wierzchołków izolowanych zachodzi
.
Wskazówka
Rozwiązanie
Na mocy Twierdzenia Koniga:

Z kolei Twierdzenie Gallai daje:

A zatem:

czyli
