Matematika III - 7. přednáška Teorie grafů - základní pojmy Michal Bulant Masarykova univerzita Fakulta informatiky 30. 10. 2007 IMMiiJMLSSm Q Základní pojmy teorie grafů • Dva příklady • Základní definice • Galerie jednoduchých grafů (Iso)Morfismy grafů a podgrafy • Morfismy • Podgrafy • Stupně uzlů a skóre grafu Q Algoritmy a reprezentace grafů • Grafové algoritmy • Martin Panák, Jan Slovák, Drsná matematika, e-text. 9 Předmětové záložky v IS MU • Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. • Petr Hliněný, Teorie grafů, studijní materiály, http://www.fi.muni.cz/~hlineny/Vyuka/GT/ • Donald E. Knuth, The Stanford GraphBase, ACM, New York, 1993 (http://www-es-facuity.stanford.edu/~knuth/sgb.html). Příklad Na večírku se někteří návštěvníci po dvojicích znají a jiné dvojice se naopak neznají. Kolik lidí musíme pozvat, abychom zaručili, že se alespoň tři hosté budou buď navzájem znát nebo neznát? Představíme situaci pomocí obrázku. Puntíky nám představí jednotlivé hosty, plnou čarou spojíme ty dvojice, které se znají, čárkovanou ty ostatní. Naše tvrzení pak zní: při jakém počtu puntíků vždy nejdeme trojúhelník, jehož strany jsou buď všechny plné nebo všechny čárkované? Na levém obrázku takový trojúhelník není, uprostřed je. Pravý naznačuje důkaz, že existuje vždy, když počet hostů bude alespoň šest. Představme si krabičku, která požírá jeden bit za druhým podle toho, jestli dveřmi zrovna prošel muž nebo žena -jednička nechť označuje třeba ženu. Přitom svítí buď modře nebo červeně podle toho, zda byl poslední bit nula nebo jednička (a bodle barvy světla tedy poznáme, zda je za dveřmi muž nebo žena. Znázorníme funkci schématem: CÄ3' Třetí uzel, ze kterého pouze vychází dvě šipky naznačuje start před prvním zaslaným bitem. Takovým schématům se říká konečný automat. Zachytíme společné rysy předchozích příkladů. Definice Grafem G = (V, E) rozumíme množinu V jeho vrcholů (někdy též uzlů) spolu s podmnožinou E množiny (2) všech dvouprvkových podmnožin ve V. Prvkům E říkáme hrany grafu. Vrcholům ve hraně e = {v, w}, v ^ w, říkáme hraniční vrcholy hrany e. O hranách, které mají daný vrchol v za hraniční říkáme, že z vrcholu v vycházejí. Orientovaným grafem G = (V, E) rozumíme množinu V jeho vrcholů spolu s podmnožinou E C V x V. Prvnímu z vrcholů definujících hranu e = (v, w) říkáme počáteční vrchol hrany, druhému pak koncový vrchol. Definice (... pokračování] Hrana e vychází ze svého počátečního vrcholu a vchází do koncového. U orientovaných hran mohou být koncový a počáteční vrchol totožný, hovoříme pak o smyčce. Sousední hrany grafu jsou ty, které sdílí hraniční vrchol, u sousedních hran orientovaného grafu musí být vrchol pro jednu koncový a pro druhou počáteční. Naopak, sousední vrcholy jsou ty, které jsou hraničními pro tutéž hranu. Jistě umíme grafy popisovat pomocí relací, viz první kapitola prvního semestru. Jednoduchým věcem se dá říkat i složitě: Např. v prvním příkladu pracujeme na množině hostů se dvěma komplementárními symetrickými a a nti reflexním i relacemi. Grafy - příklad kompromisu mezi přirozeným sklonem k „přemýšlením v obrázcích" a přesným matematickým vyjadřováním. Časté použití - dodatečné informace o vrcholech nebo hranách (obarvení vrcholů, příp. map, ohodnocení hran apod.) Náš první příklad můžeme tedy chápat jako graf s obarvenými hranami. Dokázané tvrzení v této řeči zní: V grafu Kn = (V, (2)) s n vrcholy a se všemi možnými hranami obarvenými dvěma barvami, je vždy alespoň jeden trojúhelník z hran o stejné barvě, pokud (-<==> ) je počet vrcholů alespoň šest. Grafu se všemi možnými hranami (tj. E = (2)) říkáme úplný graf. Značíme symbolem Kn, kde n je počet vrcholů grafu. Graf K4 a K5 jsme již viděli, K3 je trojúhelník, K2 je úsečka. Cesta je graf, v němž existuje uspořádání vrcholů (vq, ... ,vn) takové, že E = {ei,..., en}, kde e,- = {v,_i, v,}, pro všechny / = 1,..., n. Hovoříme o cestě délky n a značíme ji Pn. Pokud cestu upravíme tak, že poslední a první vrchol splývají, dostaneme kružnici délky n a značíme Cm- Na obrázku jsou K3 = C3, C5 a P5 r-J Úplný bipartitní graf vznikne tak, že vrcholy rozdělíme do dvou skupin (tj. obarvíme dvěma barvami) a pak přidáme všechny hrany, které spojí vrcholy z různých skupin. Značíme jej Kmn, kde man jsou počty vrcholů v jednotlivých skupinách. Na obrázku je vidět Ki,3i ^2,3 a ^3,3- Y Pro V1 = {ui,..., um}, V2 = {Ví, V =V1UV2a E=V1xV2. ■ , vn} je Km>n = (V,E), kde 0000 0001 Přímo z definice vyplývá, že hyperkostku v dané dimenzi vždy dostaneme tak, že vhodně spojíme hranami dvě hyperkostky o jednu dimenzi menší. Na obrázku je naznačeno spojení dvou H3 čárkovanými hranami. Samozřejmě ale můžeme tímto způsobem rozložit H4 mnoha různými způsoby. Cyklický žebřík CLn s 2n vrcholy je složen propojením dvou kopií kružnice Cn tak, že hrany spojí odpovídající vrcholy dle pořadí. Tzv. Petersenův graf je sice docela podobný C/.5, ale ve skutečnosti je to nejjednoduší „vyvraceč nesprávných úvah" - graf, na němž se vyplatí testovat tvrzení, než je začneme dokazovat. Definice Pro grafy G = (V, E) a G' = (V, E') budeme za (homo)morfismus f : G —> G' považovat zobrazení fy : V —► V mezi množinami vrcholů takové, že je-li e = {v, w} hrana v E, pak e' = {f(v), f(w)} musí být hranou v E'. V dalším textu nebudeme ve značení odlišovat morfismus f a zobrazení fy. Zároveň pak takové zobrazení fy určuje i zobrazení fe : E —► E', ŕ(e) = e', kde e a e' jsou jako výše. Pro orientované grafy je definice shodná, jen pracujeme s uspořádanými dvojicemi e = (v, w) v roli hran. Všimněme si, že tato definice znamená, že pokud f (v) = f{w) pro dva různé vrcholy ve V, pak mezi nimi nesměla být hrana. U orientovaných grafů je taková hrana přípustná, pokud je na společném obrazu smyčka. Speciálním případem je morfismus libovolného grafu G do úplného grafu Km. Takový morfismus je ekvivalentní vybranému obarvení vrcholů grafu V pomocí m různých jmen vrcholů Km tak, že stejně obarvené vrcholy nejsou spojeny hranou. Hovoříme v tomto případě o barvení grafu pomocí m barev. Definice V případě, že je morfismus f : G —> G' bijekcí na vrcholech takovou, že i r_1 je morfismem, hovoříme o izomorfismu grafů. Izomorfní grafy se liší pouze různým pojmenováním vrcholů. Snadno umíme načrtnout až na izomorfismus všechny grafy na málo vrcholech (třeba třech nebo čtyřech). Obecně jde ale o nesmírně složitý kombinatorický problém a i rozhodnutí o konkrétních dvou daných grafech, zda jsou izomorfní, je obecně mimořádně obtížné. Jednoduchými a mimořádně užitečnými příklady morfismů grafů jsou pojmy cesta, sled a kružnice v grafu: Definice Cestou délky n v grafu G rozumíme morfismus p : Pn —> G takový, že p je injektivní zobrazení (tj. všechny obrazy vrcholů i/o,..., vn z Pn jsou různé). Sled délky n v grafu G je jakýkoliv morfismus s : Pn —> G (tj. v obrazu se mohou opakovat vrcholy i hrany). Tah je speciální případ sledu, v němž se mohou opakovat vrcholy, ale nikoliv hrany. Sled si můžeme představit jako dráhu „přičinlivého, ale tápajícího" poutníka z uzlu f(vo) do uzlu f(vn). Poutník totiž zdárně dojde, ale klidně se po cestě grafem vrací do uzlů nebo i dokonce po hranách, kterými dříve šel. Táhnoucí poutník je již o něco moudřejší. Cesta je naopak průchod grafem z počátečního uzlu f(vo) do koncového f{vn) bez takových zbytečných oklik. Obrazy cest i sledů jsou příkladem tzv. podgrafů: Definice Graf G' = (V, E') je podgrafem v grafu G V C V, E' C E. (V, E), jestliže Speciální příklady: Uvažujme graf G = (V, E) a nějakou podmnožinu V C V. Indukovaný podgraf je graf G' = (V, £'), kde e G E patří i do £' právě, když oba krajní vrcholy hrany e patří do V (£' = £ n (^)). Faktor G' = (V, £') je takový graf, který má stejnou množinu vrcholů jako G, ale jeho množina hran E1 je libovolnou podmnožinou. Obecný případ je kombinací těchto dvou. Každý obraz homomorfismu (tj. obraz jak vrcholů, tak hran) tvoří podgraf. Neizomorfních grafů nemůže být méně než 20 *(„) = _. Pro n —> oo lze přímo odvodit log2 k{rí) = -n2 - 0(n log2 n). Můžeme to nepřesně formulovat tak, že velká většina všech možných grafů bude po dvou neizomorfní. Poznámka Vlastní konstrukce „mnoha" neizomorfních grafů na n vrcholech ale není triviální. Zkuste jich sestrojit alespoň více než n2\ Poznámka (Graph isomorphism problem) Gl problém je poměrně zvláštním příslušníkem třídy NP-problémů - není o něm známo ani, je-li NP-úplný, ani je-li polynomiální složitosti. Naproti tomu, o Subgraph isomorphism problem je známo, zeje NP-úplný. Izomorfní grafy se od sebe liší pouze přejmenováním vrcholů. Proto musí mít stejné všechny číselné charakteristiky, které se přešíslováním vrcholů nemění. Jednoduché údaje tohoto typu můžeme dostat sledováním počtů hran vycházejících z jednotlivých vrcholů. Definice Pro vrchol v G V v grafu G = (V, E) říkáme, že jeho stupeň je k, jestliže v E existuje k hran, jejichž hraničním vrcholem v je. Píšeme v takovém případě deg v = k. U orientovaných grafů rozlišujeme vstupní stupeň deg+ v vrcholu v a výstupn stupeň deg_ v. Skóre grafu G s vrcholy V = (v\, , vn) je posloupnost (deg i/i, deg v2 , deg vn) Pro izomorfní grafy se jejich skóre může lišit pouze permutací hodnot. Pokud tedy porovnáme skóre grafů setříděné podle velikosti hodnot, pak různá skóre zaručují neizomorfnost grafu. Naopak ale snadno najdeme příklad grafů se stejným skóre, které izomorfní být nemohou, např. G = C3 U C3 má skóre (2, 2, 2, 2, 2, 2), stejně jako Q- Zjevně ale izomorfní nejsou, protože v Co existuje cesta délky 5, která v druhém grafu být nemůže. Jaká skóre mohou grafy mít? Protože každá hrana vychází ze dvou vrcholů, musí být v celkovém součtu skóre započtena každá hrana dvakrát. Proto platí ^degv = 2|E|. vev Zejména tedy musí být součet všech hodnot skóre sudý. Následující věta je vlastně o návod, jak pro dané skóre buď zjistit, že graf s takovým neexistuje nebo takový graf sestrojit. Věta (Havel, Hakimi - Algoritmus na sestrojení grafu s daným skóre) Pro libovolná přirozená čísla 0 < d\ < ■ ■ ■ < dn existuje graf G na n vrcholech s těmito hodnotami skóre tehdy a jen tehdy, když existuje graf se skóre (cfi, d2,..., dn_d„ - 1, dn-d„+i - 1, • • •, dn-i - 1) na n — 1 vrcholech. Příklad Existuje graf, jehož skóre je (2, 3, 3, 3, 3, 3,4,5)? Pokud ano, sestrojte jej. Důkaz. * „<=" zřejmé. „=>" idea: ukáže se, že při pevně zadaném (vzestupném) skóre {di,,. ., dn) existuje graf s tímto skóre, jeh( dž vrchol vn je spojen hranou právě s posled nimi dn vrcholy vn -d„, . ..,!/„_!. D Grafy jsou jazykem, ve kterém často formulujeme algoritmy. Rozumíme tím postup, kdy v nějakém orientovaném grafu přecházíme z uzlu do uzlu podél hran a přitom zpracováváme informace, které jsou určeny a ovlivněny výsledkem předchozích operací, uzlem, ve kterém se zrovna nacházíme, a hranou, kterou jsme do uzlu vstoupili. Při zpracování informace se zároveň rozhodujeme, kterými výstupními hranami budeme pokračovat a v jakém pořadí. Pokud je graf neorientovaný, můžeme všechny hrany považovat za dvojice hran orientované opačnými směry. Abychom mohli algoritmy realizovat pomocí počítače, je třeba umět uvažovaný graf efektivně zadat. Uvedeme dva příklady: Definice (Hranový seznam/Edge List) Graf G = (V, E) si v něm reprezentujeme jako dva seznamy V a E propojené ukazateli tak, že každý vrchol ukazuje na všechny z něj vycházející hrany (případně také na všechny do něj vcházející hrany u orientovaných grafů) a každá hrana ukazuje na svůj počáteční a koncový vrchol. Je vidět, že pamět potřebná na uchování grafu je v tomto případě 0(\V\ + \E\), protože na každou hranu ukazujeme právě dvakrát a na každý vrchol ukazujeme tolikrát, kolik je jeho stupeň a součet stupňů je také roven dvojnásobku počtu hran. Až na konstantní násobek jde tedy stále o optimální způsob uchovávání grafu v paměti. Definice (Matice sousednosti grafu) Uvažme (neorientovaný) graf G = (V, E), zvolme uspořádání jeho vrcholů V = (ví,..., vn) a definujme matici Aq = {a,j) nad Z2 (tj zaplněnou jen nulami a jedničkami) takto: {1 jestliže je hrana e,\ = {v,, v;} v E 0 jestliže není hrana e,j = {v,, vj} v E Matici Ag nazýváme matice souslednosti grafu G. Jak vypadají matice grafů z příkladů na začátku této přednášky? Při nejjednodušším způsobu uchovávání matic v poli je zadání grafu pomocí matice souslednosti velice neefektivní metoda. Potřebuje totiž vždy 0(n2) místa v paměti. Pokud je ale v grafu málo hran, dostáváme tzv. řídkou matici se skoro všemi prvky nulovými. Existují ovšem postupy, jak tyto řídké matice uchovávat v paměti efektivněji. Definice (Základní operace nad grafem) • odebrání hrany • přidání hrany • přidání vrcholu • odebrání vrcholu 9 dělení hrany nově přidanýrr vrcholem Jak se projeví tyto operace v našich reprezentacích? Jednoduchou aplikací maticového počtu je tvrzení: B Nechť G = (V, E) je graf a maticí souslednosti Ac- s uspořádanými Označme AkG = vrcholy V = {vu...,vn) (a- ) prvky k-té mocniny v,- a Vj. matice Aq. Pak a- je počet sledů délky k mezi vrcholy Důkaz. Indukcí. Důsledek Jsou-li G = (V, E) a Ac jako v předchozí větě, pak lze všechny dvojice vrcholů G spojit cestou právě, když má matice (A + In)n_1 samé nenulové členy (zde I„ označuje jednotkovou matici s n řádky a sloupci).