Teorie grafů – ústní část zkoušky – kolokvium (oba texty, Milková i Fuchs, najdete v IS
oskenované):

Budete mít cca 10 minut na přípravu jedné z následujících sedmi otázek:

Otázka č. 1:

Graf – základní definice, skóre grafu (Milková 1.1), izomorfismus grafů (Milková 1.3)

Teoretická podotázka: kolik existuje navzájem neizomorfních grafů na 3 vrcholech, na 4 vrcholech?
(odpověď: Fuchs, str. 121)


Otázka č. 2:

Souvislost a 2-souvislost grafu, komponenty a bloky,

Teoretická podotázka: dokažte větu 1.4 (Milková, str. 21-22): průnik dvou bloků grafu je prazdná
množina nebo jednoprvková množina obsahující artikulaci tohoto grafu


Otázka č. 3:

Kostra grafu (stačí definice, není potřeba algoritmus hledání minimální kostry příliš vysvětlovat);
vrcholová 3-souvislost grafu (definice: odebráním dvou vrcholů a všech hran s nimi incidentních se
stále zachová souvislost vzniklého grafu); příklad 3-souvislého grafu; příklad grafu, který má
stupně všech vrcholů minimálně 3, a přesto není 3-souvislý;

Teoretická podotázka: a) ve skriptech Fuchs, str. 138 je na obrázku chyba (kterou přiznal i autor
doc. Fuchs): graf na obrázku není (vrcholově) 3-souvislý, i když to popis obrázku tvrdí … dokážete
tuto chybu v grafu najít a opravit? b) dokažte větu: graf se sudým stupněm všech vrcholů neobsahuje
most (Milková, str. 40-41)


Otázka č.4:

bipartitní a hamiltonovské grafy (Milková, oddíly 2.1 a 2.2)

Teoretická podotázka: a) co musí graf zhruba splňovat, aby byl hamiltonovský? (viz skripta Fuchs,
najděte nějakou větu … zhruba řečeno: musí mít dostatečný počet hran, čím více hran, tím větší
šance, že hamiltonovská kružnice v grafu existuje); b) nakreslete rovinnou reprezentaci
pravidelného osmistěnu a nalezněte na něm hamiltonovskou kružnici (pokud existuje);  c) nakreslete
příklad grafu se stupni všech vrcholů minimálně 3, který přesto není hamiltonovský;


Otázka č. 5:

Eulerovské grafy, procházení labyrintu, hledání Eulerovského tahu (Milková, oddíly 2.3,2.4 a 3,
kapitola 6 jen Edmonds-Johnsonovo procházení grafu)

Teoretická podotázka: dokažte větu: G je souvislý právě tehdy, když obsahuje aspoň jednu kostru
(Milková str. 61, věta 4.2)


Otázka č. 6:

Rovinné grafy, barvení vrcholů  (Milková, oddíl 2.4 a oddíl 3)

Teoretická podotázka: Dokažte Eulerovu větu pro rovinné grafy (Fuchs, str. 142-143).


Otázka č. 7:

Pravidelné mnohostěny (Fuchs str.145-148) … jen základní info, tj. rovnice 7.2, 7.3, 7.4 na str.
147, a pak nakreslení daných mnohostěnů + vysvětlení, v čem spočívá jejich pravidelnost.

Teoretická podotázka: Jak je možné, že Eulerova věta pro rovinné grafy platí i pro pravidelné
mnohostěny (Fuchs, str. 148: N+R-M=2)? Pokuste se zhruba vykódovat postup z daných stránek skripta
Fuchs a zobrazit krychli do roviny nejprve promítnutím na sféru (Fuchs str. 145 poslední dva řádky
a str. 146 první dva řádky),  a pak stereografickou projekcí sféry na rovinu (Fuchs obrázek na str.
147) – měl by vám vzniknout rovinný graf a mapa (= rozřezání roviny), která odpovídá mapě na
krychli.