Zaawansowane algorytmy i struktury danych/Ćwiczenia 7

Zadanie 1

Masz dany graf $G=(V,E)$ wraz z dwoma wybranymi wierzchołkami $s,t\in V$. Pokaż jak używając algorytmu Hopcrofta-Karpa wyznaczyć maksymalną liczbę wierzchołkowo rozłącznych ścieżek z $s$ do $t$. Wierzchołki $s$ i $t$ będą oczywiście wspólne dla tych ścieżek.

Rozwiązanie

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array}{r@{}c@{}l} V^k_{out} &:=& \{v_{out} : v \in V\, \ v\neq s\} \cup \{s_{out}^{i} : 1\le i \le k\},\\ V^k_{in} &:=& \{v_{in} : v \in V\, \ v\neq t\} \cup \{t_{in}^{i} : 1\le i \le k\},\\ E^k_{out,in} &:=& \{v_{out} u_{in} : (v,u) \in V, \ v \neq s,\ u\neq t\} \cup\\ &\cup& \{v_{out}v_{in} : v \in V\}\cup\\ &\cup& \{s_{out}^i u_{in} : (s,u) \in V, \ 1\le i \le k\}\cup\\ &\cup& \{v_{out} t_{in}^i : (v,t) \in V, \ 1\le i \le k\}.\\ \end{array} }

Zadanie 2

Sprowadzenie przeplywow dla przepustowosci krawedzi 0-1 do skojarzen dwudzilenych - zlozonosc m^{5/2} jak uzyjemy algorytmu HK.

Rozwiązanie

Zadanie 3

Sprowadznie przeplywow dla przepustowosci krawedzi 0-1 do skojarzen dwudzielnych z zachowaniem planarnosci - zlozonosc moze wzrosnac.

Rozwiązanie

Zadanie 4

Znajdowanie najmniejszego pokrycia wierzcholkowego grafu dwudzielnego.

Rozwiązanie

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.

Rozwiązanie