Zaawansowane algorytmy i struktury danych/Ćwiczenia 7
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.
