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 == Pokaż, że jeżeli graf $G$ rozpięty na parzystej liczbie wierzchołków $p$ ma więcej niż $\left({\begin{array}{c}p-1\\2\end{array}}\right)$ krawędzi, to zawiera doskonałe skojarzenie.

Rozwiązanie

Przeprowadzimy dowód przez indukcję. Łatwo zauważyć, że dla $p=2$ graf ma co najmniej jedną krawędź, a więc zawiera doskonałe skojarzenie. Załóżmy, że własność ta zachodzi dla grafów o mniej niż $p$ wierzchołkach. Pokażemy teraz, że zachodzi dla grafu $G$ o $p$ wierzchołkach. Wybierzmy z grafu $G$ dwa wierzchołki $u$ i $v$ których sumaryczny stopień jest minimalny. Niech $G'$ będzie grafem otrzymanym z $G$ poprzez usunięcie wierzchołków $u$ i $v$.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left(\begin{array}{c}p-1 \\ 2\end{array}\right) - \left(\begin{array}{c}p-3 \\ 2\end{array}\right) = \frac{(p-1)(p-2)}{2} - \frac{(p-3)(p-4)}{2} = \frac{p^2 -3p+2}{2} - \frac{p^2 -7p +12}{2} = \frac{4p-10){2} = 2p-5. }

Weźmy dwa wierzchołki $v,u$ w grafie $G$ o najmniejszym stopniu. Jeżeli wierzchołki te

$\deg(u)+\deg(v)$. Jeżeli

dowolne wierzchołki w grafie $G$ jeżeli nie są one połączone krawędzią, to z każdego z nich wychodzi $p-2$ krawędzi. Usuńmy te dwa wierzchołki

->

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 5

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 w $G$ przy pomocy algorytmu Edmondsa.

->