Toky a řezy

 

  1. (Operace s tokem)
    Nechť $G=(V,E)$ je síť a $f_1$, $f_2$ jsou toky v $G$ (funkce z $E \to \RR_+$). Rozhodněte jestli jsou následující funkce také tokem v $G$.

    • $f_1 + f_2$.
    • $\alpha f_1$ pro $\alpha \geq 0$.

    Funkce $f_1 + f_2$ je definována jako $(f_1 + f_2)(e) := f_1(e) + f_2(e)$ pro každou hranu $e\in E$ (sčítání po složkách). Podobně $(\alpha f_1)(e) := \alpha f_1(e)$ pro každou hranu $e\in E$.

    Jaké vlastnosti (podmínky) z definice toku mohou být porušeny? Co musí funkce $f_1+f_2$, respektive $\alpha f_1$, splňovat, aby byla tokem?

  2. (Určete maximální tok mřížkou)
    Nechť $G=(V,E)$ je síť tvaru mřížky $5\times5$ s vrcholy $V=\{[x,y]: 1\leq
    x,y\leq 5\}$ a orientovanými hranami $([x,y],[x+1,y])$ a $([x,y],[x,y+1])$ s kapacitami 

    $$c([x,y][u,v])=\frac{1}{\min\{x+y-1,\; 10-x-y\}}. $$

    Určete maximální tok ze zdroje $[1,1]$ do stoku $[5,5]$.


    Nápověda: $\frac{5}{3}$.

  3. (Určete maximální tok mřížkou)
    Nechť $G=(V,E)$ je síť tvaru mřížky $n\times n$ s vrcholy $V=\{[x,y]: 0\leq
    x,y\leq n-1\}$ a orientovanými hranami $([x,y],[x+1,y])$ a $([x,y],[x,y+1])$ s kapacitami 

    $$c([x,y][u,v])=\begin{cases}
    {x+y \choose x}/2^{x+y} & \hbox{pro } x+y \leq n-2 \\
    1 & \hbox{jinak.}\\
    \end{cases}
    $$

    Určete maximální tok ze zdroje $[0,0]$ do stoku $[n-1,n-1]$.


    Nápověda: $2$.

  4. (Určete maximální tok $n$-dimenzionální krychlí)
    Nechť $Q_n$ je orientovaný graf $n$-dimenzionální krychle. Tj. graf jehož vrcholy jsou posloupnosti nul a jedniček délky $n$ a dva vrcholy jsou spojeny hranou, pokud se příslušné posloupnosti liší právě v jedné souřadnici. Hranu orientujeme od posloupnosti s menším počtem jedniček do posloupnosti s větším počtem jedniček. Zvolme zdroj $z=(0,0,\dots,0)$ a stok $s=(1,1,\dots,1)$ a nastavme kapacity všech hran na jedničku.

    1. Nalezněte maximální tok ze zdroje do spotřebiče.
    2. Dokázali byste najít celočíselný tok?
    3. Dokázali byste najít nikde nenulový tok? Tj. aby každou hranou něco teklo.
  5. (Věta o minimálním toku a maximálním řezu)
    Nechť $G=(V,E)$ je orientovaný graf, $c:E\to \RR_+$ je ohodnocení hran, $z$ zdroj a $s$ spotřebič. 

    Hledáme minimální tok $f$ ze zdroje do spotřebiče takový, aby $f(e)\geq c(e)$ pro každou hranu $e\in E$. Hodnota $c(e)$ je minimální přípustný průtok hranou. Podobně hledáme maximální řez $\delta(R)$ určený množinou $R\subseteq V$, který odděluje zdroj od spotřebiče a opačný řez $\delta(\overline{R})$ neobsahuje žádnou hranu (všechny hrany mezi $R$ a $\overline{R}$ vedou směremem z $R$ do $\overline{R}$).

    Dokažte, že platí $$ \max\{c(\delta(R)): \delta(R) \hbox{$(z,s)$-řez takový, že } \delta(\overline{R})=\emptyset\}=$$ $$=\min\{|f|: f \hbox{$(z,s)$-tok takový, že }\;\forall e\in E\;:\; f(e)\geq c(e) \}$$

    Ukažme si příklad, proč je podmínka $\delta(\overline{R})=\emptyset$ z věty nutná. Představme si síť obsahující jen hranu $zs$ a opačnou hranu $sz$, obě s ohodnocením jedna. Nejmenší přípustný tok posílá jednotku toku po jedné hraně tam a po druhé hraně zpátky. Velikost takového toku je nula. Naproti tomu velikost jediného $(z,s)$-řezu je jedna. V tomto případě by “věta bez podmínky” neplatila. Žádný řez nesplňuje podmínku $\delta(\overline{R})=\emptyset$ a proto je velikost maximálního řezu splňujícího podmínku rovna nule.1

    Jako další jednoduchý příklad si rozmyslete tok a řez v síti, kde za $z$ připojíme ještě jednu hranu $zx$ ohodnocenou jedničkou a prohlásíme $x$ za nový a jediný spotřebič.

    Nápověda: Postupujte podobně jako při důkazu věty o maximálním toku a minimálním řezu.

