Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Drsná matematika III — 7. přednáška Grafy a algoritmy: základní pojmy a úvahy Jan Slovák Masarykova univerzita Fakulta informatiky 31. 10. 2011 Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Obsah přednášky 1 Literatura 2 Základní pojmy grafů Základní definice Galerie jednoduchých grafů 3 Morfismy grafů a podgrafy Morfismy Podgrafy Stupně uzlů a skóre grafu 4 Algoritmy a reprezentace grafů Grafové algoritmy Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Kde je dobré číst? 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/ Bill Cherowitzo, Applied Graph Therory, Lecture Notes, http://www- math.cudenver.edu/˜wcherowi/courses/m4408/m4408f.html Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů 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é? 00 00 00 11 11 11 00 0000 11 1111 00 0000 11 1111000000000000000 000000000000000 000000000000000 000000000000000 000000000000000000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000000000000000000 000000000000000 000000000000000 000000000000000 000000000000000000000000000000 000000000000000 111111111111111111111111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111111111111111111 111111111111111 111111111111111 111111111111111 111111111111111111111111111111 111111111111111 111111111111111111111111111111 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000000000000000000 000000000000000 000000000000000 000000000000000 000000000000000000000000000000 000000000000000 111111111111111111111111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111111111111111111 111111111111111 111111111111111 111111111111111 111111111111111111111111111111 111111111111111 111111111111111111111111111111 00 00 00 11 11 11 0000000000000000000000000 000000000000000000000000000000 00000000000000000000 00000000000000000000 111111111111111 111111111111111111111111111111 11111111111111111111 111111111111111111111111111111 0011 0 00 1 11 0011 0011 000 11100000000000000000000 0000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 1111111111 1111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111111111111111 00000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 1111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000 0000000000 11111111111111111111111111111111111 1111111111 00000000000000000000000000000000000 0000000000 11111111111111111111111111111111111 1111111111 0000000000 0000000000000000000000000 00000000000000000000000000000000000 000000000000000 0000000000 1111111111111111111111111 11111111111111111111111111111111111 111111111111111 11111111111111111111 0000000000 0000000000000000000000000 00000000000000000000000000000000000 000000000000000 0000000000 1111111111111111111111111 11111111111111111111111111111111111 111111111111111 11111111111111111111 0000000000000000000011111111111111111111 00000000001111111111 0000000000000000000000000 000000000000000000000000000000 00000000000000000000 00000000000000000000 111111111111111 111111111111111111111111111111 11111111111111111111 111111111111111111111111111111 0000000000 0000000000000000000000000 00000 11111 111111111111111111111111111111 11111 0000000000000000000000000 00000000000000000000 11111111111111111111 1111111111111111111111111 0011 000000 000 000 111111 111 111 00 00 00 11 11 11 0000 00 1111 11 0000 00 1111 11 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. Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů 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: 0 S BLUE RED 0 1 1 1 0 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. Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů 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 V 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 ⊂ V × V . Prvnímu z vrcholů definujících hranu e = (v, w) říkáme počáteční vrchol hrany, druhému pak koncový vrchol. Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů 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 antireflexními 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á.) Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů 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 , 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. Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů 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ů (v0, . . . , vn) takové, že E = {e1, . . . , en}, kde ei = {vi−1, vi }, pro všechny i = 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 CN. Na obrázku jsou K3 = C3, C5 a P5 0 0 0 0 00 0 0 0 00 0 11 1 1 1 1 11 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0011 0 0 1 1 0 0 1 1 0 0 1 1 0011 0011 0 0 1 1 0 0 1 10000 0000 0000 0000 00000000 0000 0000 0000 0000 0000 1111 11111111 1111 1111 1111 11111111 1111 1111 1111 0000 0000 0000 0000 00000000 0000 0000 0000 0000 0000 1111 11111111 1111 1111 1111 11111111 1111 1111 1111 0000000011111111 0000 0000 0000 00000000 0000 0000 1111 1111 1111 11111111 1111 1111 0000 0000 0000 00000000 0000 0000 1111 1111 1111 11111111 1111 1111 00 00 0000 00 00 00 00 11 11 11 1111 11 11 11 000001111100 00 0000 00 00 00 00 11 11 11 1111 11 11 11 00 00 0000 00 00 00 00 11 11 11 1111 11 11 11 0000011111 0 0 00 0 0 0 0 1 1 1 11 1 1 1 00000 00000 11111 11111 0 0 1 1 Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Ú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 m a n jsou počty vrcholů s jednotlivými barvami. Na obrázku je vidět K1,3, K2,3 a K3,3. 00110011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011000000 000000000 000000 000000000 000 111 111111111 111111 111111111111 111 000000 000000000 000000 000000000 000 111 111111111 111111 111111111111 111 0000 000000 0000 000000 00 11 111111 1111 11111111 11 0000 000000 0000 000000 00 11 111111 1111 11111111 11 00000000 000000000000 00000000 000000000000 0000 1111 111111111111 11111111 1111111111111111 1111 00 000 00 000 0 1 111 11 1111 1 0000 000000 0000 000000 00 11 111111 1111 11111111 11 0000000000 000000000000000 0000000000 000000000000000 00000 11111 111111111111111 1111111111 11111111111111111111 11111 000000 000000000 000000 000000000 000 111 111111111 111111 111111111111 111 000000 000000000 000000 000000000 000 111 111111111 111111 111111111111 111 000000 000000000 000000 000000000 000 111 111111111 111111 111111111111 111 000000 000000000 000000 000000000 000 111 111111111 111111 111111111111 111 0000000000 000000000000000 0000000000 000000000000000 00000 11111 111111111111111 1111111111 11111111111111111111 11111 0000000000 000000000000000 0000000000 000000000000000 00000 11111 111111111111111 1111111111 11111111111111111111 11111 0011 Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Hyperkostka Hn v dimenzi n vznikne tak, že vrcholy jsou všechna čísla 0, . . . , 2n − 1. Hrany spojí právě ta čísla, která se v zápisu v dvojkové soustavě liší v právě jednom bitu. Na obrázku níže je H4 a popis vrcholů je naznačen. 1001 0011 0011 0011 0011 0011 0 0 1 1 0 0 1 1 000000001111111100000 00000000000000000000 000000000000000 000000000000000 11111 111111111111111 111111111111111 111111111111111 11111 00000 00000000000000000000 000000000000000 000000000000000 11111 111111111111111 111111111111111 111111111111111 11111 00000000000000000000 00000000000000000000 000000000000000 111111111111111 111111111111111 1111111111111111111111111 0000000011111111 00000000000000000000 00000000000000000000 000000000000000 111111111111111 111111111111111 1111111111111111111111111 0000000011111111 0000000011111111 0011 0011 0011 0011 0011 0011 00110011 0000000011111111000000000000000 000000000000000 000000000000000 0000000000 11111 1111111111 111111111111111 11111 1111111111 11111 11111 000000000000000 000000000000000 000000000000000 0000000000 11111 1111111111 111111111111111 11111 1111111111 11111 11111 00000 0000000000 00000000000000000000 00000 00000 0000000000 11111 11111 11111 111111111111111 111111111111111 1111111111 0000000011111111 00000 0000000000 00000000000000000000 00000 00000 0000000000 11111 11111 11111 111111111111111 111111111111111 1111111111 0000000011111111 0000000011111111 00000000000000000000000000000000 000000000000000000000000000000000000000000000000 00000000000000000000000000000000 0000000000000000 0000000000000000 000000000000000000000000000000000000000000000000 00000000000000000000000000000000 0000000000000000 00000000000000000000000000000000 000000000000000000000000000000000000000000000000 00000000000000000000000000000000 11111111111111111111111111111111 111111111111111111111111111111111111111111111111 11111111111111111111111111111111 1111111111111111 1111111111111111 111111111111111111111111111111111111111111111111 11111111111111111111111111111111 1111111111111111 11111111111111111111111111111111 111111111111111111111111111111111111111111111111 11111111111111111111111111111111 0000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000 00000000000000000000000000000000 0000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 1111111111111111 111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111111111111111111111111111111111 1111111111111111 11111111111111111111111111111111 1111111111111111 111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 00000000000000000000000000000000 000000000000000000000000000000000000000000000000 00000000000000000000000000000000 0000000000000000 0000000000000000 000000000000000000000000000000000000000000000000 00000000000000000000000000000000 0000000000000000 00000000000000000000000000000000 000000000000000000000000000000000000000000000000 00000000000000000000000000000000 11111111111111111111111111111111 111111111111111111111111111111111111111111111111 11111111111111111111111111111111 1111111111111111 1111111111111111 111111111111111111111111111111111111111111111111 11111111111111111111111111111111 1111111111111111 11111111111111111111111111111111 111111111111111111111111111111111111111111111111 11111111111111111111111111111111 0000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000 00000000000000000000000000000000 0000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 1111111111111111 111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111111111111111111111111111111111 1111111111111111 11111111111111111111111111111111 1111111111111111 111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111111111111111111111111111111111 1111111111111111 11111111111111111111111111111111 11111111111111111111111111111111 00000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 11111111111111111111111111111111 1111111111111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 1111111111111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 00000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 11111111111111111111111111111111 1111111111111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 1111111111111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111111111111111111111111111111111 1111111111111111 11111111111111111111111111111111 11111111111111111111111111111111 0000 0001 0010 0100 0110 1110 1111 1011 0011 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 Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů 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ý CL5, 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. 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0011 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Definition Pro grafy grafy G = (V , E) a G = (V , E ) budeme za morfismus f : G → G považovat zobrazení fV : 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í fV . Zároveň pak takové zobrazení fV určuje i zobrazení fE : E → E , f (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ů, taková hrana je přípustná, pokud je na společném obrazu smyčka. Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů 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. Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Definition V případě, že je morfismus f : G → G bijekcí na vrcholech takovou, že i f −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é. Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů 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ů v0, . . . , 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 (v0) 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 (v0) do koncového f (vn) bez takových zbytečných oklik. Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Obrazy cest i sledů jsou příkladem tzv. podgrafů, ne však stejným způsobem: Definition Graf G = (V , E ) je podgrafem v grafu G = (V , E), jestliže V ⊂ V , E ⊂ E. Speciální příklady: Uvažujme graf G = (V , E) a nějakou podmnožinu V ⊂ V . Indukovaný podgraf je graf G = (V , E ), kde e ∈ E patří i do E právě, když oba krajní vrcholy hrany e patří do V . Podgraf G = (V , E ) 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. Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů 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. Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Neizomorfních grafů nemůže být méně než k(n) = 2 n 2 n! . Pro n → ∞ lze přímo dovodit log2 k(n) = 1 2 n2 − O(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í. Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů 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 ∈ 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. Skóre grafu G s vrcholy V = (v1, . . . , vn) je posloupnost (deg v1, deg v2, . . . , deg vn) Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů 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 ∪ C3 má skóre (2, 2, 2, 2, 2, 2), stejně jako C6. Zjevně ale izomorfní nejsou, protože v C6 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í v∈V deg v = 2|E|. Zejména tedy musí být součet všech hodnot skóre sudý. Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů 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 ≤ d1 ≤ · · · ≤ dn existuje graf G na n vrcholech s těmito hodnotami skóre tehdy a jen tehdy, když existuje graf se skóre (d1, d2, . . . , dn−dn − 1, dn−dn+1 − 1, . . . , dn−1 − 1) na n − 1 vrcholech. U orientovaných grafů rozlišujeme vstupní stupeň deg+ v vrcholu v a výstupní stupeň deg− v. Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů 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. Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů 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ě O(|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. Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Definition (Matice sousednosti grafu) Uvažme (neorientovaný) graf G = (V , E), zvolme uspořádání jeho vrcholů V = (v1, . . . , vn) a definujme matici AG = (aij ) nad Z2 (tj. zaplněnou jen nulami a jedničkami) takto: aij = 1 jestliže je hrana eij = {vi , vj } v E 0 jestliže není hrana eij = {vi , 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? Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů 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 O(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í operace nad grafem) odebrání hrany přidání hrany přidání vrcholu odebrání vrcholu dělení hrany nově přidaným vrcholem Jak se projeví tyto operace v našich reprezentacích? Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Jednoduchou aplikací maticového počtu je tvrzení: Theorem Nechť G = (V , E) je graf s uspořádanými vrcholy V = (v1, . . . , vn) a maticí souslednosti AG . Označme Ak G = (a (k) ij ) prvky k-té mocniny matice AG . Pak a (k) ij je počet sledů délky k mezi vrcholy vi a vj . 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 + In)n−1 samé nenulové členy (zde In označuje jednotkovou matici s n řádky a sloupci). Literatura Základní pojmy grafů Morfismy grafů a podgrafy Algoritmy a reprezentace grafů 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 AG . 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á parmutační 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í.