Matematyka dyskretna 2/Ćwiczenia 1: Zagadnienia Mini-Maksowe w grafach

From Studia Informatyczne

< Matematyka dyskretna 2

[Edytuj]

Zagadnienia Mini-Maksowe w grafach

1. Graf Petersena

Ć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>

2. Skojarzenie doskonałe w grafie Petersena

Doskonałe skojarzenie w grafie Petersena zostało przedstawione na Rysunku 2.

Ćwiczenie 2

Kostka $\displaystyle k$ -wymiarowa $\displaystyle \mathcal{Q}_{k}$ to graf, którego wierzchołki są ciągami $\displaystyle \left( a_1,a_2,\ldots,a_k \right)$ , gdzie $\displaystyle a_i=0,1$ , a krawędzie łączą te ciągi, które różnią się na jednej tylko pozycji. W kostce $\displaystyle \mathcal{Q}_{k}$ znajdź

maksymalne skojarzenie,
minimalne pokrycie krawędziowe,
minimalne pokrycie wierzchołkowe,
maksymalny zbiór niezależny,

i podaj ich liczności.

Wskazówka

Kostka $\displaystyle \mathcal{Q}_{k}$ ma skojarzenie doskonałe. Będzie ono więc też minimalnym pokryciem krawędziowym. Ponieważ kostka $\displaystyle \mathcal{Q}_{k}$ jest grafem dwudzielnym, w poszukiwaniu minimalnego pokrycia wierzchołkowego można użyć Twierdzenie Koniga 1.4.

Rozwiązanie

Maksymalne skojarzenie: $\displaystyle \nu\left( \mathcal{Q}_{k} \right)=2^{k-1}$ .

Skojarzenie $\displaystyle M$ ciągu $\displaystyle \left( 0,a_2,\ldots,a_k \right)$ z ciągiem $\displaystyle \left( 1,a_2,\ldots,a_k \right)$ jest doskonałe i zawiera $\displaystyle \left\vert {\sf V}\!\left(\mathcal{Q}_{k}\right) \right\vert/2=2^{k-1}$ krawędzi.

Minimalne pokrycie krawędziowe: $\displaystyle \rho\left( \mathcal{Q}_{k} \right)=2^{k-1}$ .

Zdefiniowane wyżej skojarzenie maksymalne $\displaystyle M$ jest doskonałe, więc $\displaystyle M$ jest pokryciem krawędziowym. Na mocy Twierdzenia 1.2 wiemy, że maksymalne skojarzenie zawiera się w jakimś minimalnym pokryciu krawędziowym. Pokrycie krawędziowe $\displaystyle M$ jest więc minimalne.

Minimalne pokrycie wierzchołkowe: $\displaystyle \tau\left( \mathcal{Q}_{k} \right)=2^{k-1}$ .

Kostka $\displaystyle \mathcal{Q}_{k}$ jest grafem dwudzielnym, więc korzystając z Twierdzenia Koniga 1.4 otrzymujemy, że minimalne pokrycie wierzchołkowe ma

$\displaystyle \tau\left( \mathcal{Q}_{k} \right)=\nu\left( \mathcal{Q}_{k} \right)=2^{k-1}$

elementów. Pozostaje jedynie wskazać takie pokrycie wierzchołkowe o $\displaystyle 2^{k-1}$ elementach. Pokażemy, że zbiór $\displaystyle C$ wszystkich ciągów o nieparzystej liczbie jedynek jest takim pokryciem. Każda krawędź $\displaystyle e\in{\sf E}\!\left(\mathcal{Q}_{k}\right)$ łączy ciągi o różnej parzystości jedynek, więc $\displaystyle e$ jest incydentna z jakimś wierzchołkiem z $\displaystyle C$ . Zbiór $\displaystyle C$ jest więc pokryciem wierzchołkowym. Ciągów o parzystej liczbie jedynek jest dokładnie tyle, co o nieparzystej liczbie jedynek. A zatem $\displaystyle \left\vert C \right\vert=2^k/2=2^{k-1}$ , czyli pokrycie wierzchołkowe $\displaystyle C$ jest minimalne.

Maksymalny zbiór niezależny: $\displaystyle \alpha\left( \mathcal{Q}_{k} \right)=2^{k-1}$ .

Z Twierdzenia Gallai 1.1 wiemy, że

