Drsná matematika III — 7. přednáška Grafy a algoritmy: základní pojmy a úvahy Jan Slovák Masarykova univerzita Fakulta informatiky 30. 10. 2006 Q Literatura Q Základní pojmy grafů • Dva příklady • Základní definice • Galerie jednoduchých grafů Q Morfismy grafů a podgrafy • Morfismy • Podgrafy • Stupně uzlů a skóre grafu Q Algoritmy a reprezentace grafů • Grafové algoritmy • 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/ • Bili Cherowitzo, Applied Graph Therory, Lecture Notes, http://www-math.cudenver.edu/~wcherowi/courses/m4408/m4408f.html Example 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: CQ' 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ů. Definition Grafem G = (V, E) rozumíme množinu V jeho vrcholů 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 7^ w, říkáme hraniční vrcholy hrany e. 0 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. Definition (.. . 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ě: V prvním příkladu pracujeme na stejné množině hostů se dvěmi komplementárními symetrickými a a nti reflexním i relacemi, ve druhém pak jde o příklad dvou antisymetrických relací na třech prvcích. Nenechte se také zmást novým významem slova graf pro který jsme již měli význam u funkcí. (Ve skutečnosti není podobnost věcně vzdálená.) Grafy jsou pěkným příkladem 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. Obecný jazyk teorie grafů nám v konkrétních úlohách také umožňuje přidávat informace o vrcholech nebo hranách. Můžeme tak např. „obarvit" vrcholy podle příslušnosti objektů k několika disjunktním skupinám nebo můžeme označit hrany několika různými hodnotami apod. Existence hrany mezi vrcholy různých barev může naznačit „konflikt". Např. když modré a červené uzly představují pánskou a dámskou část večírku, pak hrana mezi vrcholy různých barev může znamenat potenciální nevhodnost sdílení pokoje pro přenocování. Náš první příklad v předchozím odstavci 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 na dvě barvy 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 ří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, kde existuje uspořádání vrcholů (vq, ..., vn) takové, ž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 Ca/. Na obrázku jsou K3 = C3, C5 a P5 r-J Úplný bipartitní graf vznikne tak, že vrcholy si obarvíme dvěmi barvami a pak přidáme všechny hrany, které spojí vrcholy různých barev. Značíme jej Km^n, kde man jsou počty vrcholů s jednotlivými barvami. Na obrázku je vidět Ki;3, /<2;3 a K33. Y Hyperkostka Hn v dimenzi n vznikne tak, že vrcholy jsou všechna čísla 0,..., 2" — 1. Hrany spojí právě ta čísla, která se v zápisu v dvojkové soustavě liší v právě jednom bitu. Na obrázku niže je H4 a popis vrcholů je naznačen. 1110 im 1011 0100 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 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ší uvvyvraceč nesprávných úvah - graf, na němž se vyplatí testovat tvrzení, než je začneme dokazovat. Definition Pro grafy grafy G = (V, E) a G' = (V, E') budeme za 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) dva různé vrcholy ve V, pak mezi nimi nesměla být hrana. U orientovaných grafů, taková hrana je přípustná, pokud je na společném obrazu smyčka. pro 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 uzlů Km tak, že stejně obarvené uzly nejsou spojeny hranou. Hovoříme v tomto případě o barvení grafu pomocí m barev. Definition V případě, že je morfismus f : G —> G' bijekcí na vrcholech takovou, že i r_1 je morfismem, hovoříme o izomorfísmu 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: Definition Cestou délky n v grafu G rozumíme morfismus p : Pn —> G takový, že p je injektivní zobrazení (tj. všechny obrazy vrcholů vq, ... ,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). 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 fVn. Poutník se totiž v žádném uzlu nezastaví, ale klidně se po cestě grafem vrací do uzlů nebo i dokonce po hranách, kterými dříve šel. 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ů, ne však stejným způsobem: Definition Graf G' = (V, £') je podgrafem v grafu G V CV,£'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, E1), kde e G E patří i do E' právě, když oba krajní vrcholy hrany e patří do V. Podgraf G' = (V, £') je takový graf, který má stejnou množinu vrcholů jako G, ale jeho množina hran E' je libovolnou podmnožinou. Obecný případ je kombinací těchto dvou. Theorem Každý obraz homomorfismu (tj. obraz jak vrcholů tak hran) tvoří podgraf. Podgraf, který je homomorfním obrazem cesty nazýváme také cestou. Je zřejmé, každá taková cesta o n > 2 vrcholech v grafu vzniká právě dvěma způsoby jako homomorfní obraz Pn, které se liší v počátečním a koncovém uzlu. Naopak, jestliže obraz sledu obsahuje k uzlů, můžeme obecně pro n > k najít nepřeberně způsobů, jak takový obraz obdržet. Kružnice v grafu G je injektivním homomorfním obrazem grafu Cn v G. Všimněte si, že sama kružnice Cn je také homomorfním obrazem cesty Pn, kdy první a poslední bod cesty zobrazíme do téhož vrcholu a zvolíme orientaci cesty. Neizomorfních grafů nemůže být méně než 20 k(n) Pro n —> 00 lze přímo dovodit i! ' log2 /c(n) = -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í. 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ů. Definition Pro vrchol v G V \ jestliže v E existují Píšeme v takovém i grafu G i k hran, případě jejichž E) říkáme, že hraničním vre jeho stupeň je holém i/ je. k, deg v - = k. Skóre grafu G s vrcholy V - = {vi,. .., vn) je posl oupnost (deg i/i deg 1/2 • • •, 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. Theorem (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 (cři, d2,..., dn-dn - 1, dn-dn+i - 1,..., dn-i - 1) na n — 1 vrcholech. U orientovaných grafů rozlišujeme vstupní stupeň deg+ v vrcholu v a výstupní stupeň deg_ v. 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: Definition Hranový seznam (Edge List). Graf G = (V, E) si v něm reprezentujeme jako dva seznamy V a E propojené ukazately 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. Definition (Matice sousednosti grafu) Uvažme (neorientovaný) graf G = (V, E), zvolme uspořádání jeho vrcholů V = (1/1,..., vn) a definujme matici Aq = (a//) 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// = {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. Definition (Základní o perace nad grafem)______________________1 • odebrání hrany • přidání hrany • přidání vrcholu • odebrání vrcholu 9 dělení hrany nove ' přidaným vrcholem Jak se projeví tyto operace v našich reprezentacích? Jednoduchou aplikací maticového počtu je tvrzení: Theorem Nechť G = (V, E) je graf a maticí souslednosti Ag- s uspořádanými Označme AkG = vrcholy V = (vi,...,vn) (a- ) prvky k-té mocniny v,- a Vj. matice Aq. Pak a\- ' je počet sledů délky k mezi vrcholy Corollary Jsou-li G = (V, E) a Ag jako v předchozí větě, pak lze všechny vrcholy G spojit cestou právě, když má matice (A + I„)n_1 samé nenulové členy (zde In označuje jednotkovou matici s n řádky a sloupci). Jaký je vliv má permutace našeho uspořádání uzlů V na matici souslednosti grafu? Permutace uzlů grafu G má za následek jednu a tutéž permutaci řádků a i sloupců matice Aq. Každou takovou permutaci můžeme zadat právě jednou tzv. permutační maticí, tj. maticí z nul a jedniček, která má v každém řádku a každém sloupci právě jednu jedničku a jinak nuly. Je-li P taková parmutacní matice, pak nová matice souslednosti izomorfního grafu G' bude AG, = P-AG-PT, kde PT značí transponovanou matici a tečkou označujeme násobení matic. Každou permutaci umíme napsat jako složení transpozic a proto příslušnou permutační matici dostaneme jako součin příslušných matic pro transpozice. V případě permutačních matic je matice trnasponovaná zároveň maticí inverzní. Tyto úvahy lze dále rozvíjet a přemýšlet o souvislostech matic souslednosti a matic lineárních zobrazení mezi vektorovými prostory. Nebudeme zde zacházet do podrobností.