9   Pojem grafu
Třebaže grafy jsou jen jednou z mnoha struktur v matematice a vlastně pouze speciálním případem binárních relací, vydobyly si svou užitečností a názorností (a to především ve vztahu k informatice) důležité místo na slunci.
Neformálně řečeno, graf se skládá z vrcholů (představme si je jako nakreslené „puntíky") a z hran, které spojují dvojice vrcholů mezi sebou.
□
Stručný přehled lekce
* Zavedenia pochopení grafů. Príklady běžných tříd grafů.
* Základní pojmy: podgrafy a isomorfismus, souvislost, vzdálenost.
* Orientované grafy a jejich odpovídající základní pojmy.
Petr Hliněný, Fl MU Brno, 2020
1/29
Fl: IB000: Pojem grafu
9.1   Definice grafu
Definice 9.1. Graf (jednoduchý neorient.) je uspořádaná dvojice G — (V, E), kde V }e konečná množina vrcholů a E je množina hran - množina vybraných dvouprvkových podmnožin množiny vrcholů.
1
2 3 4
Značení: Hranu mezi vrcholy u a v píšeme jako {u,v}, nebo zkráceně uv.
Vrcholy spojené hranou jsou sousední b hrana uv vychází z vrcholů u b v.
Na množinu vrcholů grafu G odkazujeme jako na V(G), na množinu hran E(G).
Grafy se často zadávají přímo názorným obrázkem, jinak je lze formálně zadat výčtem vrcholů a výčtem hran. Například:
V = {1,2,3,4},   E= {{1,2}, {1,3}, {1,4}, {3,4}}
Na graf se lze dívat také jako na symetrickou ireflexivní relaci, kde hrany tvoří právě dvojice prvků z této relace.
Petr Hliněný, Fl MU Brno, 2020
2/29
Fl: IB000: Pojem grafu
Stupně vrcholů v grafu
Definice 9.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 do (v).
Slovo „vycházející" zde nenaznačuje žádný směr; je totiž obecnou konvencí u neorientovaných grafů říkat, že hrana vychází z obou svých konců zároveň.
Definice: Graf je d-regulární, pokud všechny jeho vrcholy mají stejný stupeň dx
Značení: /VejVyss/'stu peň v grafu G značíme A(G) a nejnižší 5{G).
Věta 9.3. Součet stupňů v grafu je vždy sudý, roven dvojnásobku počtu hran.
Petr Hliněný, Fl MU Brno, 2020
3/29
Fl: IB000: Pojem grafu
r
Běžné typy grafů
Kružnice délky n má n > 3 různých vrcholů spojených „do jednoho cyklu" n hranami:
3
C
n
□
Cesta délky n > 0 má n+1 různých vrcholů spojených „za sebou" n hranami:
n
12      3 4
n n+1
Petr Hliněný, Fl MU Brno, 2020
4/29
Fl: IB000: Pojem grafu
r
Úplný graf na n > 1 vrcholech má n různých vrcholů spojených po všech dvojicích (tj. celkem (™) hran): 2
K
n
□
Úplný tripartitní graf na m > 1 a n > 1 vrcholech má m + n vrcholů ve dvou skupinách (partitách), přičemž hranami jsou spojeny všechny m • n dvojice z různých skupin:
K
rn.n
ľ   2' 3'
m
n
Petr Hliněný, Fl MU Brno, 2020
5/29
Fl: IB000: Pojem grafu
Hvězda s n > 1 rameny je zvláštní název pro úplný bipartitní graf
Petr Hliněný, Fl MU Brno, 2020
6/29
Fl: IB000: Pojem grafu
Zmínka o zobecněných grafech
Všimněme si, že v definici grafu (Def. 9.1) vůbec neuvažujeme možnosti vícenásobných hran (mezi stejnou dvojicí vrcholů) a tzv. „smyček" (hrana se stejným jedním koncem) - takovému zobecnění by se říkalo multigraf. Také prozatím nepřisuzujeme hranám žádný směr.
V Oddíle 9.4 si však ještě zavedeme orientované grafy, které každé hraně přiřazují jistý směr. Orientované grafy budou mít množinu orientovaných hran A C V (G) x V (G) a zobrazíme je třeba takto...
□
Petr Hliněný, Fl MU Brno, 2020
7/29
Fl: IB000: Pojem grafu
9.2   Podgrafy a isomorfismus
Definice: Podgrafem grafu G rozumíme libovolný graf H na podmnožině vrcholů 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).
Petr Hliněný, Fl MU Brno, 2020
8/29
Fl: IB000: Pojem grafu
„Stejnost" grafů
Definice 9.6. Isomorfismus ~ grafů G a H
je bijektivní zobrazení / : V{G) —> V(H), pro které každá dvojice u,v G V^(G) je spojená hranou v G právě, když je dvojice f(u),f(v) spojená hranou v H.
Grafy G a H jsou isomorfní, G ~ H, pokud mezi nimi existuje isomorfismus.
Petr Hliněný, Fl MU Brno, 2020
9/29
Fl: IB000: Pojem grafu
Vlastnosti isomorfismu
Fakt: Mějme isomorfismus / grafů G a H. Pak platí následující
* G a H mají stejný počet hran,
* / zobrazuje na sebe vrcholy stejných stupňů, tj. de (v) — dn{f{v))-
U výše zakreslených dvou grafů objevíme isomorfismus velmi snadno - podíváme se, jak si odpovídají vrcholy stejných stupňů. □
Naopak v této trojici grafů (se stejnými počty vrcholů i hran) žádné dva nejsou isomorfní. Proč? nTen vlevo má vrchol stupně 4, čímž se od obou zbylých liší. Prostřední graf pak má jediné dva vrcholy stupně 2 spojené hranou, kdežto v pravém takové dva vrcholy spojené nejsou (isomorfismus by je však i s hranou musel zachovat).
Petr Hliněný, Fl MU Brno, 2020
10/29
Fl: IB000: Pojem grafu
Příklad 9.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. nlvlají. Pak se podíváme na stupně vrcholů a zjistíme, že oba mají stejnou posloupnost stupňů 2, 2, 2, 2, 3, 3. i ] 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 ľ. Druhý vrchol stupně tři, označený 4, se musí zobrazit na analogický vrchol druhého grafu 4'. A zbytek již plyne snadno:
□
Petr Hliněný, Fl MU Brno, 2020
11/29
Fl: IB000: Pojem grafu
Důsledek: Stejnost grafů jako isomorfismus!
Celá
Graf G       <_> třída isomorfismu
grafu G
Je uvedený přístup, tj. zaměňování konkrétního grafu za celou jeho třídu isomorfismu, v matematice neobvyklý? nNe, například už v geometrii jste říkali „čtverec o straně 2" či „jednotkový kruh" a podobně, aniž jste měli na mysli konkrétní obrázek, nýbrž celou třídu všech těchto shodných objektů.
Petr Hliněný, Fl MU Brno, 2020
12/29
Fl: IB000: Pojem grafu
Další (pod)grafové pojmy
Definice: Mějme libovolný graf G.
* Podgrafu H C G, který je isomorfní nějaké kružnici, říkáme kružnice vG.
* 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 klika 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 H C G, který je isomorfní nějaké kružnici, říkáme indukovaná kružnice v G.
Petr Hliněný, Fl MU Brno, 2020
13/29
Fl: IB000: Pojem grafu
Jak poznat neisomorfní grafy
Fakt: Mějme isomorfismus / grafů G a H. Pokud G obsahuje podgraf F, pak H také musí obsahovat podgraf isomorfní F.
Obecněji lze tvrdit, že počet podgrafů v grafu G isomorfních zvolenému F je vždy roven takovému počtu v grafu H.
Příklad 9.9. Jsou následující dva grafy isomorfní?
Postupovat budeme jako v Příkladě 9.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... nCo nám tedy v nalezení isomorfismu brání? nPodívejme se, že v druhém grafu oba vrcholy stupně tři mají svého společného souseda, tvoříš 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í. □
□
Petr Hliněný, Fl MU Brno, 2020
14/29
Fl: IB000: Pojem grafu
9.3   Souvislost, komponenty a vzdálenost
Důležitou globální vlastností grafů je souvislost, tedy možnost se v nich pohybovat odkudkoliv kamkoliv podél jeho hran, neboli po cestách v grafu.
Tvrzení 9.11. Mějme relaci ~ na množině vrcholů V(G) libovolného grafu G takovou, že pro dva vrcholy x ^ y právě když existuje v G cesta začínající v x a končící v y. Pak ~ je relací ekvivalence.
Důkaz.
• Relace ^ je reflexivní, neboť každý vrchol je spojený sám se sebou cestou délky 0.
• Symetrická je také, protože cestu z x do y snadno v neorientovaném grafu obrátíme na cestu z y do x.
• Důkaz tranzitivity však není takto triviální—npokud vezmeme cestu z x do y a cestu z y do z, tak se tyto dvě cesty mohou protínat i jinde než v y a nelze je prostě „navázat" na sebe.
Petr Hliněný, Fl MU Brno, 2020
15/29
Fl: IB000: Pojem grafu
• Zmíněný problém vidíme například zde:
Pro důkaz tranzitivity si označme P cestu z x do y a Q cestu z y do z. Pokud označíme P' C P tu část první cesty z x do prvního vrcholu p v průniku s Q (tj. p G V^(P) fl a označíme Q' C Q zbytek druhé
cesty od p do z, tak P' U Q7 vždy je cestou z x do z.
□
Petr Hliněný, Fl MU Brno, 2020
16/29
Fl: IB000: Pojem grafu
Definice 9.12. Komponentami souvislosti   grafu G nazveme třídy ekvivalence výše popsané (Tvrz. 9.11) relace ^ na V(G).
Jinak se také komponentami souvislosti myslí podgrafy indukované na těchto třídách ekvivalence.
Podívejte se, kolik komponent souvislosti má tento graf:
Vidíte v obrázku všechny tři komponenty? Jedna z nich je izolovaným vrcholem, druhá hranou (tj. grafem isomorfním K 2) a třetí je to zbývající.
Petr Hliněný, Fl MU Brno, 2020
17/29
Fl: IB000: Pojem grafu
Definice: Graf G je souvislý pokud je G tvořený nejvýše jednou komponentou souvislosti, tj. pokud každé dva vrcholy G jsou spojené cestou.
Který z těchto dvou grafů je souvislý?
Petr Hliněný, Fl MU Brno, 2020
18/29
Fl: IB000: Pojem grafu
Grafová vzdálenost
Definice 9.14. Vzdálenost dc{u,v) dvou vrcholů u,v v grafu G je dána délkou nej kratší cesty mezi u a v v G.
Pokud cesta mezi u,v neexistuje, je vzdálenost definována dc{u,v) — oo.
Neformálně řečeno, vzdálenost mezi u, v je rovna nej menším u počtu hran, které musíme překonat, pokud se chceme dostat z u do v. Speciálně vždy platí dc(u,u) = 0 a dále dc{u^v) = oo právě když u,v patří různým komponentám souvislosti.
	1-•-—>
