Teorie grafů – podzim 2012 – 3. termín
1. (10 bodů) Použitím některého algoritmu založeného na standardních operacích
s maticemi určete vzdálenosti mezi všemi dvojicemi vrcholů následujícího grafu.
Přitom vrcholy v matici reprezentujte v pořadí v1, v2, v3, v4, v5.
v2
3
~~}}}}}}}}}}}}}
2

5
AAAAAAAAAAAAA
v1
1
>>}}}}}}}}}}}}}
4
//
3
AAAAAAAAAAAAA
v5
1

5
OO
1
// v3
1
``AAAAAAAAAAAAA2oo
6
~~}}}}}}}}}}}}}
v4
2
``AAAAAAAAAAAAA
6
OO
2. (10 bodů) Určete chromatický polynom grafu
• • •

• • •
3. (5 bodů) Dejte příklad grafu se šesti vrcholy, který má až na izomorfismus právě
tři kostry. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad grafu G s devíti vrcholy, který je hamiltonovský a splňuje
χ(G) = 2. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G, který má sedm vrcholů a splňuje κ(G) = 2 a
κ′
(G) = 3. 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, x, 4, 4, y)
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í hranově 2-souvislé grafy s pěti
vrcholy, které neobsahují podgraf izomorfní grafu
•
;;;;;;;; •
• •
8. (8 bodů) Rozhodněte, zda jsou následující dva grafy izomorfní. Svoje rozhodnutí
zdůvodněte.
•
/////////////////////////// •

///////////////////////////
????????????????? •
 •
TTTTTTTTTTTTTTTTTTTT •
jjjjjjjjjjjjjjjjjjj
•
????????? •

•
?????????????????
OOOOOOOOOOOOOOOOOOOOOOOOOOO •
 •
ooooooooooooooooooooooooooo •

?????????
•
 •
<<<<<<<<<
• • • • •
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.
•
///////////
??????? •
??????? •
ooooooooooo

•
OOOOOOOOOOO • •
• • •
10. (10 bodů) Nechť n ≥ 0 je celé číslo a G je obyčejný graf tvořený třemi disjunktními
cestami délky n a dvěma dalšími vrcholy, které jsou oba spojeny hranami
právě se všemi vrcholy těchto tří cest. Určete hranovou a vrcholovou souvislost G,
jeho hranové a vrcholové chromatické číslo a zda je G eulerovský či hamiltonovský.
11. (5 bodů) Definujte tok v síti a jeho velikost.
12. (5 bodů) Formulujte Mengerovu větu o vrcholové souvislosti obyčejných grafů a
vysvětlete v ní použité pojmy.
13. (10 bodů) Dokažte, že pokud obyčejný graf G obsahuje právě jednu kružnici
liché délky, tak každý vrchol této kružnice, který má stupeň alespoň 3, je bodem
artikulace G.