Základní terminologie teorie grafů

Proč to potřebuji?

Teorie grafů je klíčovou součástí diskrétní matematiky a má obrovské množství praktických aplikací — od návrhu počítačových sítí, přes plánování tras, analýzu sociálních sítí, až po optimalizaci databázových dotazů. Grafy jsou univerzální nástroj pro modelování vztahů mezi objekty. V tomto tématu se naučíte základní pojmy, se kterými budeme pracovat po celý semestr.

Předpoklady: Základní znalost množin (sjednocení, průnik, podmnožina). Nic víc nepotřebujete.

1.1 Definice grafu

Definice — Obyčejný graf

Pod pojmem obyčejný graf G rozumíme uspořádanou dvojici G = (V, E), kde:

V je libovolná množina vrcholů
E ⊆ P₂(V) je množina hran
Každá hrana je určena dvěma vrcholy: e = {v_i, v_j}
Počet vrcholů značíme |V| = n, počet hran |E| = m

Jednoduše řečeno

Graf je sbírka teček (vrcholů) a čar (hran), které některé tečky spojují. Žádná hrana nemá smyčku (nespojuje vrchol sám se sebou) a mezi dvěma vrcholy je maximálně jedna hrana.

Příklad — Jednoduchý graf

Graf G = ({a,b,c,d,e}, {ab, ac, bc, bd, ce, de}) — 5 vrcholů, 6 hran

1.2 Reprezentace grafu

Graf můžeme zapsat několika způsoby:

a) Nakreslením

Nejpřirozenější způsob — vrcholy jako body, hrany jako čáry.

b) Matice sousednosti

Definice

Matice sousednosti grafu G s n vrcholy je čtvercová matice A_G = (a_ij) typu n × n:

a_ij = 1 když {v_i, v_j} ∈ E (jsou sousední)
a_ij = 0 když {v_i, v_j} ∉ E

Matice je symetrická, na diagonále jsou nuly.

Příklad — Matice sousednosti

	a	b	c	d	e
a	0	1	1	1	0
b	1	0	1	1	0
c	1	1	0	1	1
d	1	1	1	0	0
e	0	0	1	0	0

Stupeň vrcholu = počet jedniček v řádku. Např. deg(c) = 4, deg(e) = 1.

c) Matice incidence

Definice

Pro graf G s n vrcholy a m hranami je to matice n × m, kde m_ij = 1 když hrana e_j je incidentní s vrcholem v_i, jinak 0.

d) Seznam sousedních vrcholů

Pro každý vrchol vypíšeme jeho sousedy. Např.: a → b, c, d

1.3 Základní pojmy

Koncové vrcholy, incidentnost, sousednost

Hrana e = {v, w}: vrcholy v a w jsou koncové vrcholy hrany e
Vrchol v a hrana e jsou incidentní, když v je koncový vrchol e
Koncové vrcholy hrany jsou sousední
Hrany jsou sousední, když sdílejí společný vrchol

Stupeň vrcholu

Stupeň vrcholu v (značíme deg(v)) je počet hran incidentních s vrcholem v.

Izolovaný vrchol: stupeň 0
Koncový vrchol: stupeň 1

Podgraf, indukovaný podgraf, faktorový podgraf

Podgraf H = (V', E') grafu G: V' ⊆ V, E' ⊆ E (libovolná část)
Indukovaný podgraf: podgraf určený množinou vrcholů — hrany se automaticky vyberou
Faktorový podgraf: podgraf obsahující všechny vrcholy, ale jen některé hrany

Původní graf G

Podgraf

Indukovaný {a,b,c}

1.4 Operace na grafu

Odebrání vrcholu a hrany

G - v: graf získaný odebráním vrcholu v a všech jeho incidentních hran
G - e: graf získaný odebráním hrany e (vrcholy zůstávají)

G - b

G - {a,b}

1.5 Princip sudosti

Věta — Princip sudosti

Když obyčejný graf G má m hran, pak součet stupňů všech vrcholů je roven 2m:

∑_{v ∈ V} deg(v) = 2m

Důsledek: Počet vrcholů lichého stupně v grafu je vždy sudý.

Proč to platí?

Každá hrana spojuje dva vrcholy, takže přispívá ke stupni dvou vrcholů — každá hrana se počítá dvakrát.

Příklad — Použití principu sudosti

