1   Pojem grafu
Grafy jsou jedním z nejdú ležitejšľch pojmů diskrétní matematiky. Neformálně, graf se skladá z
• vrcholu neboli také uzlů („puntíků")
• a hran („spojnic") mezi dvojicemi vrcholů.
(Pozor, nepleťme si graf s grafem funkce!)
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
• Zavedenia 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í.
1.1   Definice grafu
Definice 1.1. Graf (rozšířeně obyčejný a 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). □
Fakt: Na graf se lze dívat také jako na symetrickou ireflexivní relaci, kde hrany tvoří právě dvojice prvků z této relace. □
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},
1
2
3
4
■r
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:
Cr.
n
Cesta délky n má n + 1 vrcholů spojených za sebou n hranami:
1      2      3      4     ...   n n+í
Úplný graf na n > 1 vrcholech má n vrcholu, všechny navzájem pospojované (tj. celkem (™) hran):
2
Úplný bipartitní graf nam>lan>l vrcholech má m + n vrcholu ve dvou skupinách (partitách), přičemž hranami jsou pospojované všechny m ■ n dvojice z různých skupin:
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 (1g{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 v nakreslené ukázce jsou stupně přímo zapsány u vrcholů.□
Definice: Graf je d-regulární, pokud všechny jeho vrcholy mají stejný stupeň d.
Značení: Nejvyššístupeň v grafu G značíme A(G) a nejnižšíS(G).
Věta 1.3. Součet stupňů v grafu je vždy sudý, roven dvojnásobku počtu hran. □
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ý. C
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.
•jc   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.) □
Věta 1.4. Nechí d\ < < • • • < dn je posloupnost přirozených čísel. Pak existuje graf s n vrcholy stupňů
di, <Í2, ■ ■ ■, dn právě tehdy, když existuje graf s n — 1 vrcholy stupňů
di, <Í2, ■ ■ ■, dn-dn-i,  dn-dn — 1, ■ ■ ■, dn-2 — 1, dn-i — 1 ■
K pochopení 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.)
Příklad 1.5. Existuje graf se stupni vrcholů:
(1,1,1,2,3,4) ?
Dle Věty 1.4 upravíme na (1, O, 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? □
(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:
(1,1,1,1,2,3,4,6,7) ? □
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.
Z
1.3   Podgrafy a Isomorfismus
Definice: Podgrafem grafu G rozumíme libovolný graf H na podmnožině vrcholu V (H) C V(G), který má za hrany libovolnou podmnožinu hran grafu G majících oba vrcholy ve V (H).
Píšeme H C G, tj. stejně jako množinová inkluze (ale význam je trochu jiný). □
Na následujícím obrázku vidíme zvýrazněné podmnožiny vrcholu hran. Proč se vlevo nejedná o podgraf? Obrázek vpravo už podgrafem je.
□
Definice: Indukovaným podgrafem je podgraf H C G takový, který obsahuje všechny hrany grafu G mezi dvojicemi vrcholů z V(H).
Definice 1.6. Isomorfismus grafů G a H
je bijektivní (vzájemně jednoznačné) zobrazení / : V(G) —>• V(H), pro které platí, že každá dvojice vrcholů u,v e 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 ~ iř. □ 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ňů. □
Fakt: Pokud je bijekce / isomorfismem, musí zobrazovat na sebe vrcholy stejných stupňů, tj. d g {v) — <ijy(/(f)). Naopak to však nestačí!
Příklad 1.7. Jsou následující dva grafy isomorfní?
>
Pokud mezi nakreslenými dvěma grafy hledáme isomorfismus, nejprve se podíváme, zda mají stejný počet vrcholů a hran. Mají. Pak se podíváme na stupně vrcholů a zjistíme, že oba mají stejnou posloupnost stupňů 2, 2, 2, 2, 3, 3. □ Takže ani takto jsme mezi nimi nerozlíš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. □
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:
Z
Věta 1.8. Relace „být isomorfní" ~ na třídě všech grafů je ekvivalencí. □
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ů. C
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.
Další grafové pojmy
Značení: Mějme libovolný graf G.
• Podgrafu H C 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. □
• Podgrafu H C G, který je isomorfní nějaké cestě, říkáme cesta v G. □
• Podgrafu H C G, který je isomorfní nějakému úplnému grafu, říkáme /c///ca v G.
• Podmnožině vrcholů X C V(G), mezi kterými nevedou v G vůbec žádné hrany říkáme nezávislá množina X v G. □
• Indukovanému podgrafu iř C G, který je isomorfní nějaké kružnici, říkáme /n-dukovaná kružnice v G.
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.
Příklad 1.9. Jsou následující dva grafy isomorfní?
X
□
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 vycházet, ž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í.
C
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? □
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!)
1.4   Orientované grafy a multigrafy
V některých případech, jako například u toků v sítích, potřebujeme u každé hrany grafu vyjádřit její směr. Tento požadavek přirozeně vede na následující definici orientovaného grafu, ve kterém hrany jsou uspořádané dvojice vrcholů.
Definice 1.10. Orientovaný graf je uspořádaná dvojice D — (V, E), kde i? C VxV. Pojmy podgrafu a isomorfismu se přirozeně přenášejí na orientované grafy.
Značení: Hrana (u,v) (zvaná také šipka) 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) !
Speciálně hrana tvaru (u,u) se nazývá orientovaná smyčka.
Fakt: Orientované grafy odpovídají relacím, které nemusí být symetrické.
Například orientovaná cesta délky n > O je následujícím grafem na n + 1 vrcholech
6       ... n
Definice: Počet hran začínajících ve vrcholu u orientovaného grafu D nazveme výstupním stupněm ďj)(u) a počet hran končících v u nazveme vstupním stupněm ďjj(u).
Různé modely grafu
Při nazírání na graf jako matematický objekt existují dva zásadně odlišné formální pohledy—tzv. sousednostnía incidenční model. Náš výklad dosud mlčky předpokládal první přístup a bude tomu tak i ve zbytku textu.
Přesto by pozorný čtenář měl mít povědomí i o druhém incidenčním modelu grafu, který staví hrany jako samostatné elementy a místo relace sousednosti mezi dvojicemi vrcholů zavádí relaci incidence mezi dvojicí vrchol-hrana.
Definice: Multigraf je uspořádaná trojice M —  (V, E, e), kde V n E —  0 a
e : E —>• (^) U V U (V x V) je incidenční zobrazeníhran.
Značení (^) v definici reprezentuje neorientované hrany, V neorientované smyčky a V x V orientované hrany a smyčky. Smyčky a paralelní hrany lehce ilustruje následující obrázek: