Zaawansowane algorytmy i struktury danych/Ćwiczenia 8

Zadanie 1

Pokaż, że każdy graf $G$ może zostać zanurzony w grafie $G'$ 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'$ może być planarny?

Rozwiązanie

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

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

500px

Łatwo teraz zauważyć, że dowolne skojarzenie $M$ w grafie $G$ daje sie rozszerzyć na doskonałe skojarzenie w grafie $G'$.

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{cases}x_{i,j}&{\mbox{jeżeli }}(i,j)\in E,\ i\in V_{1},\ j\in V_{2},0&{\mbox{w przeciwnym przypadku,}}\end{cases}}$

gdzie$x_{i,j}$ to różne zmienne przypisane krawędzią. Pokaż, że $\det(A(G))\neq 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 \Pi _{n}$ jest niezerowy, gdy wszystkie krawędzie $ip_{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{cases}x_{i,j}&{\mbox{jeżeli }}(i,j)\in E{\mbox{ i }}i<j,-x_{j,i}&{\mbox{jeżeli }}(i,j)\in E{\mbox{ i }}i>j,0&{\mbox{w przeciwnym przypadku,}}\end{cases}}$

gdzie$x_{i,j}$ to różne zmienne przypisane krawędzią. Pokaż, że $\det(A(G))\neq 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 \Pi _{n}$ jest niezerowy, gdy wszystkie krawędzie $ip_{i}$ istnieją w grafie $G$. Widzimy więc, że zbiór krawędzi $ip_{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'$ 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'$. Zbudujmy teraz las $M'$-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'$. 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})$.