Teorie grafů – podzim 2015 – 3. termín
1. (10 bodů) Určete největší velikost toku v následující síti s danými kapacitami
hran a dvou vrcholů a svoje rozhodnutí zdůvodněte.
• 7 GG/.-,()*+6
3

7 GG•
9
''✽✽✽✽✽✽✽✽✽
'&%$!"#s
9
))❀❀❀❀❀❀❀❀
7 GG
5
ff✝✝✝✝✝✝✝✝✝
•
2
yy
3 GG/.-,()*+8
3
yy
8 GG
3
ÑÑ✄✄✄✄✄✄✄✄ • 2 GG
3

2
yy
'&%$!"#t
•
5
ee✄✄✄✄✄✄✄✄
2
GG•
3
yy
3
ee✄✄✄✄✄✄✄✄✄✄
3
GG•
6
ee✄✄✄✄✄✄✄✄
2. (10 bodů) Určete počet sledů délky 6 v grafu
A B
⑦⑦⑦⑦⑦⑦⑦⑦
C D
3. (5 bodů) Dejte příklad ohodnoceného grafu a jeho vrcholu v takového, že po
spuštění Dijkstrova algoritmu pro vrchol v bude výsledek výpočtu chybný pro
právě polovinu vrcholů grafu. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad 2-souvislého grafu s osmi vrcholy, který není hamiltonovský
a obsahuje dva vrcholy, jejichž vzdálenost je 4. Pokud takový graf neexistuje,
zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G se šesti vrcholy takového, že χ(G) = 3 a žádné
dvě kostry G nejsou izomorfní. Pokud takový graf neexistuje, zdůvodněte proč.
6. (10 bodů) Určete, pro která přirozená čísla x a y je posloupnost
(1, 1, 1, 1, 2, x, 4, y, x + 3)
skórem nějakého grafu, a svoje rozhodnutí zdůvodněte. Pro všechny takové hodnoty
x a y dejte příklad grafu s tímto skóre.
7. (10 bodů) Najděte všechny vzájemně neizomorfní grafy G se sedmi vrcholy, které
jsou hranově 2-souvislé, nejsou 2-souvislé, jsou hranově 4-obarvitelné a každý jejich
blok je hranově 3-obarvitelný.
8. (8 bodů) Rozhodněte, zda jsou následující dva grafy izomorfní. Svoje rozhodnutí
zdůvodněte.
•
⑧⑧⑧⑧⑧⑧⑧⑧⑧
✯✯✯✯✯✯✯✯✯✯✯✯✯✯✯✯✯✯✯✯ •
♦♦♦♦♦♦♦♦♦♦♦♦♦♦
✴✴✴✴✴✴✴✴✴✴✴✴✴✴
❄❄❄❄❄❄❄❄❄ •
⑧⑧⑧⑧⑧⑧⑧⑧⑧
✯✯✯✯✯✯✯✯✯✯✯✯✯✯✯✯✯✯✯✯ •
✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔
✲✲✲✲✲✲✲✲✲✲✲✲✲✲
❁❁❁❁❁❁❁❁❁
•
✴✴✴✴✴✴✴✴✴✴✴✴✴✴ •
❥❥❥❥❥❥❥❥❥❥❥❥❥❥❥❥❥❥❥❥ •
✴✴✴✴✴✴✴✴✴✴✴✴✴✴
❚❚❚❚❚❚❚❚❚❚❚❚❚❚❚❚❚❚❚
❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄ •
❥❥❥❥❥❥❥❥❥❥❥❥❥❥❥❥❥❥❥
•
❄❄❄❄❄❄❄❄❄ •
♦♦♦♦♦♦♦♦♦♦♦♦♦♦
⑧⑧⑧⑧⑧⑧⑧⑧⑧ •
❄❄❄❄❄❄❄❄❄ •
✂✂✂✂✂✂✂✂✂
• • •
✁✁✁✁✁✁✁✁✁✁✁✁✁✁✁✁✁ •
9. (7 bodů) Rozhodněte, zda následující graf je rovinný. Pokud rovinný je, doplňte
jej na maximální rovinný graf. Pokud rovinný není, svoje rozhodnutí zdůvodněte.
•
✴✴✴✴✴✴✴✴✴✴✴ •
⑧⑧⑧⑧⑧⑧⑧
✎✎✎✎✎✎✎✎✎✎✎
❄❄❄❄❄❄❄ •
♦♦♦♦♦♦♦♦♦♦♦
•
❄❄❄❄❄❄❄ •
⑧⑧⑧⑧⑧⑧⑧
❄❄❄❄❄❄❄ •
• • •
10. (10 bodů) Nechť n ≥ 4 a nechť G je obyčejný graf vzniklý odebráním dvou
hran, které nemají společný vrchol, z grafu Kn. Určete hranovou a vrcholovou
souvislost G, jeho hranové a vrcholové chromatické číslo a zda je G eulerovský či
hamiltonovský.
11. (5 bodů) Definujte střed grafu.
12. (5 bodů) Formulujte Ramseyho větu pro k barev.
13. (10 bodů) Dokažte, že pro libovolný graf G = (V, E) platí 2κ′
(G) ≤ κ(G)+|V |−1.