Matematika III, 12. cvičení
Pojmy k zopakování
• Rovinný graf, Kuratowskeho veta
• Euleruv vztah, Platónska telesa, dualní graf
• Tok v síti, maximalní tok v síti
• Maximalní parovaní v bipartitním grafu
Příklad 247. Rozhodněte, zda je graf daný matici sousednosti A rovinný
( 0   0   1   1   1   1 \
0 0 110 0 110   0 11
1 1 0 0 0 1 10   10   0 1
101110
A =
Příklad 248. Určete, kolik nejvýše hran můžeme přidat do následujícího grafu, aby zůstal rovinný.
Výsledek. 3
Příklad 249. Rozhodnete, jestli graf se skórem (2,3,3,3,3,4,4) je rovinný. Výsledek. Ano
Příklad 250. Rozhodnete, zda jsou uvedené grafý rovinné
Výsledek. Ano,ne.
Příklad 251. Rozhodnete, zdaje uvedený graf rovinný
42
Výsledek. Ne
Příklad 252. Dokažte, ze každý podgraf rovinného grafu je rovinný.
Příklad 253. Necht' d(G) značí dualní graf ke grafu G. Dokažte, že d(d(G)) = G.
Příklad 254. Pomocí Eulerova vztahu dokažte, že je právě pět platýnskych těles.
Příklad 255. Určete všechny úplne tripartitní grafy, ktere jsou rovinne.
Výsledek. Ki,i,n,Ki,2,2
Příklad 256. Uveďte príklad
1. Rovinneho grafu, který není hamiltonovsky.
2. Rovinneho grafu, který je hamiltonovsky.
3. Grafu, ktery nený rovinný, ale je hamiltonovsky.
4. Grafu, ktery nený rovinny ani hamiltonovsky.
5. Rovinneho grafu, který není eulerovský.
6. Rovinneho grafu, který je eulerovský.
7. Grafu, ktery nený rovinny, ale je eulerovský.
8. Grafu, ktery nený rovinny ani eulerovský. Příklad 257. Dokažte, že Petersenův graf nený, rovinný.
Příklad 258. Uvedtte príklad rovinneho grafu na osmi vrcholech, jehoZ komplement je take rovinnýy.
Příklad 259. Urcete velikost maximalního toku ze zdroje z do stoku s.
1
Příklad 260. Urcete velikost maximalního toku ze zdroje z do stoku s.
y	y1		\9
\7 *	s % Á 2		/10
43
Příklad 261. Určete velikost maximálního toku ze zdroje z do stoku s.
12
12
1-I	i-n 3 .t	í-1	í-*1 12
3	i *j -   J »,	! 1	( 1
i      6 »	t *5 l     4 x	t *l	t *l 3 M
)[ n 12	t *J	t *1 ,-4—i	
Příklad 262. Určete velikost maximálního toku ze zdroje z do stoku s, jsou-li dány kapacity jednotlivých vrcholu.
Příklad 263. Doplňte jiZ existující tok ze zdroje z do stoku s na maximální, je-li kapacita kaZde hrany 10.
Příklad 264. Naleznete co nejjednoduZZá príklad, na kterém je vidět, proč je treba hledat vylepšující cesty poučívající hrany v protismeru ve Ford-Fulkersonovč algoritmu.
Příklad 265. Naleznete maximální, parovaní v nísledujícím bipartitním grafu
44
45