i-.	1^--•-
Fakt: V neorientovaném grafu je vzdálenost symetrická, tj. dc{u^v) — dciy^u).
Lema 9.15. Vzdálenost v grafech splňuje trojúhelníkovou nerovnost:
Mu, v, w G V(G) :   dc{u, v) + dc{v, w) > dc{u, w).
Petr Hliněný, Fl MU Brno, 2020
19/29
Fl: IB000: Pojem grafu
Jednoduché zjištění vzdálenosti
Algoritmus 9.17. Určení vzdáleností z vrcholu u grafu G.
Pro daný souvislý graf G a jeho vrchol u určíme vzdálenosti d(u, x) do každého vrcholu x £ V (G) následujícím postupem.
1. Na začátku položíme d{u,u) \— 0. □
2. Pro i — 0,1, 2,... , přesněji dokud nejsou urč. všechny vzdál., provádíme: Pro každou hranu xy G E (G) takovou, že d{u,x) = z a d{u,y) je dosud neurčená, položíme d{u,y) \— i + 1.
2 3    ...      i      i + \
Petr Hliněný, Fl MU Brno, 2020
20/29
Fl: IB000: Pojem grafu
■r
9.4   Základní pojmy orientovaných grafů
Požadavek explicitně vyjádřit směr hrany přirozeně vede na následující definici orientovaného grafu, ve kterém hrany jsou uspořádané dvojice vrcholů.
Definice 9.18. Orientovaný graf je usp. dvojice D = (V, E), kde E C V xV\.
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. Orientované grafy odpovídají relacím, které nemusí být symetrické.
□
Petr Hliněný, Fl MU Brno, 2020
21/29
Fl: IB000: Pojem grafu
• Orientovaná cesta délky n > O je následujícím grafem na n + 1 vrcholech
n
n + 1
Definice: Počet hran začínajících ve vrcholu u orientovaného grafu D nazveme výstupním stupněm d^iu) a počet hran končících v u nazveme vstupním stupněm dljj{u).
Součet všech výstupních stupňů je přirozeně roven součtu všech vstupních stupňů.
Petr Hliněný, Fl MU Brno, 2020
22/29
Fl: IB000: Pojem grafu
Souvislost na orientovaných grafech
Uvedeme si odstupňovaně tři základní pohledy na orientovanou souvislost:
• Slabá souvislost.   Jedná se o tradiční souvislost na symetrizaci grafu D (tj. po „zapomenutí" směru šipek).
®-•-s>-*-<£--•-$>-®
□
• Dosažitelnost (směrem „ven"). Orientovaný graf i? je dosažitelný směrem ven, pokud v něm existuje vrchol v £ V (D) takový, že každý vrchol x £ V (D) je dosažitelný orientovanou cestou z v.
Petr Hliněný, Fl MU Brno, 2020
23/29
Fl: IB000: Pojem grafu
Podrobným zkoumáním následujícího obrázku zjistíme, že jeho graf není dosažitelný směrem ven, neboť chybí možnost dosáhnout vrchol b úplně vpravo. Na druhou stranu po vypuštění b je zbylý graf dosažitelný ven z vrcholu a vlevo.
Petr Hliněný, Fl MU Brno, 2020
24/29
Fl: IB000: Pojem grafu
Souvislost na orientovaných grafech, silná
• Silná souvislost. V nejsilnější verzi vyžadujeme současnou existenci spojení (cest) v obou směrech mezi dvojicí vrcholů.
Tvrzení 9.19. Necht ^ je binární relace na vrcholové množině V{D) orientovaného grafu D taková, že
• u ~ v právě když existuje dvojice orientovaných cest - jedna z u do v a druhá z v do u v grafu D.
Pak ^ je relace ekvivalence.
Definice 9.20. Silné komponenty orientovaného grafu D jsou třídy ekvivalence relace ~ uvedené v Tvrzení 9.19.
Orientovaný graf D je silně souvislý pokud má nejvýše jednu silnou komponentu.
Petr Hliněný, Fl MU Brno, 2020
25/29
Fl: IB000: Pojem grafu
■r
Pro ilustraci si mírně upravíme dříve prezentovaný orientovaný graf tak, že bude dosažitelný z nejlevějšího vrcholu. Je výsledek silně souvislý?
Ne, na obrázku jsou vyznačené jeho 4 silné komponenty.
Zároveň uvádíme pro ilustraci obrázek kondenzace silných komponent tohoto grafu, což je acyklický orientovaný graf s vrcholy reprezentujícími zmíněné silné komponenty a směry hran mezi nimi.
Petr Hliněný, Fl MU Brno, 2020
26/29
Fl: IB000: Pojem grafu
9.5   Dodatek: 7 mostů jedním tahem
Pravd, nejstaršízaznamenaný výsledek teorie grafů pochází od L. Eulera -slavný problém 7 mostů v Královci / Kónigsbergu / dnešním Kaliningradě.
0 jaký problém se 7-mi mosty se tehdy v Kónigsbergu 18-tého století jednalo?
Příklad 9.21. Je možné pri jedné procházce suchou nohou přejít po každém ze sedmi vyznačených mostů v Kónigsbergu právě jednou?
Petr Hliněný, Fl MU Brno, 2020
27/29
Fl: IB000: Pojem grafu
Sled a tah v grafu
Definice: Sledem délky n v grafu G rozumíme posloupnost vrcholů a hran ve které vždy hrana    má koncové vrcholy ví-\,v\.
Všimněte si, že sled je vlastně jakákoliv procházka po hranách grafu z u do v. Příkladem sledu může být průchod IP paketu internetem (včetně cyklení). □
Definice: Tah je sled v grafu bez opakování hran.
Uzavřený tah je tahem, který končí ve vrcholu, ve kterém začal. Otevřený tah je tahem, který končí v jiném vrcholu, než ve kterém začal.
Jistě znáte dětskou hříčku s „kreslením domečku jedním tahem"... Ano, to je v podstatě totéž, co tah v grafu (kterým „kreslíme" hrany našeho grafu).
Fakt: Cesta je přesně otevřený tah bez opakování vrcholů. Kružnice je přesně uzavřený tah bez opakování vrcholů.
Petr Hliněný, Fl MU Brno, 2020
28/29
Fl: IB000: Pojem grafu
Eulerovské grafy
Slibované řešení Příkladu 9.21 od Leonharda Eulera zní takto:
Věta 9.22. Graf G lze pokrýt (nakreslit) jedním uzavřeným tahem právě když G je souvislý a všechny vrcholy v G jsou sudého stupně.
A jak je tomu v Příkladu 9.21? Zde nejprve nakreslíme příslušný (multi)graf, ve kterém vrcholy jsou jednotlivé kusy země oddělené vodou (tj. dva říční ostrovy a dva břehy):
Jaké jsou stupně vrcholů tohoto grafy? Je to 3, 3, 3,5, neboli všech 7 hran-mostů města Kónigsbergu nelze dle Věty 9.22 pokrýt jedním uzavřeným tahem (ani otevřeným).
Důsledek 9.23. Graf G lze pokrýt (nakreslit) jedním otevřeným tahem právě když G je souvislý a všechny vrcholy v G až na dva jsou sudého stupně.
Petr Hliněný, Fl MU Brno, 2020
29/29
Fl: IB000: Pojem grafu