7 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 * Zavedení a pochopení grafů, jejich základní pojmy. * Příklady běžných tříd grafů, podgrafy a isomorfismus, souvislost. * Stromy a jejich speciální vlastnosti. Petr Hliněný, Fl MU Brno, 2016 1/27 Fl: IB000: Pojem grafu 7.1 Definice grafu Definice 7.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, 2016 2/27 Fl: IB000: Pojem grafu Stupně vrcholů v grafu Definice 7.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 7.3. Součet stupňů v grafu je vždy sudý, roven dvojnásobku počtu hran. Petr Hliněný, Fl MU Brno, 2016 3/27 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, 2016 4/27 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, 2016 5/27 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, 2016 6/27 Fl: IB000: Pojem grafu Zmínka o zobecněných grafech Všimněme si, že v definici grafu (Def. 7.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; ani zatím nepřisuzujeme hranám žádný směr. V Lekci 9 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, 2016 7/27 Fl: IB000: Pojem grafu 7.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, 2016 8/27 Fl: IB000: Pojem grafu „Stejnost" grafů Definice 7.4. 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 iř jsou isomorfní, G ~ H, pokud mezi nimi existuje isomorfismus. Petr Hliněný, Fl MU Brno, 2016 9/27 Fl: IB000: Pojem grafu 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, 2016 10/27 Fl: IB000: Pojem grafu Příklad 7.5. 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, 2016 11/27 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, 2016 12/27 Fl: IB000: Pojem grafu Další 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, 2016 13/27 Fl: IB000: Pojem grafu 7.3 Souvislost grafů, komponenty 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í 7.6. 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, 2016 14/27 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, 2016 15/27 Fl: IB000: Pojem grafu Definice 7.7. Komponentami souvislosti grafu G nazveme třídy ekvivalence výše popsané (Tvrz. 7.6) 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, 2016 16/27 Fl: IB000: Pojem grafu Definice 7.8. 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, 2016 17/27 Fl: IB000: Pojem grafu ■r 7.4 Stromy - grafy bez kružnic Příklady obrázku stromu následují. Zajímavostí k povšimnutí je, že v informatice stromy typicky rostou „shora dolů"... Charakteristickými znaky stromů je absence kružnic a souvislost. □ Definice 7.9. Strom je (jednoduchý) souvislý graf T bez kružnic. □ Les je graf bez kružnic (jednoduchý, nemusí být souvislý). Komponenty souvislosti lesa jsou stromy. Jeden vrchol bez hran a prázdný graf jsou také stromy. Grafy bez kružnic také obecně nazýváme acyklické. Petr Hliněný, Fl MU Brno, 2016 18/27 Fl: IB000: Pojem grafu Vlastnosti stromů Tvrzení 7.10. Strom s více než jedním vrcholem obsahuje vrchol stupně 1. Důkaz: Souvislý graf s více než jedním vrcholem nemůže mít vrchol stupně 0. Proto vezmeme libovolný strom Tav něm libovolný vrchol v. ^Sestrojíme nyní co nejdelší cestu S y T začínající ve v: * S začne libovolnou hranou vycházející z v; * v každém dalším vrcholu u, do kterého se dostaneme a má stupeň větší než 1, lze pak pokračovat cestu S další novou hranou. Pokud by se v S poprvé zopakoval některý vrchol, získali bychom kružnici. Proto □ cesta S musí jednou skončit v nějakém vrcholu stupně 1 v T. □ Petr Hliněný, Fl MU Brno, 2016 19/27 Fl: IB000: Pojem grafu Věta 7.11. Strom na n vrcholech má přesně n — 1 hran pro n > 1. □ Důkaz: Toto tvrzení dokážeme indukcí podle n. * Strom s jedním vrcholem má n — 1 = 0 hran. * Nechť T je strom na n > 1 vrcholech. Podle Tvrzení 7.10 má T vrchol v stupně 1. Označme T' — T — v graf vzniklý z T odebráním vrcholu v. Pak T' je také souvislý bez kružnic, tudíž strom na n — 1 vrcholech. Dle indukčního předpokladu T' má n — 1 — 1 hran, a proto Tmán —1 — 1 + 1 = n — 1 hran. ^ Petr Hliněný, Fl MU Brno, 2016 20/27 Fl: IB000: Pojem grafu Věta 7.12. Mezi každými dvěma vrcholy stromu vede právě jediná cesta. Důkaz: Jelikož strom T je souvislý dle definice, mezi libovolnými dvěma vrcholy u,v vede nějaká cesta. Pokud by existovaly dvě různé cesty P\^?2 nnezi u,v, tak bychom vzali jejich symetrický rozdíl, podgraf H = P1AP2 s neprázdnou množinou hran, kde H zřejmě má všechny stupně sudé. ^Na druhou stranu se však podgraf stromu musí opět skládat z komponent stromů, a tudíž obsahovat vrchol stupně 1 podle Tvrzení 7.10, což je spor. □ Důsledek 7.13. Přidáním jedné hrany do stromu vznikne právě jedna kružnice. Petr Hliněný, Fl MU Brno, 2016 21/27 Fl: IB000: Pojem grafu Alternativní charakterizace stromů Na dané množině vrcholů je (vzhledem k inkluzi množin hran) strom • minimální souvislý graf (plyne z Věty 7.12) • a zároveň maximální acyklický graf (plyne z Důsledku 7.13). Petr Hliněný, Fl MU Brno, 2016 22/27 Fl: IB000: Pojem grafu Kořenový strom Definice: Strom T s vyznačeným vrcholem r £ V(T), zkráceně dvojice (T, r), nazýváme kořenovým stromem s kořenem r. V přirozeně přeneseném významu se u kořenových stromů používají pojmy rodič, děti/synové, sourozenci, předchůdce, následovník/potomek, atd. Definice: Listem stromu nazveme každý vrchol stupně 1. V kořenovém stromu nazveme listem každý vrchol, který nemá potomky. Petr Hliněný, Fl MU Brno, 2016 23/27 Fl: IB000: Pojem grafu 7.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 7.14. 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, 2016 24/27 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, 2016 25/27 Fl: IB000: Pojem grafu Eulerovské grafy Slibované řešení Příkladu 7.14 od Leonharda Eulera zní takto: Věta 7.15. 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 7.14? 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 7.15 pokrýt jedním uzavřeným tahem (ani otevřeným). Důsledek 7.16. 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, 2016 26/27 Fl: IB000: Pojem grafu Důkaz: Dokazujeme oba směry ekvivalence Věty 7.15. Pokud lze G pokrýt jedním uzavřeným tahem, tak je zřejmě G souvislý a navíc má každý stupeň sudý, neboť uzavřený tah každým průchodem vrcholem pokryje dvě hrany. Naopak zvolíme mezi všemi uzavřenými tahy T obsaženými v G ten (jeden z) nejdelší. Tvrdíme, že T obsahuje všechny hrany grafu G. - Pro spor vezměme graf G' — G — E(T), o kterém předpokládejme, že je neprázdný. Jelikož G' má taktéž všechny stupně sudé, je (z indukčního předpokladu) libovolná jeho komponenta C C G' pokrytá jedním uzavřeným tahem Tq. - Vzhledem k souvislosti grafu G každá komponenta C C G' protíná náš tah T v některém vrchole w, a tudíž lze oba tahy a T „propojit přes w". To je spor s naším předpokladem nejdelšího možného T, neboť T U Tc je delším tahem v G. □ □ Důkaz důsledku: Nechť u, v jsou dva vrcholy grafu G mající lichý stupeň, neboli dva (předpokládané) konce otevřeného tahu pro G. Do G nyní přidáme nový vrchol w spojený hranami s u b v. Tím jsme náš případ převedli na předchozí případ grafu se všemi sudými stupni. □ Petr Hliněný, Fl MU Brno, 2016 27/27 Fl: IB000: Pojem grafu