Petr Hliněný, FI MU Brno 1 FI: MA010: Pojem grafu
1 Pojem grafu
Grafy jsou jedním z nejdůležitějších pojmů diskrétní matematiky. Neformálně, graf se skládá z
* vrcholů neboli také uzlů ("puntíků")
* a hran ("spojnic") mezi dvojicemi vrcholů.
(Pozor, nepleťme si graf s grafem funkce!)
2
Takový graf může vyjadřovat souvislosti mezi objekty, návaznosti, spojení nebo toky, atd. Své
důležité místo v informatice si grafy získaly dobře vyváženou kombinací svých vlastností ­
snadným názorným nakreslením a zároveň jednoduchou zpracovatelností na počítačích.
Stručný přehled lekce
* zavedení a pochopení grafů, jejich základní pojmy,
* příklady běžných tříd grafů,
* stupně vrcholů v grafech,
* podgrafy, isomorfismus grafů a jeho poznání.
Petr Hliněný, FI MU Brno 2 FI: MA010: Pojem grafu
1.1 Definice grafu
Definice 1.1. Graf (rozšířeně obyčejný či jednoduchý neorientovaný graf)
je uspořádaná dvojice G = (V, E), kde V je množina vrcholů a E je množina hran ­
množina vybraných dvouprvkových podmnožin množiny vrcholů.
Značení: Hranu mezi vrcholy u a v píšeme jako {u, v}, nebo zkráceně uv.
Vrcholy spojené hranou jsou sousední.
Na množinu vrcholů grafu G odkazujeme jako na V (G), na množinu hran E(G). 2
Fakt: Na graf se lze dívat také jako na symetrickou ireflexivní relaci, kde hrany tvoří
právě dvojice prvků z této relace. 2
Poznámka: Grafy se často zadávají přímo názorným obrázkem, jinak je lze také zadat výčtem
vrcholů a výčtem hran. Například:
V = {1, 2, 3, 4}, E = {1, 2}, {1, 3}, {1, 4}, {3, 4}
1
2 3 4
Petr Hliněný, FI MU Brno 3 FI: MA010: Pojem grafu
Běžné typy grafů
Pro snadnější vyjadřování je zvykem některé běžné typy grafů nazývat popisnými jmény.
Kružnice délky n má n  3 vrcholů spojených do jednoho cyklu n hranami:
Cn 6
5 2
1
7 . . .
4
n
3
2
Cesta délky n má n + 1 vrcholů spojených za sebou n hranami:
Pn
1 2 3 4 . . . n n + 1
Petr Hliněný, FI MU Brno 4 FI: MA010: Pojem grafu
Úplný graf na n  1 vrcholech má n vrcholů, všechny navzájem pospojované (tj.
celkem n
2 hran):
Kn
1
2
3
4 n. . . 2
Úplný bipartitní graf na m  1 a n  1 vrcholech má m + n vrcholů ve dvou
skupinách (partitách), přičemž hranami jsou pospojované všechny m  n dvojice
z různých skupin:
Km,n
m
n
Petr Hliněný, FI MU Brno 5 FI: MA010: Pojem grafu
1.2 Stupně vrcholů v grafu
Definice 1.2. Stupněm vrcholu v v grafu G
rozumíme počet hran vycházejících z v. Stupeň v v grafu G značíme dG(v).
Slovo "vycházející" zde nenaznačuje žádný směr; je totiž obecnou konvencí říkat, že hrana
vychází z obou svých konců zároveň.
Například tento zakreslený graf má stupně vrcholů 1, 2, 3, 4, 4, 4, 6.2
Značení: Nejvyšší stupeň v grafu G značíme (G) a nejnižší (G).
Věta 1.3. Součet stupňů v grafu je vždy sudý, roven dvojnásobku počtu hran. 2
Důkaz. Při sčítání stupňů vrcholů v grafu započítáme každou hranu dvakrát ­ jednou
za každý její konec. Proto výsledek vyjde sudý. 2
Petr Hliněný, FI MU Brno 6 FI: MA010: Pojem grafu
Vlastnosti stupňů
Jelikož v obyčejném grafu zvlášť nerozlišujeme mezi jednotlivými vrcholy, nemáme dáno
žádné pořadí, ve kterém bychom stupně vrcholů měli psát. Proto si stupně obvykle
seřazujeme podle velikosti.
* Zajímavou otázkou je, které posloupnosti stupňů odpovídají vrcholům skutečných
grafů?
(Například posloupnost stupňů 1, 2, 3, 4, 5, 6, 7 nemůže nastat nikdy.) 2
Věta 1.4. Nechť d1  d2  . . .  dn je posloupnost přirozených čísel. Pak existuje
graf s n vrcholy stupňů
d1, d2, . . . , dn
právě tehdy, když existuje graf s n - 1 vrcholy stupňů
d1, d2, . . . , dn-dn-1, dn-dn - 1, . . . , dn-2 - 1, dn-1 - 1 .
K použití Věty 1.4: Mírně nepřehledný formální zápis věty znamená, že ze seřazené posloupnosti
odebereme poslední (největší) stupeň dn a od tolika dn bezprostředně předchozích stupňů
odečteme jedničky. Zbylé stupně na začátku posloupnosti se nezmění.
(Nezapomeňme, že posloupnost je třeba znovu seřadit dle velikosti.)
Petr Hliněný, FI MU Brno 7 FI: MA010: Pojem grafu
Příklad 1.5. Existuje graf se stupni vrcholů:
(1, 1, 1, 2, 3, 4) ?
Dle Věty 1.4 upravíme na (1, 0, 0, 1, 2), uspořádáme ji (0, 0, 1, 1, 2),
pak znovu (0, 0, 0, 0) a takový graf už jasně existuje.
Na druhou stranu, jak takový graf sestrojíme? 2
(Obvykle není jediný, ale nás zajímá aspoň jeden z nich.) Prostě obrátíme předchozí
postup, začneme z grafu se 4 vrcholy bez hran, přidáme vrchol stupně 2
spojený se dvěma z nich a další vrchol stupně 4 takto:
s s s s s s s s
s
s s s s
s
s 2
(1, 1, 1, 1, 2, 3, 4, 6, 7) ? 2
Podobně upravíme na (1, 0, 0, 0, 1, 2, 3, 5) a uspořádáme ji (0, 0, 0, 1, 1, 2, 3, 5),
pak znovu (0, 0, -1, 0, 0, 1, 2), ale to už přece nelze ­ stupně nejsou záporné.
Proto takový graf neexistuje.
2
Petr Hliněný, FI MU Brno 8 FI: MA010: Pojem grafu
1.3 Podgrafy a Isomorfismus
Definice: Podgrafem grafu G rozumíme libovolný graf H na podmnožině vrcholů
V (H)  V (G), který má za hrany libovolnou podmnožinu hran grafu G majících
oba vrcholy ve V (H).
Píšeme H  G, tj. stejně jako množinová inkluze (ale význam je trochu jiný). 2
Na následujícím obrázku vidíme, co je (vlevo) a co není (vpravo) podgraf. (Zvýrazněny jsou
vybrané podmnožiny vrcholů a hran.)
Definice: Indukovaným podgrafem je podgraf H  G takový, který obsahuje všechny
hrany grafu G mezi dvojicemi vrcholů z V (H).
Petr Hliněný, FI MU Brno 9 FI: MA010: Pojem grafu
Definice 1.6. Isomorfismus grafů G a H
je bijektivní (vzájemně jednoznačné) zobrazení f : V (G)  V (H), pro které platí, že
každá dvojice vrcholů u, v  V (G) je spojená hranou v G právě tehdy, když je dvojice
f(u), f(v) spojená hranou v H.
Grafy G a H jsou isomorfní pokud mezi nimi existuje isomorfismus.
Píšeme G  H. 2
Fakt: Isomorfní grafy mají stejný počet vrcholů (i hran).
Z nakreslených tří grafů jsou první dva isomorfní ­ jsou to jen různá nakreslení "téhož"
grafu, kružnice délky 5. (Určitě snadno najdete isomorfismus mezi nimi. Pro jednoduchost
isomorfismus zakreslete do obrázku tak, že vrcholy prvního očíslujete čísly 1 až 5 a vrcholy
druhého stejnými čísly v pořadí odpovídajícím jeho bijekci.) Třetí graf jim isomorfní není,
neboť, například, má vrcholy jiných stupňů. 2
Fakt: Pokud je bijekce f isomorfismem, musí zobrazovat na sebe vrcholy stejných
stupňů, tj. dG(v) = dH(f(v)). Naopak to však nestačí!
Petr Hliněný, FI MU Brno 10 FI: MA010: Pojem grafu
Příklad 1.7. Jsou následující dva grafy isomorfní?
s s
s s
s s
s s
s s
s s
Pokud mezi nakreslenými dvěma grafy hledáme isomorfismus, nejprve se podíváme, zda
mají stejný počet vrcholů a hran. 2Mají. Pak se podíváme na stupně vrcholů a zjistíme,
že oba mají stejnou posloupnost stupňů 2, 2, 2, 2, 3, 3. 2Takže ani takto jsme mezi nimi
nerozlišili a mohou (nemusejí!) být isomorfní. Dále tedy nezbývá, než zkoušet všechny
přípustné možnosti zobrazení isomorfismu z levého grafu do pravého. 2
Na levém grafu si pro ulehčení všimněme, že oba vrcholy stupně tři jsou si symetrické,
proto si bez újmy na obecnosti můžeme vybrat, že vrchol označený 1 se zobrazí na 1
.
Druhý vrchol stupně tři, označený 4, se musí zobrazit na analogický vrchol druhého
grafu 4
. A zbytek již plyne snadno:
s s
s s
s s
1 4
2 3
6 5
s s
s s
s s
1' 2'
3' 4'
5' 6'
2
Petr Hliněný, FI MU Brno 11 FI: MA010: Pojem grafu
Věta 1.8. Relace "být isomorfní"  na třídě všech grafů je ekvivalencí. 2
Důkaz. Relace  je reflexivní, protože graf je isomorfní sám sobě identickým zobrazením.
Relace je také symetrická, neboť bijektivní zobrazení lze jednoznačně "obrátit".
Tranzitivnost  se snadno dokáže skládáním zobrazení­isomorfismů. 2
Důsledkem je, že všechny grafy se rozpadnou na třídy isomorfismu. V praxi pak, pokud
mluvíme o grafu, myslíme tím obvykle jeho celou třídu isomorfismu, tj. nezáleží nám
na konkrétní prezentaci grafu.
Petr Hliněný, FI MU Brno 12 FI: MA010: Pojem grafu
Další grafové pojmy
Značení: Mějme libovolný graf G.
* Podgrafu H  G, který je isomorfní nějaké kružnici, říkáme kružnice v G.
* Speciálně říkáme trojúhelník kružnici délky 3. 2
* Podgrafu H  G, který je isomorfní nějaké cestě, říkáme cesta v G. 2
* Podgrafu H  G, který je isomorfní nějakému úplnému grafu, říkáme klika v G.
* Podmnožině vrcholů X  V (G), mezi kterými nevedou v G vůbec žádné hrany,
říkáme nezávislá množina X v G. 2
* Indukovanému podgrafu H  G, který je isomorfní nějaké kružnici, říkáme indukovaná
kružnice v G.
Petr Hliněný, FI MU Brno 13 FI: MA010: Pojem grafu
s s
s s
s s
1 4
2 3
6 5
s s
s s
s s
1 4
2 3
6 5
První z ukázaných grafů například neobsahuje žádný trojúhelník, ale obsahuje kružnici
délky 4, dokonce indukovanou. Druhý graf trojúhelník obsahuje a kružnici délky 4
taktéž. První graf obsahuje cestu délky 4 na vrcholech 1, 2, 3, 4, 5, ale ta není indukovaná.
Indukovaná cesta délky 4 v něm je třeba 2, 3, 4, 5, 6. Druhý graf tyto cesty také
obsahuje, ale naopak žádná z nich není indukovaná.
První graf má největší kliku velikosti 2 ­ jedinou hranu, kdežto druhý graf má větší
kliku na vrcholech 3, 4, 5. Největší nezávislá množina u obou grafů má 3 vrcholy 2, 4, 6.
Petr Hliněný, FI MU Brno 14 FI: MA010: Pojem grafu
Příklad 1.9. Jsou následující dva grafy isomorfní?
s s
s s
s s
s s
s s
s s
2
Postupovat budeme jako v Příkladě 1.7, nejprve ověříme, že oba grafy mají stejně
mnoho vrcholů i stejnou posloupnost stupňů 2, 2, 2, 2, 3, 3. Pokud se však budeme snažit
najít mezi nimi isomorfismus, něco stále nebude sedět, že? Co nám tedy v nalezení
isomorfismu brání? Podívejme se, že v druhém grafu oba vrcholy stupně tři mají svého
společného souseda, tvoří s ním trojúhelník. V prvním grafu tomu tak není, první graf
dokonce nemá žádný trojúhelník. Proto zadané dva grafy nejsou isomorfní. 2 2
Poznámka: Výše uvedené příklady nám ukazují některé cesty, jak poznat (tj. najít nebo vyloučit)
isomorfismus dvou grafů. Ty však ne vždy musí fungovat. Čtenář se může ptát, kde
tedy najde nějaký univerzální postup pro nalezení isomorfismu? 2
Bohužel vás musíme zklamat, žádný rozumný univerzální postup není znám a zatím platí, že
jediná vždy fungující cesta pro nalezení či nenalezení isomorfismu mezi dvěma grafy je ve stylu
vyzkoušejte všechny možnosti bijekcí mezi vrcholy těchto grafů. (Těch je, jak známo, až n!)
Petr Hliněný, FI MU Brno 15 FI: MA010: Pojem grafu
1.4 Orientované grafy a multigrafy
V některých případech (například u toků v sítích) potřebujeme u každé hrany vyjádřit
její směr. To vede na definici orientovaného grafu, ve kterém hrany jsou uspořádané
dvojice vrcholů. (V obrázcích kreslíme orientované hrany se šipkami.)
Definice: Orientovaný graf je uspořádaná dvojice D = (V, E), kde E  V × V .
Fakt: Orientované grafy odpovídají relacím, které nemusí být symetrické.
Značení: Hrana (u, v) v orientovaném grafu D začíná ve vrcholu u a končí ve (míří
do) vrcholu v. Opačná hrana (v, u) je různá od (u, v) ! 2
Petr Hliněný, FI MU Brno 16 FI: MA010: Pojem grafu
Navíc někdy můžeme mluvit o tzv. multigrafech, ve kterých padají téměř všechna
omezení na hrany. . .
V multigrafu může mezi dvojicí vrcholů vést libovolný počet hran ­ tzv. násobné hrany,
a některé z nich mohou být i orientované.
Také jsou povoleny hrany, které mají oba konce totožné ­ tzv. smyčky.
Definice: Multigraf je uspořádaná trojice M = (V, E, ), kde V  E =  a
 : E  V
