KG1 Jiří Kalvoda: Cvičení 7

Also available as: PDF Markdown

Informace k cvičení jsou na https://kam.mff.cuni.cz/~jirikalvoda/vyuka/24z/kg1.

Projektivní roviny

Připomeňme, že projektivní rovina byla definovaná jako hypergraf $(X, {\cal P})$ splňující trojici axiomů:

Pro každé dva různé vrcholy $x, y \in X$ existuje právě jedna hyperhrana $p \in {\cal P}$ , která je oba obsahuje.
Pro každé dvě různé hyperhrany $p, q \in {\cal P}$ platí $|p \cap q| = 1$ .
Existuje čtyřprvková množina vrcholů $C$ , jejíž žádné tři vrcholy neleží ve společné hyperhraně.

Konstrukce

Nechť $p$ je prvočíslo a $[p] = \{0,1,\dots, p-1\}$ . Uvažme množinu trojic $[p]^3-\{(0,0,0)\}$ . Na této množině zavedeme ekvivalenci $(x_1, y_1, z_1) \sim (x_2, y_2, z_2)$ právě tehdy když existuje $\alpha \in \{1,2,\dots, p-1\}$ takové, že: $x_1 \equiv \alpha \cdot x_2 \qquad y_1 \equiv \alpha \cdot y_2 \qquad z_1 \equiv \alpha \cdot z_2 \qquad ({\rm mod}\ p).$ Množinu všech tříd ekvivalence $\sim$ ozmačíme $X$ .

Definujeme ${\cal P} = \{\{(x,y,z) \mid (x,y,z)\in [p]^3, ax+by+cz \equiv 0 \ ({\rm mod}\ p) \} \mid (a,b,c)\in [p]^3-\{(0,0,0)\}\}$ .

Ověřte, že $\sim$ je skutečně relace ekivalence.
Ověřte, že $(X, {\cal P})$ je projektivní rovina. Nejprve nahlédněte, že vnitřní množina v definici ${\cal P}$ se skládá vždy z celých tříd ekivalence $\sim$ . Dále si rozyslete, že pro různá $a,b,c$ ze stejne třídy ekvivalence $\sim$ dosteneme stejnou množinu bodů (tedy pro jednu třídu ekvivalence máme jen jednu přímku). Nakonec ověřte axiomy projektivní roviny.

Aplikace

Ukažte, že existuje graf s nejvýše $n$ vrcholy s alespoň $\Omega(n^{3/2})$ hranami, který neobsahuje cyklus na čtyřech vrcholech.

Toky

Toková síť $(V, E, z, s, c)$ je uspořádaná 5-tice, kde $(V,E)$ je orientovaný graf, $z$ je zdroj, $s$ je stok a $c:E\rightarrow \R_0^+$ je funkce kapacit hran.

Tok v této síti je $f:E\rightarrow \R_0^+$ tž:

$\forall e\in E: f(e) \le c(e)$
$\forall x\in V-\{z,s\}: f[{\rm In}(x)] = f[{\rm Out}(x)]$ .

Velikost toku je $f[{\rm Out}(z)] - f[{\rm In}(z)] = f[{\rm In}(s)] - f[{\rm Out}(s)]$ .

Řez $R$ v takovéto síti je podmnožina $R\subseteq E$ tž. v grafu $(V, E-R)$ neexistuje orientovaná cesta ze $z$ do $s$ .

Zlepšující cesta pro tok $f$ je taková cesta ze $z$ do $s$ složená z dopředných i zpětných hran taková, že pro každou dopřednou $e$ na ní platí $f(e) < c(e)$ a zpětnou $e'$ platí $f(e')>0$ .

Párování v grafu $G$ je podmnožina hran taková, že žádně dvě nesdílí společný vrchol.

Vrcholové pokrytí v grafu $G$ je podmnožina vrcholů taková, že pro každou hranu $G$ platí, že obsahuje alespoň jeden vrchol pokrytí.

Lemátka

Dokažte/nahlédněte následujíci lemátka, které jste na přednášce používali bez důkazu:

Tok, který má zlepšující cestu, není maximální.
Pokud $M$ je párování a $C$ je vrcholové pokrytí v nějakém grafu, tak $|M| \le |C|$ .

Algoritmické aplikace toků

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).

Máme dánu tokovou síť $(V, E, z, s, c)$ , cílem je najít její minimální $zs$ -řez.
Máme dánu tokovou síť, kde ovšem místo jednoho spotřebiče $s$ je několik spotřebičů $s_1 , s_2 , \dots , s_k$ a jeden zdroj $z$ . Rozdíl oproti běžné síti je jen v tom, že pro žádný z vrcholů $z, s_1 , s_2 , \dots , s_k$ nepožadujeme, aby se v nich zachovával tok. Cílem je najít maximální tok v této síti. (Velikost toku definujeme obvyklým způsobem, tedy jako rozdíl mezi tím, co vytéká ze zdroje, a tím, co do zdroje přitéká.)
Máme dánu tokovou síť $(V, E, z, s, c)$ a hranu $e \in E$ , cílem je najít tok $f$ (ne nutně maximální) takový, že $f(e)$ je co největší.
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.