Matematika III, 12. cvičení
Pojmy k zopakování
• Rovinný graf, Kuratowského věta
• Eulerův vztah, Platónská tělesa, duální graf
• Tok v síti, maximální tok v síti
• Maximální párování v bipartitním grafu
Příklad 245. Rozhodněte, zdaje graf daný maticí 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
V i o i i i o /
Příklad 246. 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 247. Rozhodněte, jestli graf se skórem (2,3,3,3,3,4,4) je rovinný. Výsledek. Ano
Příklad 248. Rozhodněte, zda jsou uvedené grafy rovinné
Výsledek. Ano,ne.
Příklad 249. Rozhodněte, zdaje uvedený graf rovinný
42
Výsledek. Ne
Příklad 250. Dokazte, že každý podgraf rovinného grafu je rovinný.
Příklad 251. Nechť d(G) znáči duální graf ke grafu G. Dokažte, že d(d(G)) = G.
Příklad 252. Pomocí Eulerova vztahu dokažte, že je právě pět platónských těles.
Příklad 253. Určete všechny úplné tripartitní grafy, které jsou rovinné.
Výsledek. Äi,i,n, Äi,2,2
Příklad 254. Uveďte příklad
1. Rovinného grafu, který není hamiltonovský.
2. Rovinného grafu, který je hamiltonovský.
3. Grafu, který není rovinný, ale je hamiltonovský. 4- Grafu, který není rovinný ani hamiltonovský.
5. Rovinného grafu, který není eulerovský.
6. Rovinného grafu, který je eulerovský.
7. Grafu, který není rovinný, ale je eulerovský.
8. Grafu, který není rovinný ani eulerovský. Příklad 255. Dokažte, že Petersenův graf není rovinný.
Příklad 256. Uveďte příklad rovinného grafu na osmi vrcholech, jehož komplement je také rovinný.
Příklad 257. Určete velikost maximálního toku ze zdroje z do stoku s.
s
Příklad 258. Určete velikost maximálního toku ze zdroje z do stoku s.
7
4
z
s
7
5
43
Příklad 259. Určete velikost maximálního toku ze zdroje z do stoku s.
1 3	i-»1 3 3	I-»1 3 .1	í-*\ 6 4	\- 12 <     6 ,■
4	I " 3 4	1 1 i     J «	{ *j 4 i    J »	f i 6 4
ň i 12	t *! 4 <> „	t *5 3 -       4 M	t *l 3 3	t *! 4 3
	l *! ů 12	! *5	t *1 3 4	t *! 3
r
Příklad 260. Určete velikost maximálního toku ze zdroje z do stoku s, jsou-li dány kapacity jednotlivých vrcholů.
4 3
Příklad 261. Doplňte již existující tok ze zdroje z do stoku s na maximální, je-li kapacita každé hrany 10.
Příklad 262. Nalezněte co nejjednodušší příklad, na kterém je vidět, proč je třeba hledat vylepšující cesty používající hrany v protisměru ve Ford-Fulkersonově algoritmu.
Příklad 263. Nalezněte maximální párování v následujícím bipartitním grafu
44
Příklad 264. Nalezněte maximální párování v následujícím bipartitním grafu
Příklad 265. Nalezněte maximální párování v následujícím bipartitním grafu
45