Teorie grafů – podzim 2011 – 3. termín
1. (10 bodů) Nalezněte největší párování v následujícím grafu. Svoje tvrzení zdů-
vodněte.
•
OOOOOOOOOOO •

??????? •
ooooooooooo

???????
TTTTTTTTTTTTTTTT •
jjjjjjjjjjjjjjjj

??????? •
jjjjjjjjjjjjjjjj
ooooooooooo

??????? •
jjjjjjjjjjjjjjjj

• • • • • •
2. (10 bodů) Následující graf vyjadřuje pravděpodobnost přechodu systému mezi
stavy A, B, C a D během jednoho kroku. Určete, s jakou pravděpodobností bude
systém začínající ve stavu A ve kterém stavu po čtyřech krocích.
A
1
4

1
4
@@@@@@@@@@@@@@@@@ 1
2
// B
1
2oo
1
2

D
1
4
OO
1
4
??~~~~~~~~~~~~~~~~~
1
2
// C
1
2oo
1
2
OO
3. (5 bodů) Dejte příklad grafu G se šesti vrcholy, který není hamiltonovský a
splňuje κ(G) = 2. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad grafu, který nemá mosty a obsahuje bod artikulace, jehož
stupeň je 3. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad 3-regulárního grafu G, který splňuje χ(G) = 2. Pokud
takový graf neexistuje, zdůvodněte proč.
6. (2 × 5 bodů) Dejte příklad grafu G se skóre (1, 1, 2, 3, 3, 3, 3), který splňuje
a) χ′
(G) = 3.
b) χ′
(G) = 4.
7. (10 bodů) Najděte všechny vzájemně neizomorfní grafy G se šesti vrcholy, které
splňují κ(G) = 1 a κ′
(G) = 2.
8. (8 bodů) Rozhodněte, zda jsou následující dva grafy izomorfní. Svoje rozhodnutí
zdůvodněte.
•

 •
//////////////
????????? •

 •

?????????
•
????????????????? •
 •
TTTTTTTTTTTTTTTTTTTT •

•
????????? •
 •
????????? •

• • • •
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.
•
/////////////
OOOOOOOOOOOOO •
 •

•
OOOOOOOOOOOOO •
ooooooooooooo
• • •
10. (10 bodů) Nechť n ≥ 3 je přirozené číslo a G je graf tvořený cyklem délky n a
dvěma vrcholy u a w, přičemž u i w jsou spojeny hranami se všemi vrcholy grafu.
Určete hranovou a vrcholovou souvislost G, jeho hranové a vrcholové chromatické
číslo a zda je G eulerovský či hamiltonovský.
11. (5 bodů) Definujte vrcholovou souvislost κ(G) grafu G a vysvětlete v definici
použité pojmy.
12. (5 bodů) Formulujte Ramseyho větu pro k barev.
13. (10 bodů) Dokažte, že pro každý graf G, který je souvislý a není úplný, platí
χ′
(G) ≥ χ(G).