Zaawansowane algorytmy i struktury danych/Ćwiczenia 7: Różnice pomiędzy wersjami
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 2: | Linia 2: | ||
{{kotwica|zadanie 1|}} | {{kotwica|zadanie 1|}} | ||
Masz dany graf | |||
Sprowadzenie przeplywow wierzcholkowych dla przepustowosci krawedzi | |||
0-1 do skojarzen dwudzielnych - zlozonosc ma wyjsc taka sama. | |||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie''' | <div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie''' | ||
| Linia 13: | Linia 15: | ||
{{kotwica|zadanie 2|}} | {{kotwica|zadanie 2|}} | ||
Sprowadzenie przeplywow dla przepustowosci krawedzi 0-1 do | |||
skojarzen dwudzilenych - zlozonosc m^{5/2} jak uzyjemy algorytmu HK. | |||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie''' | <div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie''' | ||
| Linia 25: | Linia 28: | ||
{{kotwica|zadanie 3|}} | {{kotwica|zadanie 3|}} | ||
Sprowadznie przeplywow dla przepustowosci krawedzi 0-1 do skojarzen | |||
dwudzielnych z zachowaniem planarnosci - zlozonosc moze wzrosnac. | |||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie''' | |||
<div class="mw-collapsible-content" style="display:none"> | |||
</div> | |||
</div> | |||
== Zadanie 4 == | |||
{{kotwica|zadanie 4|}} | |||
Znajdowanie najmniejszego pokrycia wierzcholkowego grafu dwudzielnego. | |||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie''' | |||
<div class="mw-collapsible-content" style="display:none"> | |||
</div> | |||
</div> | |||
== Zadanie 5 == | |||
{{kotwica|zadanie 5|}} | |||
Obliczanie skierowania grafu | |||
Pokaz, ze jezeli zachodzi $\frac{|E_H|}{|V_H|} \le d$, dla kazdego | |||
podgrafu $H=(V_H,E_H)$ grafu $G$, to wtedy $G$ ma skierowanie, w | |||
ktorym kazdy wierzcholek ma stopien wychodzacy co najwyzej | |||
$d$. Skierowanie to nadanie krawedziom grafu jednego z dwoch | |||
kierunkow. | |||
Wersja z 10:25, 12 wrz 2006
Zadanie 1
Masz dany graf Sprowadzenie przeplywow wierzcholkowych dla przepustowosci krawedzi 0-1 do skojarzen dwudzielnych - zlozonosc ma wyjsc taka sama.
Zadanie 2
Sprowadzenie przeplywow dla przepustowosci krawedzi 0-1 do skojarzen dwudzilenych - zlozonosc m^{5/2} jak uzyjemy algorytmu HK.
Zadanie 3
Sprowadznie przeplywow dla przepustowosci krawedzi 0-1 do skojarzen dwudzielnych z zachowaniem planarnosci - zlozonosc moze wzrosnac.
Zadanie 4
Znajdowanie najmniejszego pokrycia wierzcholkowego grafu dwudzielnego.
Zadanie 5
Obliczanie skierowania grafu Pokaz, ze jezeli zachodzi $\frac{|E_H|}{|V_H|} \le d$, dla kazdego podgrafu $H=(V_H,E_H)$ grafu $G$, to wtedy $G$ ma skierowanie, w ktorym kazdy wierzcholek ma stopien wychodzacy co najwyzej $d$. Skierowanie to nadanie krawedziom grafu jednego z dwoch kierunkow.
