Zaawansowane algorytmy i struktury danych/Ćwiczenia 8

From Studia Informatyczne

Spis treści

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 \le i \le ndwa dodatkowe wierzchołki v_i' i v_i'' połączone krawędziami v_iv_i', v_iv_i'' oraz v_i'v_i''. Następnie dodajemy krawędzie v_i''v_{i+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.

Ł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}

gdziex_{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:

\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}

gdziex_{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:

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