PŘÍKLAD 1. [2 body] Existuje graf se skóre (2, 2, 2,4,4, 5, 5)? Pokud ano, nějaký nakreslete,
pokud ne, zdůvodněte proč.
PŘÍKLAD 2. [2 body] Jsou grafy Gl a G2
a) izomorfní?
b) rovinné?
OBRÁZEK 1. Graf Gl
OBRÁZEK 2. GrafG2
PŘÍKLAD 3. [1,5 bodu] Uveďte (nakreslete) příklad neorientovaného grafu, který
a) má aspoň 8 vrcholů, je souvislý, není rovinný a není hamiltonovský,
b) má aspoň 7 vrcholů, není rovinný a je eulerovský,
c) má aspoň 6 vrcholů, je eulerovský a je hamiltonovský.
PŘÍKLAD 4. [1,5 bodu] Nakreslete pěstěný strom daný kódem
000110001100101111.
PŘÍKLAD 5. [3 body] Užitím Ford-Fulkersonova algoritmu najděte maximální tok a minimální
řez v síti dané maticí A, kde vrchol 1 je zdroj a vrchol 8 stok. (Použité nenasycené cesty
schématicky načrtněte mimo graf v pořadí, v jakém je použijete a u každé připište její rezervu.)
/ - 14 - - - 10 18 - \
- - 18 8
10
- - 14 - - - - 20
- - 1 6 - - - - 6
A =
- - - - 1 6 6 - V
7