Zaawansowane algorytmy i struktury danych/Ćwiczenia 8: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
Linia 98: Linia 98:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Zacznijmy od znalezienia doskonałego skojarzenia w <math>G</math> przy pomocy algorytmu Edmondsa.
+
Zacznijmy od znalezienia doskonałego skojarzenia <math>M</math> w <math>G</math> przy pomocy algorytmu Edmondsa. Rozpatrzmy teraz wierzchołek <math>v \in V</math>. Usuńmy ze skojarzenia krawędź <math>vu</math> sąsiednią z <math>v</math> otrzymując mniejsze skojarzenie <math>M'</math>. Zbudujmy teraz las <math>M'</math>-naprzemienny <math>L</math> w <math>G</math>. Jednak w trakcie budowy gdy napotkamy krawędź łączącą dwie składowe lasu to dodajemy do zbioru <math>X</math> nie powiększając skojarzenia. Rozpatrzmy teraz graf <math>L \cup X</math>, graf ten koduje wszystkie ścieżki powiększające względem <math>M'</math>. Możemy więc za jego pomocą wyznaczyć wszystkie ich początki, a co za tym idzie krawędzie dozwolone sąsiednie z <math>v</math>. Procedura ta dla wierzchołka <math>v</math> działa w czasie <math>O(n^2)</math>, a więc dla całego grafu zajmie ona czas <math>O(n^3)</math>.
 
 
 
</div>
 
</div>
 
</div>
 
</div>

Aktualna wersja na dzień 16:13, 28 wrz 2006

Zadanie 1

Pokaż, że każdy graf może zostać zanurzony w grafie rozpiętym na co najwyżej wierzchołkach tak, aby dla każdego skojarzenia w istniało dokładnie jedno doskonałe skojarzenie takie, że . Czy jeżeli jest zewnętrznie planarny, to może być planarny?

Rozwiązanie


Zadanie 2

Dla grafu dwudzielnego , gdzie zdefiniujmy symboliczną macierz sąsiedztwa rozmiaru jako:

gdzie to różne zmienne przypisane krawędzią. Pokaż, że wtedy i tylko wtedy gdy ma doskonałe skojarzenie.

Rozwiązanie


Zadanie 3

Dla grafu zdefiniujmy symboliczną macierz sąsiedztwa rozmiaru jako:

gdzie to różne zmienne przypisane krawędzią. Pokaż, że wtedy i tylko wtedy gdy ma doskonałe skojarzenie.

Rozwiązanie

Zadanie 4

Załóżmy, że graf ma doskonałe skojarzenie. Powiemy, że krawędź jest niedozwolona jeżeli nie należy do żadnego doskonałego skojarzenia w . Pokaż jak w czasie znaleźć wszystkie niedozwolone krawędzie w grafie .

Rozwiązanie