Algoritmické aplikace toků podruhé

Ukažte, jak lze následující úlohy efektivně, tj. v polynomiálním čase, vyřešit (například převedením na standardní úlohu pro nalezení největšího toku v síti).

1. Máme danou tokovou sít s jednotkovými kapacitami. Najděte největší tok takový, že přes každý vrchol krom $z$ a $s$ teče nejvýše jedna jednotka toku.
2. Máme dán (neorientovaný) graf $G = (V, E)$ a dva různé vrcholy $x, y$. Cílem je najít co nejmenší množinu vrcholů $C \subseteq V - \{x, y\}$ takovou, že $x$ a $y$ jsou v různých komponentách grafu $G − C = \left(V - C, E \cap {V-C \choose 2}\right)$. Předpokládejme, že mezi $x$ a $y$ není hrana.
3. Máme dán graf cílem je najít jeho minimální hranový řez, tedy podmnožinu hran takovou, že po jejich odstranění graf není souvislý.
4. Máme dán graf cílem je najít jeho minimální vrcholový řez, tedy podmnožinu vrcholů takovou, že po jejich odstranění graf není souvislý.
5. Máme dánu matici $M$, jejíž prvky jsou nuly a jedničky. Cílem je najít v $M$ co největší množinu jedniček takových, že žádné dvě nejsou ve stejném řádku ani ve stejném sloupci.

Párování a pokrytí v obecných grafech

Označme $m(G)$ velikost největšího párování a $c(G)$ velikost nejmenšího vrcholového pokrytí v grafu $G$.

1. Najděte graf $G$, pro který platí $m(G) < c(G)$.
2. Existuje graf $G$, pro který platí $m(G) + 100 < c(G)$?
3. Ukažte, že pro každý graf platí $m(G) \leq c(G) \leq 2m(G)$.

Hallova věta a spol.

1. Nechť $G$ je bipartitní graf s partitami $A$ a $B$. Předpokládejme, že pro nějaké $k \in \N^+$ platí, že všechny vrcholy partity $A$ mají stupeň aspoň $k$ a všechny vrcholy partity $B$ mají stupeň nejvýš $k$. Ukažte, že G má párování velikosti $|A|$.
2. Dokažte, že každý (nenulově) regulární bipartitní graf má perfektní párování. (Graf je regulární, pokud mají všechny jeho vrcholy stejný stupeň. Párování $P$ je perfektní, pokud každý vrchol patří do nějaké hrany v $P$.)
3. Do mateřské školky přišel Mikuláš a přinesl pytel plný hraček. Každé dítě ukázalo na pět hraček, které se mu líbí. Ukázalo se, že každá hračka se líbí nejvýše pěti dětem. Ukažte, že je možné každému dítěti dát jako dárek některou z hraček, která se mu líbí (přirozeně, každé dítě dostane jinou hračku).
4. Do mateřské školky zase přišel Mikuláš s novým pytlem hraček. Každé dítě tentokrát ukázalo na deset hraček, které se mu líbí. Ukázalo se opět, že každá hračka se líbí nejvýše pěti dětem. Ukažte, že je možné každému dítěti dát jako dárek dvě hračky, které se mu líbí.
5. Nechť $G = (V, E)$ je graf. Předpokládejme, že pro každý podgraf $H$ grafu $G$ platí $|E(H)| \le 10|V(H)|$. Ukažte, že je možné hrany $G$ nahradit orientovanými hranami tak, že do každého vrcholu bude vstupovat nejvýš deset hran.