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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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 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 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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é při 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, 2018 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, 2018 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, 2018 29/29 Fl: IB000: Pojem grafu