Petr Hliněný, FI MU Brno 1 FI: MA010: Vzdálenost v grafech 3 Vzdálenost a metrika v grafech V minulé lekci jsme mluvili o souvislosti grafu, tj. o možnosti procházení z jednoho vrcholu do jiného. Někdy je prostá informace o souvislosti dostačující, ale většinou bychom rádi věděli i jak je to z jednoho vrcholu do druhého "daleko". a b c d x V jednodušším případě se při zjišťování grafové vzdálenosti díváme jen na minimální počet prošlých hran z vrcholu do vrcholu. V obecném případě však při určování vzdálenosti bereme do úvahy délky jednotlivých hran podél cesty (tyto délky musí být nezáporné!). 2 Stručný přehled lekce * Vzdálenost v grafech a její vlastnosti. * Výpočet metriky grafu maticí. * Dijkstrův algoritmus pro nejkratší (ohodnocenou) cestu v grafu. Petr Hliněný, FI MU Brno 2 FI: MA010: Vzdálenost v grafech 3.1 Vzdálenost v grafu Vzpomeňme si, že sledem délky n v grafu G rozumíme posloupnost vrcholů a hran v0, e1, v1, e2, v2, . . . , en, vn, ve které hrana ei má koncové vrcholy vi-1, vi. Definice 3.1. Vzdálenost dG(u, v) dvou vrcholů u, v v grafu G je dána délkou nejkratšího sledu mezi u a v v G. Pokud sled mezi u, v neexistuje, je vzdálenost dG(u, v) = . 2 Neformálně řečeno, vzdálenost mezi u, v je rovna nejmenšímu počtu hran, které musíme projít, pokud se chceme dostat z u do v. Speciálně dG(u, u) = 0. Uvědomme si, že nejkratší sled je vždy cestou (vrcholy se neopakují) ­ Věta 2.2. Poznámka: V neorientovaném grafu je vzdálenost symetrická dG(u, v) = dG(v, u). 2 Lema 3.2. Vzdálenost v grafech splňuje trojúhelníkovou nerovnost: u, v, w V (G) : dG(u, v) + dG(v, w) dG(u, w) . Důkaz. Nerovnost snadno plyne ze zřejmého pozorování, že na sled délky dG(u, v) mezi u, v lze navázat sled délky dG(v, w) mezi v, w, čímž vznikne sled délky dG(u, v)+ dG(v, w) mezi u, w. Skutečná vzdálenost mezi u, w pak už může být jen menší. 2 Petr Hliněný, FI MU Brno 3 FI: MA010: Vzdálenost v grafech Zjištění vzdálenosti Věta 3.3. Nechť u, v, w jsou vrcholy souvislého grafu G takové, že dG(u, v) < dG(u, w). Pak při algoritmu procházení grafu G do šířky z vrcholu u je vrchol v nalezen dříve než vrchol w. 2 Důkaz. Postupujeme indukcí podle vzdálenosti dG(u, v): Pro dG(u, v) = 0, tj. u = v je tvrzení jasné ­ vrchol u jako počátek prohledávání byl nalezen první. Proto nechť dG(u, v) = d > 0 a označme v souseda vrcholu v bližšího k u, tedy dG(u, v ) = d - 1. Stejně tak značme w souseda vrcholu w bližšího k u, tedy dG(u, w ) > dG(u, v ). Potom byl vrchol v nalezen v prohledávání do šířky dříve než vrchol w podle indukčního předpokladu. To znamená, že v se dostal do fronty úschovny dříve než w , a tudíž sousedé v (mezi nima v) budou při prohledávání nalezeni dříve než sousedé w . 2 2 Důsledek 3.4. Základní algoritmus procházení grafu do šířky lze použít pro výpočet vzdálenosti z vrcholu u: Toto je poměrně jednoduchá aplikace, kdy počátečnímu vrcholu přiřadíme vzdálenost 0, a pak vždy každému dalšímu nalezenému vrcholu přiřadíme vzdálenost o 1 větší než byla vzdálenost vrcholu, ze kterého jsme jej nalezli. 2 My si ale dále ukážeme obecnější Dijkstrův algoritmus, který počítá nejkratší vzdálenost při libovolně kladně ohodnocených délkách hran. Petr Hliněný, FI MU Brno 4 FI: MA010: Vzdálenost v grafech Další pojmy a fakta s s s s s s s s Definice. Mějme graf G. Definujeme (vzhledem k G) následující pojmy a značení: * Excentricita vrcholu exc(v) je nejdelší vzdálenost z v do jiného vrcholu grafu; exc(v) = maxxV (G) dG(v, x). 2 * Průměr diam(G) grafu G je největší excentricita jeho vrcholů, naopak poloměr rad(G) grafu G je nejmenší excentricita jeho vrcholů. 2 * Centrem grafu je množina vrcholů U V (G) takových, jejichž excentricita je rovna rad(G). 2 * Steinerova vzdálenost mezi vrcholy libovolné podmnožiny W V (G) je rovna minimálnímu počtu hran souvislého podgrafu v G obsahujícího všechny vrcholy W. Petr Hliněný, FI MU Brno 5 FI: MA010: Vzdálenost v grafech Jedna zajímavost Pro zajímavost (a zvídavé studenty) si uveďme následující vlastnost grafů. (Nebude třeba ke zkoušce.) Definice: Graf je vzdálenostně dědičný (distance-hereditary), pokud vzdálenost každé dvojice jeho vrcholů u, v je stejná ve všech indukovaných souvislých podgrafech obsahujících u, v. 2 Fakt. Grafy bez kružnic jsou vzdálenostně dědičné. 2 Fakt. Následující konstrukce vytváří vzdálenostně dědičné grafy: ­ Začněme z jediného vrcholu. ­ Mějme dva grafy G1, G2 získané touto konstrukcí (rekurzivně). Vytvoříme jejich disjunktní sjednocení G1 ˙ G2. ­ Mějme dva grafy G1, G2 získané touto konstrukcí (rekurzivně). Vytvoříme jejich disjunktní sjednocení G1 ˙ G2 a přidáme všechny hrany mezi V (G1) a V (G2). 2 (Najděte vzdálenostně dědičný graf, který nelze takto sestrojit. . . ) Věta 3.5. Graf G je vzdálenostně dědičný právě když každá kružnice délky alespoň 5 má v G dvě ,,zkřížené tětivy. Petr Hliněný, FI MU Brno 6 FI: MA010: Vzdálenost v grafech 3.2 Výpočet metriky Definice: Metrikou grafu myslíme soubor vzdáleností mezi všemi dvojicemi vrcholů grafu. Jinak řečeno, metrikou grafu G je matice (dvourozměrné pole) d[,], ve kterém prvek d[i,j] udává vzdálenost mezi vrcholy i a j. 2 Metoda 3.6. Iterativní výpočet metriky skládáním cest * Na počátku nechť d[i,j] udává 1 (případně délku hrany {i, j}), nebo pokud hrana mezi i, j není. 2 * Po každém kroku t 0 nechť d[i,j] udává délku nejkratší cesty mezi i, j, která jde pouze přes vnitřní vrcholy z množiny {0, 1, 2, . . ., t - 1}. 2 * Při přechodu z t na následující krok t + 1 upravujeme vzdálenost pro každou dvojici vrcholů ­ jsou vždy pouhé dvě možnosti: ­ Buď je cesta délky d[i,j] z předchozího kroku stále nejlepší (tj. nově povolený vrchol t nám nepomůže), ­ nebo cestu vylepšíme spojením přes nově povolený vrchol t, čímž získáme menší vzdálenost d[i,t]+d[t,j]. Petr Hliněný, FI MU Brno 7 FI: MA010: Vzdálenost v grafech Poznámka: V praktické implementaci pro symbol použijeme velkou konstantu, třeba MAX INT/2. Algoritmus 3.7. Výpočet metriky grafu vstup: matice sousednosti G[][] grafu na N vrcholech, kde G[i,j]=1 pro hranu mezi i, j a G[i,j]=0 jinak; for (i=0; i 0 pro všechny hrany e. 2 Definice: Mějme (kladně) vážený graf G, w. Délkou váženého sledu S = v0, e1, v1,e2, v2, . . . , en, vn v G myslíme součet dw G(S) = w(e1) + w(e2) + . . . + w(en) . Váženou vzdáleností v G, w mezi dvěma vrcholy u, v pak myslíme dw G(u, v) = min{dw G(S) : S je sled s konci u, v} .2 Lema 3.10. Vážená vzdálenost v kladně vážených grafech také splňuje trojúhelníkovou nerovnost. Petr Hliněný, FI MU Brno 9 FI: MA010: Vzdálenost v grafech Podívejme se na následující graf vlevo. (Čísla u hran udávají jejich váhy, hrany bez čísel mají váhu 1.) Vážená vzdálenost mezi vrcholy a, c je 3, mezi b, c také 3. Jaká je vzdálenost mezi vrcholy a, b? Ne, není to 6, ale najdeme kratší cestu délky 5. a 3 3 b c 4 x y 3 3 3 -4 2 V druhém příkladě vpravo je uvedena i hrana se zápornou vahou -4. Nejkratší cesta mezi vrcholy x, y tak má délku -2, ale pokud vezmeme sled, který hranu váhy -4 vícekrát zopakuje, dostaneme se na libovolně nízkou zápornou délku. To je samozřejmě nesmyslné, a proto se takovému problému radši vyhýbáme zákazem záporných vah hran. Petr Hliněný, FI MU Brno 10 FI: MA010: Vzdálenost v grafech 3.4 Hledání nejkratší cesty Pro nalezení nejkratší (vážené) cesty mezi dvěma vrcholy kladně váženého grafu se používá známý tzv. Dijkstrův algoritmus. Poznámka: Dijkstrův algoritmus je sice složitější než Algoritmus 3.7, ale na druhou stranu je výrazně rychlejší, pokud nás zajímá jen nejkratší vzdálenost z jednoho vrcholu místo všech dvojic vrcholů. Zrovna tento algoritmus se například používá při vyhledávání vlakových či autobusových spojení. Pravděpodobně se i vy někdy dostanete do situace, kdy budete nejkratší cestu hledat, proto si tento algoritmus zapamatujte. 2 Dijkstrův algoritmus * Je variantou procházení grafu (skoro jako do šířky), kdy pro každý nalezený vrchol ještě máme proměnnou udávající vzdálenost ­ délku nejkratšího sledu (od počátku), kterým jsme se do tohoto vrcholu zatím dostali. 2 * Z úschovny nalezených vrcholů vždy vybíráme vrchol s nejmenší vzdáleností (mezi uschovanými vrcholy) ­ do takového vrcholu se už lépe dostat nemůžeme, protože všechny jiné cesty by byly dle výběru delší. 2 * Na konci zpracování tyto proměnné vzdálenosti udávají správně nejkratší vzdálenosti z počátečního vrcholu do ostatních. Petr Hliněný, FI MU Brno 11 FI: MA010: Vzdálenost v grafech Algoritmus 3.11. Dijkstrův pro nejkratší cestu v grafu Tento algoritmus nalezne nejkratší cestu mezi vrcholy u a v kladně váženého grafu G. vstup: graf na N vrcholech daný seznamem sousedů sous[][] a del[][], kde sous[i][0],...,sous[i][st[i]-1] jsou sousedé vrcholu i stupně st[i] a hrana z i do sous[i][k] má délku del[i][k]>0; vstup: u,v, kde hledáme cestu z u do v;2 // stav[i] udává zpracovanost vrcholu, vzdal[i] zatím nalezenou vzdálenost for (i=0; i<=N; i++) { vzdal[i] = MAX INT; stav[i] = 0; } vzdal[u] = 0;2 while (stav[v]==0) { for (i=0, j=N; i