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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
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>.
  
Linia 101: Linia 101:
  
 
</div>
 
</div>
</div>->
+
</div>
  
  

Wersja z 15:49, 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