8 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, 2017 1/29 Fl: IB000: Pojem grafu 8.1 Definice grafu Definice 8.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, 2017 2/29 Fl: IB000: Pojem grafu Stupně vrcholů v grafu Definice 8.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 8.3. Součet stupňů v grafu je vždy sudý, roven dvojnásobku počtu hran. Petr Hliněný, Fl MU Brno, 2017 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, 2017 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, 2017 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, 2017 6/29 Fl: IB000: Pojem grafu Zmínka o zobecněných grafech Všimněme si, že v definici grafu (Def. 8.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 8.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, 2017 7/29 Fl: IB000: Pojem grafu 8.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, 2017 8/29 Fl: IB000: Pojem grafu „Stejnost" grafů Definice 8.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, 2017 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, 2017 10/29 Fl: IB000: Pojem grafu Příklad 8.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, 2017 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, 2017 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, 2017 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 8.9. Jsou následující dva grafy isomorfní? □ Postupovat budeme jako v Příkladě 8.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, 2017 14/29 Fl: IB000: Pojem grafu 8.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í 8.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, 2017 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, 2017 16/29 Fl: IB000: Pojem grafu Definice 8.12. Komponentami souvislosti grafu G nazveme třídy ekvivalence výše popsané (Tvrz. 8.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, 2017 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, 2017 18/29 Fl: IB000: Pojem grafu Grafová vzdálenost Definice 8.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 (Ig(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 8.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, 2017 19/29 Fl: IB000: Pojem grafu Jednoduché zjištění vzdálenosti Algoritmus 8.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 G 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, 2017 20/29 Fl: IB000: Pojem grafu ■r 8.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 8.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, 2017 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 (P^^u) 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, 2017 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, 2017 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, 2017 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í 8.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 8.20. Silné komponenty orientovaného grafu D jsou třídy ekvivalence relace ~ uvedené v Tvrzení 8.19. Orientovaný graf D je silně souvislý pokud má nejvýše jednu silnou komponentu. Petr Hliněný, Fl MU Brno, 2017 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, 2017 26/29 Fl: IB000: Pojem grafu 8.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 8.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, 2017 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, 2017 28/29 Fl: IB000: Pojem grafu Eulerovské grafy Slibované řešení Příkladu 8.21 od Leonharda Eulera zní takto: Věta 8.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 8.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 8.22 pokrýt jedním uzavřeným tahem (ani otevřeným). Důsledek 8.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, 2017 29/29 Fl: IB000: Pojem grafu