Úloha: Graf má 44 hran, 4 vrcholy stupně 5 a ostatní stupně 4. Kolik má vrcholů?

Řešení:

4·5 + (n-4)·4 = 2·44

20 + 4n - 16 = 88

4n = 84 ⇒ n = 21

Příklad — Kamarádky

Úloha: 7 kamarádek si posílá pohledy. Každá poslala 3 pohlednice. Je možné, aby každá dostala pohlednice od těch samých 3 kamarádek, kterým poslala?

Řešení: Takový graf by měl 7 vrcholů všechny stupně 3 (samé liché). Ale podle důsledku principu sudosti musí být počet lichých vrcholů sudý. 7 je liché ⇒ není to možné.

1.6 Skóre grafu (grafová posloupnost)

Definice

Skóre grafu G je uspořádaná posloupnost stupňů všech vrcholů od nejmenšího po největší: (deg(v₁), deg(v₂), ..., deg(v_n))

Věta o skóre (grafové posloupnosti)

Nechť D = (d₁, d₂, ..., d_n) je nerostoucí posloupnost přirozených čísel. Označme D' posloupnost, která vznikne tak, že:

Odebereme poslední (největší) hodnotu d_n
Od předchozích d_n hodnot odečteme 1
Znovu uspořádáme

Pak D je skóre grafu ⇔ D' je skóre grafu.

Postup opakujeme, dokud nedostaneme samé nuly (je skóre) nebo záporné číslo (není skóre).

Příklad — Je (1,1,1,1,2,3,3,4) skóre?

D = (1,1,1,1,2,3,3,4) → odeber 4, sniž předchozí 4 hodnoty o 1:

D' = (1,1,1,0,1,2,2) → uspořádat: (0,1,1,1,1,2,2)

D'' = (0,1,1,1,0,1) → uspořádat: (0,0,1,1,1,1)

D''' = (0,0,1,1,0) → uspořádat: (0,0,0,1,1)

D'''' = (0,0,0,0) — samé nuly ⇒ ANO, je to skóre grafu!

Výsledný graf zpětnou konstrukcí:

Příklad — Je (2,3,3,3,6,6,6,7) skóre?

