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

From Studia Informatyczne

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).