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

Zagadnienia Mini-Maksowe w grafach

Ćwiczenie 1

Czy graf Petersena przedstawiony na Rysuneku Uzupelnic cw minmax petersen| ma skojarzenie doskonałe? Odpowiedź uzasadnij.

{cw_grafy_petersen} {Graf Petersena.

Rozwiązanie

Doskonałe skojarzenie w grafie Petersena zostało przedstawione na Rysunku Uzupelnic cw minmax petersen match|.

{cw_minmax_petersen_match} {Skojarzenie doskonałe w grafie Petersena.

Ćwiczenie 2

Kostka $k$ -wymiarowa ${{𝒬}}_k$ to graf, którego wierzchołki są ciągami $(a_1,a_2,\dots ,a_k)$ , gdzie $a_i=0,1$ , a krawędzie łączą te ciągi, które różnią się na jednej tylko pozycji. W kostce ${{𝒬}}_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 ${{𝒬}}_k$ ma skojarzenie doskonałe. Będzie ono więc też minimalnym pokryciem krawędziowym. Ponieważ kostka ${{𝒬}}_k$ jest grafem dwudzielnym, w poszukiwaniu minimalnego pokrycia wierzchołkowego można użyć Twierdzenie Koniga [th][th Konig].

Rozwiązanie

• Maksymalne skojarzenie: $\nu \left({{𝒬}}_k\right)=2^{k-1}$ .

Skojarzenie $M$ ciągu $(0,a_2,\dots ,a_k)$ z ciągiem $(1,a_2,\dots ,a_k)$ jest doskonałe i zawiera Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left\vert {\sf V}\!\left(\mathcal{Q}_{k}\right) \right\vert/2=2^{k-1} } krawędzi.

• Minimalne pokrycie krawędziowe: $\rho \left({{𝒬}}_k\right)=2^{k-1}$ .

Zdefiniowane wyżej skojarzenie maksymalne $M$ jest doskonałe, więc $M$ jest pokryciem krawędziowym. Na mocy Twierdzenia [th][th covering = matching] wiemy, że maksymalne skojarzenie zawiera się w jakimś minimalnym pokryciu krawędziowym. Pokrycie krawędziowe $M$ jest więc minimalne.

• Minimalne pokrycie wierzchołkowe: $\tau \left({{𝒬}}_k\right)=2^{k-1}$ .

Kostka ${{𝒬}}_k$ jest grafem dwudzielnym, więc korzystając z Twierdzenia Koniga [th][th Konig] otrzymujemy, że minimalne pokrycie wierzchołkowe ma

$\tau \left({{𝒬}}_k\right)=\nu \left({{𝒬}}_k\right)=2^{k-1}$

elementów. Pozostaje jedynie wskazać takie pokrycie wierzchołkowe o $2^{k-1}$ elementach. Pokażemy, że zbiór $C$ wszystkich ciągów o nieparzystej liczbie jedynek jest takim pokryciem. Każda krawędź Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle e\in{\sf E}\!\left(\mathcal{Q}_{k}\right) } łączy ciągi o różnej parzystości jedynek, więc $e$ jest incydentna z jakimś wierzchołkiem z $C$ . Zbiór $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 $\left|C\right|=2^k/2=2^{k-1}$ , czyli pokrycie wierzchołkowe $C$ jest minimalne.

• Maksymalny zbiór niezależny: $\alpha \left({{𝒬}}_k\right)=2^{k-1}$ .

Z Twierdzenia Gallai [th][th Gallai] wiemy, że

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 $2^{k-1}$ elementach. Zbiór $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 $C$ realizuje wartość $\alpha \left(\mathbf{𝐆}\right)=2^{k-1}$ , więc jest maksymalnym zbiorem niezależnym.

Ćwiczenie 3

Wskaż minimalne pokrycie krawędziowe $C$ drzewa ${\mathbf{𝐓}}_1$ z Rysunku Uzupelnic cw minmax drzewo rozw| oraz maksymalne skojarzenie $M$ zawarte w tym pokryciu.

{cw_minmax_drzewo} {Drzewo ${\mathbf{𝐓}}_1$ .

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

Na Rysunku Uzupelnic cw minmax drzewo rozw| kolorami niebieskim i zielonym zostały zaznaczone krawędzie z minimalnego pokrycia, przy czym zielone krawędzie tworzą maksymalne skojarzenie.

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

Ćwiczenie 4

Pokaż, że w grafie prostym $\mathbf{𝐆}$ bez punktów izolowanych, maksymalne, w sensie inkluzji, skojarzenie $M$ jest najbardziej liczne wtedy i tylko wtedy, gdy $M$ jest zawarte w jakimś minimalnym pokryciu krawędziowym $\mathbf{𝐆}$ .

Wskazówka

Przeprowadź rozumowanie analogiczne do dowodu pierwszej części Twierdzenia [th][th covering = matching].

Rozwiązanie

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 $M$ zawiera się w minimalnym pokryciu krawędziowym $C$ . Pokrycie krawędziowe $C$ , jako minimalne, składa się z gwiazd. A zatem, $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łoby maksymalne w sensie inkluzji, a gdyby w gwieździe były dwie krawędzie z $M^{\prime }$ ,to $M^{\prime }$ nie byłoby skojarzeniem. Tak więc $C$ składa się z $\left|M^{\prime }\right|$ gwiazd. Ponieważ w każdej gwieździe krawędzi jest o jedną mniej niż wierzchołków, to skojarzenie $M^{\prime }$ ma

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 $\mathbf{𝐆}$ zachodzi:

$\nu \left(\mathbf{𝐆}\right)\le \tau \left(\mathbf{𝐆}\right)\le 2\nu \left(\mathbf{𝐆}\right).$

Wskazówka

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

Rozwiązanie

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

$\nu \left(\mathbf{𝐆}\right)=\left|M\right|\le \left|C\right|=\tau \left(\mathbf{𝐆}\right).$

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

$\tau \left(\mathbf{𝐆}\right)\le \left|C^{\prime }\right|=2\left|M\right|=2\nu \left(\mathbf{𝐆}\right).$

Ćwiczenie 6

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

Wskazówka

Skorzystaj z Twierdzenia Koniga [th][th Konig] i Twierdzenia Gallai [th][th Gallai].

Rozwiązanie

Na mocy Twierdzenia Koniga:

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

Z kolei Twierdzenie Gallai daje:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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

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