Teorie grafů – podzim 2011 – 1. termín
1. (10 bodů) Nalezněte všechny kostry nejmenší váhy v grafu
•
1
oooooooooooooo
4
2
yyyyyyyyyyyyyy
•
2
4
ccccccccc •
1

1
ccccccccc •
1
•
3 ccccccccc •
2
1
•
2
3
•
4

• 3
•
2. (10 bodů) Určete chromatický polynom grafu
• •
ccccccc •
• • •
3. (5 bodů) Dejte příklad grafu G, který splňuje κ(G) = 4 a χ′
(G) = 3. Pokud
takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad 3-regulárního grafu G, který splňuje χ(G) = 3. Pokud
takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu, který neobsahuje žádný most a má následující
blokový strom. Pokud takový graf neexistuje, zdůvodněte proč.
• •
cccccccc •

• • •
 •
cccccccc
• • •
6. (2 × 5 bodů) Dejte příklad grafu G se skóre (2, 2, 2, 3, 3, 4), který splňuje
a) κ(G) = κ′
(G).
b) κ(G) = κ′
(G).
7. (10 bodů) Najděte všechny vzájemně neizomorfní grafy G, které mají právě pět
vrcholů a splňují χ(G) = 4.
8. (8 bodů) Rozhodněte, zda jsou následující dva grafy izomorfní. Svoje rozhodnutí
zdůvodněte.
•
 •
ccccccccc •
DDDDDDDDDDDDD
WWWWWWWWWWWWWWWW
hhhhhhhhhhhhhhhhhhh •

DDDDDDDDDDDDD
WWWWWWWWWWWWWWWW •
¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥

DDDDDDDDDDDDD •
zzzzzzzzzzzzzzzzzzz
¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥

• •
•
ccccccccc •
 • • • •
• •
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.
•
ccccccc •

ccccccc •


•
ccccccc •
ccccccc •
ooooooooooo
• • •
10. (10 bodů) Nechť n ≥ 4 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 právě se všemi vrcholy
cyklu. Určete hranovou a vrcholovou souvislost G, jeho hranové a vrcholové
chromatické číslo a zda je G eulerovský či hamiltonovský.
11. (5 bodů) Definujte řez sítě a jeho kapacitu.
12. (5 bodů) Formulujte Eulerův vztah.
13. (10 bodů) Dokažte, že pokud v grafu G neexistuje vrchol stupně většího než 3,
tak počet bodů artikulace G je menší nebo roven dvojnásobku počtu mostů G.