Algoritmy na toky v sítích

  1. Nalezněte maximální tok v síti na obrázku pomocí
    1. Ford-Fulkersonova algoritmu
    2. Edmonds-Karpova algoritmu
    3. Dinicova algoritmu
    4. Dinicova algoritmu s metodou $3$ Indů
    5. Goldbergova Push-Relabel algoritmu.

    Který algoritmus se Vám nejjednodušeji provádí na papíře? Který algoritmus proběhne nejrychleji na počítači?

    Úlohu vyřeště ještě pro síť z tvaru mřížky z příkladu 2 (praktické příklady na začátku). Čím je tato síť speciální?

  2. Pomocí Goldbergova Push-Relabel algoritmu nalezněte maximální tok v následující síti se zdrojem $v_0$ a spotřebičem $v_5$.
    1. Průběh celého algoritmu si odkrokujte. Kolik kroků algoritmus provede? Kolik kroků provede FIFO push-relabel algoritmus. A kolik kroků provede maximum distance push-relabel algoritmus? Výsledky porovnejte. Které pravidlo pro výběr aktivního vrcholu byste si vybrali?
    2. Graf na obrázku je zužující cesta délky $5$. Dokázali byste spočítat, kolik kroků provede která varianta push-relabel algoritmu na zužující se cestě délky $n$?
  3. Profesor Protékal tvrdí, že ve Ford-Fulkersonově algoritmu není potřeba hledat vylepšující cesty používající hrany v protisměru. Nalezněte co nejjednoduší příklad, na kterém profesorovi dokážete, že jeho zjednodušení Ford-Fulkersonova algoritmu nenajde maximální tok.
  4. (Kolik vylepšujících cest stačí?)
    Ukažte, že maximální tok v síti $G=(V, E)$ se dá vždy najít pomocí nejvýše $|E|$ vylepšujících cest. 

    Nápověda: Vylepšující cesty určete až po nalezení maximálního toku.

  5. (Kratší důkaz Edmonds-Karpova algoritmu)
    Dokažte, že v průběhu Edmonds-Karpova algoritmu může každá hrana zmizet ze sítě rezerv nejvýše $n/2$ krát. Z toho dále odvoďte, že Edmonds-Karpův algoritmus provede nejvýše $mn/2$ iterací (vylepšení podél nejkratší vylepšující cesty). Uměli byste ukázat ještě lepší odhad? Dokažte, že každá hrana $uv\in E$ může zmizet ze sítě rezerv nejvýše $n/4$ krát. 

    Nápověda: Co víte o změnách $d_f(u)$ pro hranu $uv\in E$?

  6. (Otázka k algoritmu $3$ Indů)
    Proč musíme tok velikosti $R(v_0)$ protlačovat z vrcholu $v_0$ doprava a pak ještě doleva? Nemohli bychom začít ve zdroji $s$ a protlačovat tok velikosti $R(v_0)$ pouze doprava? 
  7. (Jednotkové kapacity hran)
    Nechť $G=(V,E)$ je síť se zdrojem $s$, spotřebičem $t$ a jednotkovými kapacitami hran. Předpokládejme, že $G$ není multigraf a že ke každé hraně $uv\in E$ existuje opačná hrana $vu\in E$ (pokud ne, tak přidáme hranu s nulovou kapacitou). 

    Budeme zkoumat, jak rychle poběží Dinicův algoritmus těchto sítích.

    1. (Jednoduchý odhad)
      Při hledání toku v čisté síti mají všechny hrany jednotkovou rezervu. Proto při vylepšení toku podél vylepšující cesty odstraním z čisté sítě všechny hrany na této cestě. Na základě toho ukažte, že nalezení blokujícího toku v čisté síti (jedna iterace) bude trvat jen $\OO(m)$. To potom dává časovou složitost celého algoritmu $\OO(nm)$. 
    2. (Lepší odhad)
      Zastavme Dinicův algoritmus po $k$ iteracích. Délka nejkratší cesty ze zdroje do spotřebiče je v tento moment $\ell > k$. Dosud jsme nalezli tok $f_k$ a chtěli bychom nalézt maximální tok $f$. Zbývá nám tedy v síti rezerv najít tok $f_R := f – f_k$.2 Každá vylepšující cesta zlepší tok alespoň o $1$. Zbývá nám tedy najít nejvýše $|f_R|$ vylepšujících cest. Velikost toku lze ze shora odhadnout velikostí libovolného $(s,t)$-řezu. 

      Jak najít vhodný (malý) $(s,t)$-řez? Zkoumejte řezy mezi jednotlivými vrstvami čisté sítě a ukažte, že existuje řez velikosti nejvýše $m/k$. Potom i $|f_R|\leq m/k$.

      Na základě toho odvoďte, že zbývá provédst nejvýše $m/k$ iterací. Celkem algoritmus provede nejvýše $k+m/k$ iterací, což pro volbu $k:=\sqrt{m}$ dává nejvýše $2\sqrt{m}$ iterací. Z bodu (a) víme, že jedna iterace trvá nejvýše $\OO(m)$ a proto je časová složitost Dinicova algoritmu v této síťi $\OO(m^{3/2})$.

    3. (Ještě lepší odhad)
      Myšlenka je podobná jako v předchozí části. Po $k$ iteracích budeme chtít nalézt malý řez. 

      Zkoumejte $(s,t)$-řezy mezi sousedními vrstvami čisté sítě a ukažte, že existuje řez velikosti nejvýše $(n/k)^2$.

      Z toho dostaneme, že algoritmus provede nejvýše $k+(k/n)^2$ iterací, což při volbě $k:=n^{2/3}$ dává časovou složitost celého algoritmu $\OO(n^{2/3}m)$.

      Nápověda: Označme $s_i$ počet vrcholů v $i$-té vrstvě. Ukažte, že existuje $i$ takové, že $s_i + s_{i+1} \leq 2n/k$. Velikost řezu mezi $i$-tou a $(i+1)$-ní vrstvou je rovna počtu hran mezi $s_i$ a $s_{i+1}$ a to je nevýše $s_i \cdot s_{i+1}$.

  8. (Jednotkové kapacity a každý vrchol má vstupní nebo výstupní stupeň $1$)
    Nechť $G=(V,E)$ je síť se zdrojem $s$, spotřebičem $t$ a jednotkovými kapacitami hran. Každý vrchol má vstupní a nebo výstupní stupeň roven jedné. 

    Postupujeme stejně jako v předchozím cvičení. Zastavme Dinicův algoritmus po $k$ iteracích. Ukažte, že existuje vrstva čisté sítě, která má nejvýše $n/k$ vrcholů. Z toho vyvoďte, že zbývá provést nejvýše $n/k$ iterací a že časová složitost Dinicova algoritmu v této síti je $\OO(\sqrt{n}m)$.

  9. (“Bipartitní graf”)
    Dostanete bipartitní graf $G=(A\cup B, E)$. Ke grafu přidáme zdroj a spojíme ho hranou se všemi vrcholy $v\in A$. Podobně přidáme spotřebič a spojíme ho hranou se všemi vrcholy $v\in B$. Všem hranám nastavíme jednotkovou kapacitu. Těmito úpravami jsme dostali síť $G’$. Jaká je časová složitost Dinicova algoritmu puštěného na síť $G’$? 

    Poznámka: Jak jste se dozvěděli v sekci o aplikacích toků v sítích, hledání maximálního toku v síti $G’$ odpovídá hledání maximálního párování v bipartitním grafu.

    Nápověda: $\OO(\sqrt{n}m)$.

  10. (Celočíselné kapacity hran)
    Nechť $G=(V,E)$ je síť se zdrojem $s$, spotřebičem $t$ a celočíselnými kapacitami hran $c(e)\in \{0,1,2,\dots, U\}$ pro každé $e\in E$. Označme $f$ maximální tok v síti $G$. 

    Ukažte, že algoritmus provede nejvýše $|f|$ vylepšení podél vylepšujících cest.

    Jednu zlepšující cestu najdeme v čase $\OO(n)$. Během celého algoritmu zabere hledání vylepšujících cest nejvýše čas $\OO(|f|n)$. Kromě hledání vylepšujících cest ještě provádíme pročišťování čisté sítě. To během jedné iterace zabere čas $\OO(m)$ a celkem během algoritmu zabere čas $\OO(nm)$.

    Ukažte, že v síti $G$ existuje $(s,t)$-řez velikosti nejvýše $Un$. Velikost libovolného toku je menší než velikost libovolného řezu. Proto je celková časová složitost Dinicova algoritmu pro sítě s celočíselnými kapacitami hran $\OO(Un^2 + nm)$.

  11. (Scaling algoritmus)
    Nechť $G=(V,E)$ je síť se zdrojem $s$, spotřebičem $t$ a celočíselnými kapacitami hran $c(e)\in \{0,1,2,\dots, U\}$ pro každé $e\in E$. Nechť $k:=\lfloor \log_2 U \rfloor$, neboli $k$ je počet bitů potřebných k zápisu největší kapacity nějaké hrany. 

    1. Dokažte, že velikost minimálního $(s,t)$-řezu v $G$ je nejvýše $Um$. (Dokonce můžete najít $(s,t)$-řez velikosti nejvýše $Un$.)
    2. Dostanete pevné číslo $K$. Ukažte, že vylepšující cesta s kapacitou alespoň $K$ se dá v síti $G$ nalézt v čase $\OO(m)$, tedy pokud taková cesta existuje.

    Následující modifikace Ford-Fulkersonova algoritmu se dá použít pro hledání maximálního toku v $G$.

    Scaling algoritmus pro maximální tok:
    
    	 $U := max\{c(e)\;|\; e\in E\}$, $k:=\lfloor \log_2 U \rfloor$ 
    	 $f := 0$ (inicializace toku na nulový tok) 
    	 $K := 2^k$ 
    	 while $K\geq 1$ do
    	 	 while existuje vylepšující cesta $P$ kapacity alespoň $K$ do
    	 	 	 vylepši tok $f$ podél cesty $P$
    	 	 $K := K/2$
    	 return $f$
    1. Dokažte, že předchozí scaling algoritmus vrátí maximální tok.
    2. Ukažte, že pokaždé, když probíhá krok $5$, tak je kapacita rezerv na hranách minimálního řezu $G$ nejvýše $2Km$
    3. Dokažte, že vnitřní cyklus na řádcích $6$–$7$ může pro každou hodnotu $K$ proběhnout nejvýše $\OO(m)$ krát.
    4. Z výše dokázaných pozorování vyvoďte, že časová složitost scaling algoritmu pro hledání maximálního toku je $\OO(m^2 \log U)$.
    5. S využitím předchozího cvičení „celočíselné kapacity hran“ ukažte, že časová složitost scaling algoritmu je dokonce jen $\OO(nm\log U)$.
  12. (Updatování maximálního toku)
    Nechť $G=(V,E)$ je síť se zdrojem $s$, spotřebičem $t$ a celočíselnými kapacitami hran. Předpokládejme, že už známe maximální tok v $G$.

    1. Kapacita jedné hrany $uv\in E$ se zvýší o $1$. Navrhněte algoritmus, který v čase $\OO(n+m)$ přepočítá maximální tok.
    2. Kapacita jedné hrany $uv\in E$ se sníží o $1$. Navrhněte algoritmus, který v čase $\OO(n+m)$ přepočítá maximální tok.
  13. (Minimální řez pomocí Goldbergova Push-Relabel algoritmu)
    Předpokládejme, že už jste pomocí Goldbergova Push-Relabel algoritmu nalezli maximální tok v síti $G=(V,E)$. Navrhněte rychlý algoritmus, který nalezne minimální řez. Jak rychle poběží? 
  14. (Speciální případy Push-Relabel algoritmu)
    Analyzujte časovou složitost Golbergova Push-Relabel algoritmu v sítích s následujícími kapacitami hran. Časovou složitost vyjádřete vzhledem k $n$, $m$ a $k$.

    1. Všechny hrany sítě mají kapacitu $1$.
    2. Kapacity všech hran sítě leží v množině $\{1, 2, \dots, k \}$.

    Nápověda: Kolikrát proběhne nenasycující protlačení po hraně $e$ před tím, než se hrana $e$ nasytí?

  15. (Goldbergův Push-Relabel algoritmus)
    Jak by se změnila analýza obecného Golbergova push-relabel algoritmu, kdybychom vrcholy $v$ nezvyšovali až na $\min\{ d(w)\;|\; vw\in E(G_f) \}$ ale vždy jen o $1$? 