2  V  (V × V ) je incidenční zobrazení hran.
Značení V
2
v definici reprezentuje neorientované hrany, V neorientované smyčky a V × V
orientované hrany a smyčky.
Petr Hliněný, FI MU Brno 17 FI: MA010: Pojem grafu
1.5 Implementace grafů
Mějme jednoduchý graf G na n vrcholech a značme vrcholy jednoduše čísly V (G) =
{0, 1, . . ., n - 1}. Pro počítačovou implementaci grafu G se nabízejí dva základní způ-
soby:
* Maticí sousednosti, tj. dvourozměrným polem g[][], ve kterém g[i][j]=1 znamená
hranu mezi vrcholy i a j.
* Výčtem sousedů, tj. použitím opět dvourozměrné pole h[][] a navíc pole d[]
stupňů vrcholů. Zde prvky h[i][0],h[i][1],...,h[i][d[i]-1] udávají seznam
sousedů vrcholu i.
Poznámka: Dávejte si pozor na symetrii hran v implementaci!
Implementace maticí sousednosti je hezká svou jednoduchostí.
Druhá možnost se však mnohem lépe hodí pro grafy s malým počtem hran, což nastává ve
většině praktických aplikací.
(Navíc je implementace výčtem sousedů vhodná i pro multigrafy.)
Ke grafům lze do zvláštních polí přidat také ohodnocení vrcholů a hran libovolnými čísly či
značkami. . .