Zaawansowane algorytmy i struktury danych/Ćwiczenia 8

Zadanie 1

Pokaż, że każdy graf $G$ może zostać zanurzony w grafie $G^{\prime }$ rozpiętym na co najwyżej $3|V(G)|$ wierzchołkach tak, aby dla każdego skojarzenia $M$ w $G$ istniało dokładnie jedno doskonałe skojarzenie $F$ takie, że $F\cap E(G)=M$. Czy jeżeli $G$ jest zewnętrznie planarny, to $G^{\prime }$ może być planarny?

Rozwiązanie

Graf $G^{\prime }$ konstruujemy z grafu $G$ poprzez dodanie do każdego wierzchołka $v_i$ dla $1\le i\le n$dwa dodatkowe wierzchołki ${v_i}^{\prime }$ i ${v_i}^{″}$ połączone krawędziami $v_i{v_i}^{\prime }$, $v_i{v_i}^{″}$ oraz ${v_i}^{\prime }{v_i}^{″}$. Następnie dodajemy krawędzie ${v_i}^{″}{v}_{i^{\prime }+1}$ dla $1\le i\le n-1$. Jeżeli $n$ jest nieparzyste to usuwamy wierzchołek ${v_n}^{″}$.

Konstrukcja ta została przedstawiona na rysunku poniżej.

Plik:Zasd maximum matchings.png

Łatwo teraz zauważyć, że dowolne skojarzenie $M$ w grafie $G$ daje sie rozszerzyć na doskonałe skojarzenie w grafie $G^{\prime }$.

Zadanie 2

Dla grafu dwudzielnego $G=(V_1\cup V_2,E)$, gdzie $|V_1|=|V_2|$ zdefiniujmy symboliczną macierz sąsiedztwa $B(G)$ rozmiaru $V_1\times V_2$ jako:

$B(G{)}_{i,j}=\{\begin{array}{lll}{x}_{i,j}& \text{jeżeli }(i,j)\in E,i\in V_1,j\in V_2,0& \text{w przeciwnym przypadku,}\end{array}$

gdzie$x_{i,j}$ to różne zmienne przypisane krawędzią. Pokaż, że $\det (A(G))\ne 0$ wtedy i tylko wtedy gdy $G$ ma doskonałe skojarzenie.

Rozwiązanie

Wyznacznik $\det (B(G))$ możemy zapisać jako:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \det(B(G)) = \sum_{p\in \Pi_n} \sgn(p) \prod_{i=1}^{n} B(G)_{i,p_i)} .

Zauważmy teraz, że wyraz tej sumy dla $p\in {\mathrm{\Pi }}_n$ jest niezerowy, gdy wszystkie krawędzie $i{p}_i$ istnieją w grafie $G$. Zauważmy, że ten zbiór krawędzi odpowiada dokładnie doskonałemu skojarzeniu, ponieważ permutacja $p$ przypisuje każdemu wierzchołkowi $i$ różny wierzchołek $p_i$.

Zadanie 3

Dla grafu $G=(V,E)$ zdefiniujmy symboliczną macierz sąsiedztwa $A(G)$ rozmiaru $V\times V$ jako:

$A(G{)}_{i,j}=\{\begin{array}{llll}{x}_{i,j}& \text{jeżeli }(i,j)\in E\text{ i }i<j,-x_{j,i}& \text{jeżeli }(i,j)\in E\text{ i }i>j,0& \text{w przeciwnym przypadku,}\end{array}$

gdzie$x_{i,j}$ to różne zmienne przypisane krawędzią. Pokaż, że $\det (A(G))\ne 0$ wtedy i tylko wtedy gdy $G$ ma doskonałe skojarzenie.

Rozwiązanie

Wyznacznik $\det (A(G))$ możemy zapisać jako:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \det(A(G)) = \sum_{p\in \Pi_n} \sgn(p) \prod_{i=1}^{n} A(G)_{i,p_i)} .

Zauważmy teraz, że wyraz tej sumy dla $p\in {\mathrm{\Pi }}_n$ jest niezerowy, gdy wszystkie krawędzie $i{p}_i$ istnieją w grafie $G$. Widzimy więc, że zbiór krawędzi $i{p}_i$ opisuje zbiór cykli w grafie $G$. Cykle te odpowiadają dokładnie cyklom permutacji $p$. Weźmy permutację $p$ zawierającą cykl $C$ nieparzystej długości. Skonstruujmy z $p$ permutację $p^{\prime }$ z odwróconym skierowaniem cyklu $C$. Zauważmy, że elementy odpowiadające tym permutacjom zawierają te same zmienne. Jednak ich znaki są przeciwne, ze względu na antysymetryczność macierzy $A(G)$. Widzimy więc, że w $\det (A(G))$ niezerowe będą tylko wyrazy odpowiadające zbiorom cykli parzystej długości. Z każdego takiego zbioru cykli łatwo jest skonstruować doskonałe skojarzenie. Wystarczy wziąć z każdego cyklu co drugą krawędź.

Zadanie 4

Załóżmy, że graf $G=(V,E)$ ma doskonałe skojarzenie. Powiemy, że krawędź $(i,j)$ jest niedozwolona jeżeli nie należy do żadnego doskonałego skojarzenia w $G$. Pokaż jak w czasie $O(n^3)$ znaleźć wszystkie niedozwolone krawędzie w grafie $G$.

Rozwiązanie

Zacznijmy od znalezienia doskonałego skojarzenia $M$ w $G$ przy pomocy algorytmu Edmondsa. Rozpatrzmy teraz wierzchołek $v\in V$. Usuńmy ze skojarzenia krawędź $vu$ sąsiednią z $v$ otrzymując mniejsze skojarzenie $M^{\prime }$. Zbudujmy teraz las $M^{\prime }$-naprzemienny $L$ w $G$. Jednak w trakcie budowy gdy napotkamy krawędź łączącą dwie składowe lasu to dodajemy do zbioru $X$ nie powiększając skojarzenia. Rozpatrzmy teraz graf $L\cup X$, graf ten koduje wszystkie ścieżki powiększające względem $M^{\prime }$. Możemy więc za jego pomocą wyznaczyć wszystkie ich początki, a co za tym idzie krawędzie dozwolone sąsiednie z $v$. Procedura ta dla wierzchołka $v$ działa w czasie $O(n^2)$, a więc dla całego grafu zajmie ona czas $O(n^3)$.