Modifikace sítě

V následujících úlohách vymyslete, jak upravit zadanou síť tak, abychom pro vyřešení úlohy mohli použít hledání klasického toku v síti.

  1. Co kdybychom hledali maximální tok v síti s neomezenými kapacitami hran, ale s omezením průtoku skrz vrcholy? Vyslovte a dokažte analogii Ford-Fulkersonovy věty. 
  2. A co kdyby byly kapacity na hranách a i ve vrcholech (omezní průtoku skrz vrchol)?
  3. Jak najít maximální tok v síti, která má několik zdrojů a několik spotřebičů?

Aplikace toků v sítích

 

  1. (Útěk z mřížky)
    Mřížka $n\times n$ je neorientovaný graf s vrcholy $[i,j]$ pro $1\leq i,j \leq n$. Vrcholy, které se liší v právě jedné souřadnici a to o jedna, jsou spojeny hranou. Hranice mřížky obsahuje vrcholy pro které je $i=1$, $i=n$, $j=1$ nebo $j=n$. 





    Dostanete $m\leq n^2$ startovních bodů $(x_1, y_1)$, $(x_2, y_2)$,\dots, $(x_m, y_m)$ ležících v bodech mřížky (černé body na obrázku). Problémem útěku je rozhodnout, jestli ze startovních bodů vede $m$ vrcholově disjunktních cest na hranici mřížky (do $m$ různých bodů na hranici mřízky). Mřížka na obrázku vlevo má řešení, mřížka na obrázku vpravo nemá.

    Navrhněte efektivní algoritmus pro rozhodnutí problému útěku. Analyzujte jeho časovou složitost.

    Nápověda: Síť s $m$ zdroji a $2n-2$ spotřebiči, kde hrany i vrcholy mají kapacitu $1$. Jak tuto síť upravit, abychom mohli použít algoritmus pro hledání maximálního toku?

  2. (Mengerova věta)
    Pomocí toků v sítích najděte:

    1. Maximální množinu hranově disjunktních cest mezi danou dvojicí vrcholů. Jak se dá snadno ukázat, že víc cest neexistuje?
    2. Maximální množinu vrcholově disjunktních cest mezi danou dvojicí vrcholů. Jak se dá snadno ukázat, že víc cest neexistuje?
    3. Dokažte Mengerovu větu. 

      Graf $G$ je hranově (vrcholově) $k$-souvislý právě tehdy když mezi každou dvojicí vrcholů existuje $k$ hranově (vrcholově) disjunktních cest.

  3. (Königova věta)
    Dostenete bipartitní graf $G=(A\cup B, E)$. Pomocí toků v sítích najděte:

    1. Maximální párování v bipartitním grafu $G$. Jak se dá snadno ukázat, že větší párování neexistuje? Párování $M\subseteq E$ je množina disjunktních hran (žádné dvě hrany $M$ nemají společný vrchol). 
    2. Minimální vrcholové pokrytí v bipartitním grafu $G$. Vrcholové pokrytí $S\subseteq V$ je množina vrcholů taková, že pro každou hranu $e\in E$ je $S\cap e\not=\emptyset$.
    3. Dokažte Königovu větu:Nechť $G$ je bipartitní graf. Velikost maximálního párování v $G$ je rovna velikosti minimálního vrcholového pokrytí v $G$.
  4. (Rozvrhování letadel)
    V podsekci [ref]subsection_rozvrhovani_letadel[/ref] jsme řešili rozvrhování letadel pomocí cirkulací. Zkuste úlohu vyřešit přímo převodem na maximální párování v bipartitním grafu. 
  5. (Pokrytí šachovnice dominem)
    Dostanete šachovnici, na které už stojí některé figurky. Rozhodněte, jestli lze všechna prázdná políčka pokrýt kostičkami $1\times 2$? Při pokrytí se kostičky nesmí překrývat. Pokud ne, tak kolik nejvíce políček můžete pokrýt? 
  6. (Rozmístění věží, aby se neohrožovali)
    Dostanete šachovnici, která má místo některých políček díry. Kolik nejvíc věží můžete na šachovnici rozmístit tak, aby se navzájem neohrožovali? Věž se nesmí položit na díru, ale může přes ní útočit. 
  7. (Hallova věta)
    Pomocí věty o minimálním řezu a maximálním toku dokažte: 

    Nechť $Q$ je množina a $(S_1, S_2, \dots S_k)$ je systém jejích podmnožin. Systém různých reprezentantů (SRR) je množina různých prvků $\{q_1, q_2, \dots, q_k\}$ taková, že $q_i\in S_i$ pro $1\leq i\leq k$. Hallova věta říká, že systém podmnožin má SRR právě tehdy když pro každou podmnožinu $I\subseteq \{1, 2, \dots, k\}$ platí $|\cup_{i\in I} S_i| \geq |I|$ (Hallova podmínka).

  8. (Dopravní problém)
    Máme množinu $l$ obchodů $O$ a množinu $k$ továren $P$. Za určité časové období je továrna $i$ schopna vyrobit nejvýše $a_i$ kusů produktu. Obchod $j$ prodá za stejné časové období $b_j$ kusů produktu. Dostaneme bipartitní graf $G=(O\cup P,E)$, kde $ij\in E$ pokud továrna $i$ může zásobovat obchod $j$. Rozhodněte, jestli za zadaných podmínek dokáží továrny dostatečně zásobovat všechny obchody. Případně pro každou továrnu spočítejte, kolik kusů produktu má vyrobit a do kterých obchodů se mají produkty rozvézt. 
  9. (Maximalizace zisku z projektů)
    Jako ředitel firmy plánujete projekty na příští rok. Můžete začít realizovat projekty $P=\{p_1$, $p_2$,\dots, $p_k\}$. K realizaci některých projektů budete potřebovat některé ze zdrojů $Z=\{z_1$, $z_2$,\dots, $z_l\}$. 

    Na realizaci projektu $p_i$ vyděláte částku $r_i$, ale na druhou stranu k realizaci každého projektu $p_i$ potřebujete množinu zdrojů $S_i\subseteq Z$. Každý zdroj $z_j$ pro $1\leq j \leq l$ je spojen s náklady $c_j$. Ale jakmile už zdroj $z_j$ zakoupíme, tak ho můžeme použít ve všech projektech, které ho vyžadují.

    Navrhněte algoritmus, který zjistí, které projekty realizovat, aby byl celkový zisk co největší.

  10. (Dilworthova věta)
    Nechť G je acyklický orientovaný graf. Dva vrcholy jsou nezávislé, pokud neexistuje orientovaná cesta z jedno vrcholu do druhého. Pokrytí grafu řetězci je množina orientovaných cest $\{P_1, P_2, \dots, P_k\}$ taková, že každý vrchol grafu leží na některé cestě $P_i$. Dokažte Dilworthovu věta, která říká, že velikost maximální nezávislé množiny je rovna minimálnímu počtu pokrývajících řetězců. 

    Nápověda: použijte větu o minimálním toku a maximálním řezu (viz cvičení 5 v podsekci příklady na toky).

  11. (Minimální pokrytí cestami)
    Cestové pokrytí3 orientovaného grafu $G=(V,E)$ je množina ${\cal P}$ vrcholově disjunktních cest v $G$ takových, že každý vrchol je obsažen právě v jedné cestě z ${\cal P}$. Někdy jednoduše říkáme, že každý vrchol je “pokryt” právě jednou cestou z ${\cal P}$. Cesty mohou začínat a končit v libovolných vrcholech a mohou mít libovolnou délku (včetně délky $0$). Minimální cestové pokrytí je cestové pokrytí nejmenším možným počtem cest. 

    1. Vymyslete efektivní algoritmus, který dostane orientovaný acyklický graf $G=(V,E)$ a najde jeho minimální cestové pokrytí. 

      Nápověda: Nechť $V=\{ 1,2,3,\dots ,n \}$. Zkonstruujeme orientovaný graf $G’=(V‘,E‘)$, kde $V‘ = \{ x_0, x_1, x_2, \dots, x_n \} \cup \{ y_0, y_1, y_2, \dots, y_n \}$, $E‘ = \{ (x_0,x_i) \,|\, i\in V \} \cup \{ (y_i,y_0) \,|\, i\in V \} \cup \{ (x_i,y_j) \,|\, (i,j)\in E \}$ a pustíme na něj algoritmus pro hledání maximálního toku.

    2. Funguje váš algoritmus i pro obecné orientované grafy? To je, nebude vadit, když $G$ bude obsahovat orientované cykly?
  12. (Orientovaný Eulerovský tah)
    Dostanete orientovaný graf $G=(V,E)$. Orientovaný Eulerovský tah je tah, který prochází každou hranu grafu právě jednou a to po směru hrany. Tah navíc skončí ve steném vrcholu, ve kterém začal (jde o orientovaný “cyklus”, který může projít některé vrcholy vícekrát). 

    1. Ukažte, že graf $G$ obsahuje orientovaný Euleroský tah právě tehdy, když je graf $G$ souvislý a pro každý vrchol $v\in V$ platí $\deg^{+}(v)=\deg^{-}(v)$ (počet šipek vstupujících do vrcholu se rovná počtu šipek vycházejících z vrcholu). 
    2. (Pošťákův problém v orientovaných grafech)
      Pošťák roznáší poštu ve městě, kde jsou samé jednosměrky. Mapa města odpovídá silně souvislému orientovanému grafu $G=(V,E)$ (odevšud se dá dostat kamkoliv). Pošťák potřebuje projít všechny ulice města a roznést poštu. Navrhněte mu takovou trasu, aby se nachodil co nejméně (tj. minimalizujte počet ulic, které bude muset projít vícekrát). 

      Pokud v grafu nebude existovat orientovaný Eulerovský tah, tak bude pošťák muset projít některé hrany dvakrát. Navrhněte algoritmus, který rozhodne, kolik nejméně a které hrany se mají v grafu zdvojit (dostaneme tak multigraf), aby už v grafu existoval orientovaný Euleroský tah.