$\displaystyle \alpha\left( \mathbf{G} \right) =\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-\tau\left( \mathbf{G} \right) =2^k-2^{k-1}=2^{k-1}.$

Wystarczy więc znaleźć zbiór niezależny o $\displaystyle 2^{k-1}$ elementach. Zbiór $\displaystyle C$ 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 $\displaystyle C$ realizuje wartość $\displaystyle \alpha\left( \mathbf{G} \right)=2^{k-1}$ , więc jest maksymalnym zbiorem niezależnym.

3. Drzewo $\displaystyle \mathbf{T}_1$

Ćwiczenie 3

Wskaż minimalne pokrycie krawędziowe $\displaystyle C$ drzewa $\displaystyle \mathbf{T}_1$ z rysunku 3 oraz maksymalne skojarzenie $\displaystyle M$ 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>

4. Minimalne pokrycie wierzchołkowe (niebieskie i zielone krawędzie) oraz maksymalne skojarzenie (zielone krawędzie) w drzewie $\displaystyle \mathbf{T}_1$

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 $\displaystyle \mathbf{G}$ bez punktów izolowanych, maksymalne, w sensie inkluzji, skojarzenie $\displaystyle M$ jest najbardziej liczne wtedy i tylko wtedy, gdy $\displaystyle M$ jest zawarte w jakimś minimalnym pokryciu krawędziowym $\displaystyle \mathbf{G}$ .

Wskazówka

Przeprowadź rozumowanie analogiczne do dowodu pierwszej części Twierdzenia 1.2.

Rozwiązanie

Niech $\displaystyle M$ będzie najliczniejszym skojarzeniem w grafie $\displaystyle \mathbf{G}$ , czyli $\displaystyle \left\vert M \right\vert=\nu\left( \mathbf{G} \right)$ . Wtedy $\displaystyle I={\sf V}\!\left(\mathbf{G}\right)- {\sf V}\!\left(M\right)$ jest zbiorem niezależnym i ma $\displaystyle \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-2\cdot\nu\left( \mathbf{G} \right)$ elementów. Ponieważ $\displaystyle \mathbf{G}$ nie ma punktów izolowanych, to każdy wierzchołek z $\displaystyle I$ jest połączony krawędzią z jakimś wierzchołkiem ze zbioru $\displaystyle {\sf V}\!\left(M\right)$ . Dla każdego wierzchołka $\displaystyle v\in I$ wybierzmy krawędź incydentną z $\displaystyle v$ . Zbiór tak wybranych krawędzi w sumie z $\displaystyle M$ tworzy pokrycie krawędziowe $\displaystyle C_e$ grafu $\displaystyle \mathbf{G}$ . W $\displaystyle C_e$ jest $\displaystyle \nu\left( \mathbf{G} \right)$ krawędzi ze skojarzenia $\displaystyle M$ oraz $\displaystyle \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-2\cdot\nu\left( \mathbf{G} \right)$ krawędzi incydentnych z elementami $\displaystyle I$ . A zatem $\displaystyle C_e$ ma

$\displaystyle \left\vert C_e' \right\vert =\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 {\sf V}\!\left(\mathbf{G}\right) \right\vert-\nu\left( \mathbf{G} \right)=\rho\left( \mathbf{G} \right)$

elementów.

Dla dowodu implikacji odwrotnej niech skojarzenie $\displaystyle M$ zawiera się w minimalnym pokryciu krawędziowym $\displaystyle C$ . Pokrycie krawędziowe $\displaystyle C$ , jako minimalne, składa się z gwiazd.

A zatem, $\displaystyle M$ musi zawierać po dokładnie jednej krawędzi z każdej gwiazdy pokrycia $\displaystyle C$ . Istotnie, gdyby jakaś gwiazda nie zawierała krawędzi z $\displaystyle M$ , to $\displaystyle M$ nie byłoby maksymalne w sensie inkluzji, a gdyby w gwieździe były dwie krawędzie z $\displaystyle M'$ ,to $\displaystyle M'$ nie byłoby skojarzeniem. Tak więc $\displaystyle C$ składa się z $\displaystyle \left\vert M' \right\vert$ gwiazd. Ponieważ w każdej gwieździe krawędzi jest o jedną mniej niż wierzchołków, to skojarzenie $\displaystyle M'$ ma

