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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 1 pośredniej wersji utworzonej przez tego samego użytkownika)
Linia 14: Linia 14:
 
</div>
 
</div>
  
<!-== Zadanie 2 ==
+
<!--== Zadanie 2 ==
 
{{kotwica|zadanie 2|}}
 
{{kotwica|zadanie 2|}}
 
Pokaż, że jeżeli graf <math>G</math> rozpięty na parzystej liczbie wierzchołków <math>p</math> ma więcej niż <math>\left(\begin{array}{c}p-1 \\ 2\end{array}\right)</math> krawędzi, to zawiera doskonałe skojarzenie.
 
Pokaż, że jeżeli graf <math>G</math> rozpięty na parzystej liczbie wierzchołków <math>p</math> ma więcej niż <math>\left(\begin{array}{c}p-1 \\ 2\end{array}\right)</math> krawędzi, to zawiera doskonałe skojarzenie.
Linia 39: Linia 39:
 
</div>
 
</div>
  
->
+
-->
  
 
== Zadanie 2 ==
 
== Zadanie 2 ==
Linia 92: Linia 92:
 
</div>
 
</div>
  
== Zadanie 5 ==
+
== Zadanie 4 ==
{{kotwica|zadanie 5|}}
+
{{kotwica|zadanie 4|}}
 
Załóżmy, że graf <math>G = (V,E)</math> ma doskonałe skojarzenie. Powiemy, że krawędź <math>(i,j)</math> jest ''niedozwolona'' jeżeli nie należy do żadnego doskonałego skojarzenia w <math>G</math>. Pokaż jak w czasie <math>O(n^3)</math> znaleźć wszystkie niedozwolone krawędzie w grafie <math>G</math>.
 
Załóżmy, że graf <math>G = (V,E)</math> ma doskonałe skojarzenie. Powiemy, że krawędź <math>(i,j)</math> jest ''niedozwolona'' jeżeli nie należy do żadnego doskonałego skojarzenia w <math>G</math>. Pokaż jak w czasie <math>O(n^3)</math> znaleźć wszystkie niedozwolone krawędzie w grafie <math>G</math>.
  
 
<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