D = (2,3,3,3,6,6,6,7) → D' = (1,2,2,2,5,5,5) → D'' = (1,1,1,1,4,4) → D''' = (0,0,0,1,3) → D'''' = (0,-1,-1,0)

Obsahuje záporná čísla ⇒ NE, není to skóre grafu!

1.7 Sled, tah, cesta, kružnice

Definice

Sled: konečná posloupnost vrcholů a hran. Hrany i vrcholy se mohou opakovat.
Tah: sled, ve kterém se žádná hrana neopakuje (vrcholy se mohou).
Cesta: otevřený tah, ve kterém jsou všechny vrcholy různé.
Kružnice: uzavřená cesta (začíná a končí ve stejném vrcholu).

Délka sledu/tahu/cesty/kružnice = počet hran!

Zapamatuj si hierarchii

Sled (cokoliv) ⊃ Tah (neopakované hrany) ⊃ Cesta (neopakované vrcholy) ⊃ Kružnice (uzavřená cesta)

Tvrzení

V grafu G existuje cesta z v do w právě tehdy, když existuje sled z v do w.

1.8 Souvislost, komponenty, artikulace, most

Definice

Souvislý graf: mezi libovolnými dvěma vrcholy existuje cesta
Komponenta: maximální souvislý podgraf
Artikulace: vrchol, jehož odebráním se zvýší počet komponent
Most: hrana, jejímž odebráním se zvýší počet komponent (právě o jednu)

Vzdálenost

Vzdálenost dvou vrcholů u, v v souvislém grafu = délka nejkratší u-v cesty.

Důležitá fakta

Koncové vrcholy mostu stupně > 1 jsou artikulace
Vrcholy stupně 0 a 1 nikdy nemohou být artikulací
Odebráním mostu se počet komponent zvýší právě o 1
Odebráním artikulace v se může počet komponent zvýšit až o deg(v) - 1

1.9 Izomorfismus grafů

Definice

Dva grafy G a G' jsou izomorfní, když existuje jednoznačné zobrazení f: V → V' takové, že {x,y} ∈ E ⇔ {f(x), f(y)} ∈ E'. Zobrazení f je izomorfismus.

Příklad — Izomorfní grafy

Graf G

≅

Graf G' (izomorfní)

Oba grafy mají skóre (2,2,2,2,2) — jsou to kružnice C₅. Izomorfismus: 1→a, 2→b, 4→c, 5→d, 3→e.

Jak zjistit, že grafy NEJSOU izomorfní

Mají různý počet vrcholů nebo hran
Mají různá skóre
Jeden obsahuje kružnici délky k, druhý ne
Různé okolí odpovídajících vrcholů

1.10 Kompletní a regulární graf

Definice

Kompletní (úplný) graf K_n: každá dvojice vrcholů je sousední
Regulární graf: všechny vrcholy mají stejný stupeň. r-regulární = každý stupeň je r.

K₃

K₄

K₅

Počet hran kompletního grafu

|E(K_n)| = C(n,2) = n(n-1)/2

Příklad

K₇ má 7·6/2 = 21 hran.

Počet všech grafů na n vrcholech: 2^C(n,2) (každá hrana buď je, nebo není).

1.11 Doplněk grafu

Definice

Doplněk (komplement) grafu G = (V, E) je graf G = (V, E), kde dva vrcholy jsou sousední v G právě tehdy, když nejsou sousední v G.

Graf G

→

Doplněk G̅

Cvičení — Základní terminologie

Úkol 1 — Princip sudosti: Kolik vrcholů obsahuje graf s 21 hranami, 3 vrcholy stupně 4 a ostatními stupně 3?

Princip sudosti: ∑ deg(v) = 2m

3·4 + (n-3)·3 = 2·21

12 + 3n - 9 = 42

3n = 39 ⇒ n = 13

Úkol 2 — Princip sudosti II: Graf má 29 hran, 5 vrcholů stupně 4, 4 vrcholy stupně 5 a ostatní stupně 6. Kolik má vrcholů?

5·4 + 4·5 + (n-9)·6 = 2·29

20 + 20 + 6n - 54 = 58

6n = 72 ⇒ n = 12

Úkol 3 — Skóre grafu: Zjistěte, zda (2,2,2,3,3,4,4) je skóre grafu. Pokud ano, nakreslete graf.

D = (2,2,2,3,3,4,4) → D' = (1,2,2,2,2,3) → D'' = (1,1,1,1,2) → D''' = (0,0,1,1) → D'''' = (0,0,0)

Samé nuly ⇒ ANO, je to skóre

Úkol 4 — Počty v kompletním grafu:

a) Kolik indukovaných podgrafů s 5 vrcholy je v K₉?
b) Kolik cest délky 5 existuje z A do B v K₉?

a) Stačí vybrat 5 z 9 vrcholů: C(9,5) = 126

b) Cesta: A _ _ _ _ B. Vybrat 4 vnitřní vrcholy: 1 · 7 · 6 · 5 · 4 · 1 = 840

Úkol 5 — Fotbalový turnaj: 11 mužstev hraje turnaj. Je možné, aby v určitém čase 6 mužstev odehrálo 4 zápasy, 3 mužstva 3 zápasy a 2 mužstva 2 zápasy?

Skóre by bylo (2,2,3,3,3,4,4,4,4,4,4). Počet lichých vrcholů = 3 (lichý počet!) ⇒ Podle důsledku principu sudosti to není možné.

Kvíz 1: Kolik hran má kompletní graf K₁₀?

a) 40 b) 45 c) 50 d) 90

Správná odpověď: b) 45

Vzorec: |E(K_n)| = n(n-1)/2 = 10·9/2 = 45.

Kvíz 2: Princip sudosti říká, že součet stupňů všech vrcholů je roven...

a) počtu hran b) dvakrát počtu hran c) počtu vrcholů d) dvakrát počtu vrcholů

Správná odpověď: b) dvakrát počtu hran

Princip sudosti: ∑ deg(v) = 2m, kde m je počet hran.

Kvíz 3: Může existovat graf se 7 vrcholy, kde každý vrchol má stupeň 3?

a) Ano b) Ne

Správná odpověď: b) Ne

Všech 7 vrcholů by mělo lichý stupeň (3), tedy počet vrcholů lichého stupně by byl 7, což je liché číslo. To je v rozporu s důsledkem principu sudosti (počet lichých vrcholů musí být sudý).