$\displaystyle \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-\left\vert C \right\vert =\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-\rho\left( \mathbf{G} \right) =\nu\left( \mathbf{G} \right)$

krawędzi, co kończy dowód.

Ćwiczenie 5

Udowodnij, że w grafie prostym $\displaystyle \mathbf{G}$ zachodzi:

$\displaystyle \nu\left( \mathbf{G} \right)\leq \tau\left( \mathbf{G} \right)\leq 2\nu\left( \mathbf{G} \right).$

Wskazówka

Niech $\displaystyle M$ będzie maksymalnym skojarzeniem, a $\displaystyle C$ minimalnym pokryciem wierzchołkowym w grafie $\displaystyle \mathbf{G}$ . Co możesz powiedzieć o związku skojarzenia $\displaystyle M$ z pokryciem $\displaystyle C$ . Ponadto, rozważ zbiór wszystkich wierzchołków incydentnych z którąś krawędzią z $\displaystyle M$ .

Rozwiązanie

Niech $\displaystyle M$ będzie maksymalnym skojarzeniem, a $\displaystyle C$ minimalnym pokryciem wierzchołkowym w grafie $\displaystyle \mathbf{G}$ . Oczywiście każda krawędź skojarzenia $\displaystyle M\subseteq{\sf E}\!\left(\mathbf{G}\right)$ , tak jak i każda krawędź grafu $\displaystyle \mathbf{G}$ jest incydentna z jakimś wierzchołkiem z $\displaystyle C$ . Skoro jednak $\displaystyle M$ jest skojarzeniem, to różne krawędzie z $\displaystyle M$ nie mogą być incydentne z tym samym wierzchołkiem. A zatem:

$\displaystyle \nu\left( \mathbf{G} \right)=\left\vert M \right\vert\leq \left\vert C \right\vert=\tau\left( \mathbf{G} \right).$

Ponadto, każda krawędź $\displaystyle e\in{\sf E}\!\left(\mathbf{G}\right)$ jest incydentna z jakimś wierzchołkiem ze zbioru $\displaystyle C'$ składającego się ze wszystkich końców krawędzi skojarzenia $\displaystyle M$ . Istotnie, gdyby krawędź $\displaystyle e$ nie była incydentna z $\displaystyle C'$ , to zbiór $\displaystyle M$ powiększony o $\displaystyle e$ przeczyłby o maksymalności skojarzenia $\displaystyle M$ . A zatem $\displaystyle C'$ jest pokryciem wierzchołkowym. Z każdej krawędzi $\displaystyle C'$ otrzymał po dwa wierzchołki, więc

$\displaystyle \tau\left( \mathbf{G} \right)\leq\left\vert C' \right\vert=2\left\vert M \right\vert=2\nu\left( \mathbf{G} \right).$

Ćwiczenie 6

Udowodnij, że w grafie dwudzielnym $\displaystyle \mathbf{G}$ bez wierzchołków izolowanych zachodzi $\displaystyle \rho\left( \mathbf{G} \right)=\alpha\left( \mathbf{G} \right)$ .

Wskazówka

Skorzystaj z Twierdzenia Koniga 1.4 i Twierdzenia Gallai 1.1.

Rozwiązanie

Na mocy Twierdzenia Koniga:

$\displaystyle \tau\left( \mathbf{G} \right)=\nu\left( \mathbf{G} \right).$

Z kolei Twierdzenie Gallai daje:

$\displaystyle \aligned \tau\left( \mathbf{G} \right)&=\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-\alpha\left( \mathbf{G} \right),\\ \nu\left( \mathbf{G} \right)&=\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-\rho\left( \mathbf{G} \right). \endaligned$

A zatem:

$\displaystyle \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-\alpha\left( \mathbf{G} \right)\ = \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-\rho\left( \mathbf{G} \right),$

czyli

$\displaystyle \rho\left( \mathbf{G} \right)=\alpha\left( \mathbf{G} \right).$

Źródło: "http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_2/%C4%86wiczenia_1:_Zagadnienia_Mini-Maksowe_w_grafach"

Matematyka dyskretna 2/Ćwiczenia 1: Zagadnienia Mini-Maksowe w grafach

From Studia Informatyczne

Zagadnienia Mini-Maksowe w grafach

Nawigacja

Szukaj

Napisz do nas