Teorie grafů
(Neorientovaný) graf je uspořádaná dvojice (V, E), kde V je množina vrcholů a E je množina
hran. Zapisujeme G = (V, E). Hrany jsou tvaru {u, v}, kde u, v ∈ V .
Matice sousednosti grafu G o n vrcholech v1, v2, . . . , vn je čtvercová matice (aij)n
i,j=1, jejíž
prvky jsou definovány předpisem
aij =
1 pokud {vi, vj} ∈ E
0 jinak
Podgraf grafu G = (V, E) je graf H = (V , E ), kde V ⊆ V a E ⊆ E, tedy H je vytvořen
z G odebráním několika vrcholů a několika hran, přičemž pro každý odebraný vrchol musíme
odebrat i všechny hrany s ním incidentní. Pokud je graf H vytvořen pouze pomocí odebrání
několika vrcholů a všech hran s nimi incidentními, hovoříme o podgrafu indukovaném.
Úplný graf je takový graf, kde jsou každé dva vrcholy spojeny hranou. Úplný graf o n vrcholech
se značí Kn.
Bipartitní graf je graf G = (V, E), kde množinu V lze rozdělit na dvě části, na množiny V1, V2
takové, že z vrcholů množiny V1 mohou vést hrany pouze do vrcholů z množiny V2 a naopak.
O takovém grafu řekneme, že je úplný bipartitní, jestliže z každého vrcholu V1 vede hrana do
každého vrcholu V2 a opačně. Pokud platí |V1| = m a |V2| = n, pro nějaká m, n ∈ N, značí se
úplný bipartitní graf mezi V1 a V2 jako Km,n.
Grafy G = (V, E) a H = (W, F) nazveme izomorfními, jestliže existuje bijektivní zobrazení
f : V → W takové, že pro všechna u, v ∈ V platí {u, v} ∈ E ⇐⇒ {f(u), f(v)} ∈ F.
Stupeň vrcholu v grafu G je počet hran grafu, které tento vrchol obsahují. Značí se DegG(v).
Tah v grafu je posloupnost vrcholů a hran (v1, e1, v2, e2, . . . , en−1, vn), kde pro i = 1, 2, . . . , n
jsou vi vrcholy grafu a pro i = 1, 2, . . . , n − 1 jsou {vi, vi+1} = ei navzájem různé hrany grafu.
Cesta v grafu je tah, ve kterém se neopakují vrcholy.
Graf je souvislý, jestliže pro každé jeho dva vrcholy u, v existuje cesta z u do v. Komponentou
grafu nazýváme každý jeho maximální souvislý podgraf. Hranu nazveme mostem, jestliže se po
jejím odstranění zvýší počet komponent grafu o 1.
Eulerovský graf je takový graf, ve kterém je každý vrchol sudého stupně.
Platí, že graf lze nakreslit jedním uzavřeným tahem právě tehdy, když je souvislý a eulerovský.
Graf lze nakreslit jedním (ne nutně uzavřeným) tahem, neobsahuje-li žádné vrcholy lichého
stupně nebo obsahuje-li právě dva vrcholy lichého stupně.
Kružnicí v grafu rozumíme posloupnost (v1, e1, v2, e2, . . . , en−1, vn = v1), ve které pro i =
1, 2, . . . , n − 1 jsou vi po dvou různé vrcholy grafu a {vi, vi+1} = ei jsou hrany grafu.
Strom je souvislý graf neobsahující kružnici.
Kostra grafu G = (V, E) je libovolný souvislý podgraf H = (V, F), který neobsahuje kružnici.
Ohodnocení grafu G = (V, E) je zobrazení w: E → R. Ohodnocený graf se pak značí G =
(V, E, w).
Minimální kostra ohodnoceného grafu je taková kostra, která má mezi všemi kostrami daného
grafu minimální součet ohodnocení hran. Minimální kostra nemusí být určená jednoznačně.
(Vrcholové) obarvení grafu je přiřazení jedné barvy každému vrcholu tak, aby žádné dva vrcholy
obarvené stejnou barvou nebyly spojeny hranou. Podobně lze definovat hranové obarvení,
kde požadujeme, aby hrany obarvené stejnou barvou neměly společný vrchol.
Graf je rovinný, jestliže jde nakreslit do roviny tak, aby se žádné jeho hrany neprotínaly.
Orientovaný graf je uspořádaná dvojice G = (V, E), kde V je množina vrcholů a E je množina
hran tvaru (u, v) pro u, v ∈ V . Orientovaný graf je souvislý, jestliže pro každou dvojici vrcholů
u, v ∈ V existuje cesta z u do v nebo z v do u.
Příklady:
1. Určete, které dva z těchto tří grafů jsou navzájem izomorfní:
•1
•
2 3
•
•4
•5
•
6
•1
• 3
•
•4
2
•5
•6
•1 •2
•
•
•5
3
4
•
6
2. Kolik různých kružnic obsahuje tento graf?
•
• • •
•
3. Dejte příklad grafu, který splňuje následující (nebo zdůvodněte, proč neexistuje):
(a) má 1 komponentu, 3 vrcholy a je nesouvislý,
(b) skládá se ze 2 komponent a 3 vrcholů,
(c) má 5 vrcholů a obsahuje právě 3 kružnice,
(d) má 4 vrcholy se stupni 3,2,2,2,
(e) má 4 vrcholy se stupni 2,2,2,2.
2
4. Nalezněte až na izomorfismus všechny kostry tohoto grafu:
• •
•
• •
5. Nalezněte 3 navzájem neizomorfní souvislé Eulerovské grafy o šesti vrcholech.
6. Najděte až na izomorfismus všechny grafy, které splňují tyto podmínky:
(a) graf má 3 vrcholy,
(b) graf obsahuje právě 5 vrcholů, 5 hran a 1 kružnici,
(c) graf má 4 vrcholy, lze obarvit 4 barvami ale ne 3 barvami,
(d) graf je souvislý, má 4 vrcholy a nelze nakreslit jedním tahem,
(e) graf má 4 vrcholy a není rovinný.
3