Teoretyczne podstawy informatyki WykÅ‚ad 7: Grafowy model danych 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s 1 Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Graf pð Graf to jest relacja binarna. pð Dla grafów mamy ogromne możliwoÅ›ci wizualizacji jako zbiór punktów (zwanych wierzchoÅ‚kami) poÅ‚Ä…czonych liniami lub strzaÅ‚kami (nazwanych krawÄ™dziami). Pod tym wzglÄ™dem graf stanowi uogólnienie drzewiastego modelu danych. pð Podobnie jak drzewa, grafy wystÄ™pujÄ… w różnych postaciach: grafów skierowanych i nieskierowanych lub etykietowanych i niezaetykietowanych. pð Grafy sÄ… przydatne do analizy szerokiego zakresu problemów: obliczanie odlegÅ‚oÅ›ci, znajdowanie cyklicznoÅ›ci w relacjach, reprezentacji struktury programów, reprezentacji relacji binarnych, reprezentacji automatów i ukÅ‚adów elektronicznych. 2 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Relacje pð Chociaż zaÅ‚ożyliÅ›my, że w ogólnoÅ›ci elementy należące do zbiorów sÄ… niepodzielne, w praktyce czÄ™sto korzystnym rozwiÄ…zaniem jest przypisanie elementom pewnych struktur. pð WażnÄ… strukturÄ… dla elementów jest lista o staÅ‚ej dÅ‚ugoÅ›ci zwana krotkÄ…. pð Każdy element takiej listy nazywamy skÅ‚adowÄ… krotki. pð Zbiór elementów, z których każdy jest krotkÄ… o takiej samej licznoÅ›ci powiedzmy k - nazywamy relacjÄ…. LicznoÅ›ciÄ… takiej relacji jest k. pð JeÅ›li liczność wynosi 2 mówimy o krotce lub relacji binarnej. pð Iloczyn kartezjaÅ„ski A x B: Jest to zbiór par, z których pierwszy element pochodzi ze zbioru A, drugi ze zbioru B, czyli A x B = { (a, b) : a Îð A oraz b Îð B} Iloczyn kartezjaÅ„ski nie ma wÅ‚asnoÅ›ci przemiennoÅ›ci, A x B Ä…ð B x A K-elementowy iloczyn kartezjaÅ„ski A1 x A2 x A3 & x Ak to zbiór k-krotek (a1,a2, & , ak). 3 29.11.2011 3 24.11.2009 Prof. dr hab. Elżbieta Richter-WÄ…s Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Podstawowe pojÄ™cia pð Graf skierowany (ang. directed graph) SkÅ‚ada siÄ™ z nastÄ™pujÄ…cych elementów: Zbioru V wierzchoÅ‚ków (ang. nodes, vertices) Relacji binarnej E na zbiorze V. Relacje E nazywa siÄ™ zbiorem krawÄ™dzi (ang. edges) grafu skierowanego. KrawÄ™dzie stanowiÄ… zatem pary wierzchoÅ‚ków (u,v). 0 1 V = {0,1,2,3,4} E = { (0,0), (0,1), (0,2), (1,3), (2,0), (2,1), 2 3 (2,4), (3,2), (3,4), (4,1) } 4 4 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Podstawowe pojÄ™cia pð Etykiety: Podobnie jak dla drzew, dla grafów istnieje możliwość przypisania do każdego wierzchoÅ‚ka etykiety (ang. label). Nie należy mylić nazwy wierzchoÅ‚ka z jego etykietÄ…. Nazwy wierzchoÅ‚ków musza być niepowtarzalne, ale kilka wierzchoÅ‚ków może być oznaczonych ta sama etykieta. gryzie 1 2 pies kot pð Drogi: Droga (ang. path) w grafie skierowanym stanowi listÄ™ wierzchoÅ‚ków, (n1, n2, & , nk) taka, że wystÄ™puje krawÄ™dz Å‚Ä…czÄ…ca każdy wierzchoÅ‚ek z nastÄ™pnym, to znaczy (ni, ni+1) Îð E dla i=1, 2, & , k. DÅ‚ugość (ang. lengh) drogi wynosi k-1, co stanowi liczbÄ™ krawÄ™dzi należących do tej samej drogi. 5 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Podstawowe pojÄ™cia pð Grafy cykliczne i acykliczne: Cykl (ang. cycle) w grafie skierowanym jest drogÄ… o dÅ‚ugoÅ›ci 1 lub wiÄ™cej, która zaczyna siÄ™ i koÅ„czy w tym samym wierzchoÅ‚ku. DÅ‚ugość cyklu jest dÅ‚ugoÅ›ciÄ… drogi. Cykl jest prosty (ang. simple) jeżeli żaden wierzchoÅ‚ek (oprócz pierwszego) nie pojawia siÄ™ na nim wiÄ™cej niż raz. Jeżeli istnieje cykl nieprosty zawierajÄ…cy wierzchoÅ‚ek n, to można znalezć prosty cykl który zawiera n. Jeżeli graf posiada jeden lub wiÄ™cej cykli to mówimy ze jest grafem cyklicznym (ang. cyclic). JeÅ›li cykle nie wystÄ™pujÄ… to, graf okreÅ›la siÄ™ mianem acyklicznego (ang. acyclic). 0 1 PrzykÅ‚ady cykli prostych: (0,0), (0,2,0), (1,3,2,1), (1,3,2,4,1) 2 3 PrzykÅ‚ad cyklu nieprostego: (0,2,1,3,2,0) 4 6 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Grafy wywoÅ‚aÅ„ pð WywoÅ‚ania dokonywane przez zestaw funkcji można reprezentować za pomocÄ… grafu skierowanego, zwanego grafem wywoÅ‚aÅ„. Jego wierzchoÅ‚ki stanowiÄ… funkcje, a krawÄ™dz (P, Q) istnieje wówczas, gdy funkcja P wywoÅ‚uje funkcje Q. pð Istnienie cyklu w grafie implikuje wystÄ™powanie w algorytmie rekurencji. pð Rekurencja w której funkcja wywoÅ‚uje samÄ… siebie nazywamy bezpoÅ›redniÄ… (ang. direct). pð Czasem mamy do czynienia z rekurencja poÅ›rednia (ang. indirect) która reprezentuje cykl o dÅ‚ugoÅ›ci wiÄ™kszej niż 1, np. (P, Q, R, P). main Graf wywoÅ‚aÅ„ dla algorytmu sortowania przez scalanie MakeList PrintList MergeSort Rekurencja bezpoÅ›rednia split merge 7 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Grafy nieskierowane pð Czasem zasadne jest poÅ‚Ä…czenie wierzchoÅ‚ków krawÄ™dziami, które nie posiadajÄ… zaznaczonego kierunku. Z formalnego punktu widzenia taka krawÄ™dz jest zbiorem dwóch wierzchoÅ‚ków. pð Zapis {u,v} mówi ze wierzchoÅ‚ki u oraz v sÄ… poÅ‚Ä…czone w dwóch kierunkach. JeÅ›li {u,v} jest krawÄ™dziÄ… nieskierowana, wierzchoÅ‚ki u i v okreÅ›la siÄ™ jako sÄ…siednie (ang. adjacent) lub mianem sÄ…siadów (ang. neighbors). pð Graf zawierajÄ…cy krawÄ™dzie nieskierowane, czyli graf z relacjÄ… symetrycznoÅ›ci krawÄ™dzi, nosi nazwÄ™ grafu nieskierowanego (ang. undirected graph). 8 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Grafy nieskierowane Kahului Graf nieskierowany reprezentujÄ…cy 22 60 drogi na wyspie Hawajów Maui. Lahaina 16 Hana 10 Keokea pð Droga to lista wierzchoÅ‚ków. Nieco trudniej jest sprecyzować co to jest cykl, tak aby nie byÅ‚a to każda lista (n1, n2, & , nk-1, nk, nk-1, & , n2, n1) 9 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Pewne pojÄ™cia z teorii grafów pð Teoria grafów jest dziedzinÄ… matematyki zajmujÄ…cÄ… siÄ™ wÅ‚aÅ›ciwoÅ›ciami grafów. pð Grafy peÅ‚ne: Nieskierowany graf posiadajÄ…cy krawÄ™dzie pomiÄ™dzy każdÄ… parÄ… różnych wierzchoÅ‚ków nosi nazwÄ™ grafu peÅ‚nego (ang. complete graph). Graf peÅ‚ny o n wierzchoÅ‚kach oznacza siÄ™ przez Kn. Liczba krawÄ™dzi w nieskierowanym grafie Kn wynosi n(n-1)/2, w skierowanym grafie Kn wynosi n2. n1 n1 n1 n2 n1 n1 n2 n2 n3 n3 n4 n2 n3 K1 K2 K3 K4 K3 10 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Grafy planarne i nieplanarne pð O grafie nieskierowanym mówi siÄ™ że jest planarny (ang. planar) wówczas, gdy istnieje możliwość rozmieszczenia jego wierzchoÅ‚ków na pÅ‚aszczyznie, a nastÄ™pnie narysowania jego krawÄ™dzi jako lini ciÄ…gÅ‚ych które siÄ™ nie przecinajÄ…. pð Grafy nieplanarne (ang. nonplanar) to takie które nie posiadajÄ… reprezentacji pÅ‚askiej. Reprezentacja planarna: Najprostsze grafy nieplanarne: n1 n2 n1 n1 n2 n2 n3 n3 n4 n3 n4 n4 n5 K4 n5 n6 K5 K3,3 11 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Zastosowania planarnoÅ›ci i kolorowanie grafów pð Planarność ma duże zastosowanie do graficznych reprezentacji w informatyce dla projektowania różnego rodzaju ukÅ‚adów (np. scalonych, bramek, etc.) pð Kolorowanie grafu (ang. graph coloring) polega na przypisaniu do każdego wierzchoÅ‚ka pewnego koloru, tak aby żadne dwa wierzchoÅ‚ki poÅ‚Ä…czone krawÄ™dziÄ… nie miaÅ‚y tego samego koloru. pð Minimalna liczba kolorów potrzebna do takiej operacji nazwana jest liczbÄ… chromatycznÄ… grafu (ang. chromatic number), oznaczanÄ… c(G). Jeżeli graf jest peÅ‚ny to jego liczba chromatyczna jest równÄ… liczbie wierzchoÅ‚ków Jeżeli graf możemy pokolorować przy pomocy dwóch kolorów to nazywamy go dwudzielnym (ang. bipartite graph). Np. K3,3. n1 n2 c(G)=4 n1 c(G)=2 n2 n3 n3 n4 n6 n4 n5 n5 n6 12 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Sposoby implementacji grafów pð IstniejÄ… dwie standardowe metody reprezentacji grafów. Pierwsza z nich, listy sÄ…siedztwa (ang. adjacency lists), jest, ogólnie rzecz biorÄ…c, podobna do implementacji relacji binarnych. Druga, macierze sÄ…siedztwa (ang. adjacency matrices), to nowy sposób reprezentowania relacji binarnych, który jest bardziej odpowiedni dla relacji, w przypadku którym liczba istniejÄ…cych par stanowi znaczÄ…cÄ… część caÅ‚kowitej liczby par, jakie mogÅ‚yby teoretycznie istnieć w danej dziedzinie. pð WierzchoÅ‚ki sÄ… ponumerowane kolejnymi liczbami caÅ‚kowitymi 0,1,....., MAX-1 lub oznaczone za pomocÄ… innego adekwatnego typu wyliczeniowego (używamy poniżej typu NODE jako synonimy typu wyliczeniowego). pð Wówczas można skorzystać z podejÅ›cia opartego na wektorze wÅ‚asnym. pð Element successors[u] zawiera wskaznik do listy jednokierunkowej wszystkich bezpoÅ›rednich nastÄ™pników wierzchoÅ‚ka u. NastÄ™pniki mogÄ… wystÄ™pować w dowolnej kolejnoÅ›ci na liÅ›cie jednokierunkowej. typedef struct CELL *LIST; struct CELL { NODE nodeName; Listy sÄ…siedztwa: LIST next; } LIST successors[MAX] 13 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Reprezentacja grafu za pomocÄ… list sÄ…siedztwa pðListy sÄ…siedztwa zostaÅ‚y posortowane wg. kolejnoÅ›ci, ale nastÄ™pniki mogÄ… wystÄ™pować w dowolnej kolejnoÅ›ci na odpowiedniej liÅ›cie sÄ…siedztwa. 0 1 2 0 0 1 1 3 2 3 2 0 1 4 4 2 4 3 1 4 14 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Reprezentacja grafu za pomocÄ… macierzy sÄ…siedztwa pðTworzymy dwuwymiarowÄ… tablicÄ™; BOOLEAN vertices[MAX][MAX]; w której element vertices[u][v] ma wartość TRUE wówczas, gdy istnieje krawÄ™dz (u, v), zaÅ› FALSE, w przeciwnym przypadku. 0 1 2 3 4 0 1 0 1 1 1 0 0 1 0 0 0 1 0 2 3 2 1 1 0 0 1 3 0 0 1 0 1 4 4 0 1 0 0 0 15 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Porównanie macierzy sÄ…siedztwa z listami sÄ…siedztwa. pð Macierze sÄ…siedztwa sÄ… preferowanym sposobem reprezentacji grafów wówczas, gdy grafy sÄ… gÄ™ste (ang. dense), to znaczy, kiedy liczba krawÄ™dzi jest bliska maksymalnej możliwej ich liczby. pð Dla grafu skierowanego o n wierzchoÅ‚kach maksymalna liczba krawÄ™dzi wynosi n2. pð JeÅ›li graf jest rzadki (ang. sparse) to reprezentacja oparta na listach sÄ…siedztwa może pozwolić zaoszczÄ™dzić pamięć. pð Istotne różnice miedzy przedstawionymi reprezentacjami grafów sÄ… widoczne już przy wykonywaniu prostych operacji. Preferowany sposób reprezentacji: OPERACJA GRAF GESTY GRAF RZADKI Wyszukiwanie krawÄ™dzi Macierz sÄ…siedztwa Obie Znajdowanie nastÄ™pników Obie Lista sÄ…siedztwa Znajdowanie poprzedników Macierz sÄ…siedztwa Obie 16 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Spójna skÅ‚adowa grafu nieskierowanego pð Każdy graf nieskierowany można podzielić na jedna lub wiÄ™kszÄ… liczbÄ™ spójnych skÅ‚adowych (ang. connected components). pð Każda spójna skÅ‚adowa to taki zbiór wierzchoÅ‚ków, że dla każdych dwóch z tych wierzchoÅ‚ków istnieje Å‚Ä…czÄ…ca je Å›cieżka. Jeżeli graf skÅ‚ada siÄ™ z jednej spójnej skÅ‚adowej to mówimy że jest spójny (ang. connected). Kahului 22 60 To jest graf spójny Lahaina 16 Hana 10 Keokea 17 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Spójne skÅ‚adowe jako klasy równoważnoÅ›ci pð PojÄ™cie spójnych skÅ‚adowych można potraktować formalnie jako klasy równoważnoÅ›ci relacji równoważnoÅ›ci P zdefiniowanej na wierzchoÅ‚kach grafu nieskierowanego jako uPv wtedy i tylko wtedy, gdy istnieje droga z wierzchoÅ‚ka u do v. pð Sprawdzenie czy P jest relacjÄ… równoważnoÅ›ci Relacja P jest zwrotna, to znaczy zachodzi uPu dla dowolnego wierzchoÅ‚ka u, gdyż istnieje droga o dÅ‚ugoÅ›ci 0 z dowolnego wierzchoÅ‚ka do niego samego. Relacja P jest symetryczna. JeÅ›li zachodzi uPv, to istnieje droga z wierzchoÅ‚ka u do v. Ponieważ graf jest nieskierowany, odwrotny porzÄ…dek wierzchoÅ‚ków również stanowi drogÄ™. Stad zachodzi vPu. Relacja P jest przechodnia. Załóżmy, ze relacje uPw oraz wPv sÄ… prawdziwe. Wówczas istnieje pewna droga, na przykÅ‚ad (x1, x2, & , xj) z u do w. Zatem u=x1 oraz w=xj. Ponadto istnieje droga (y1, y2, & , yk) z wierzchoÅ‚ka w do v, gdzie w=y1 oraz v=yk. SkÅ‚adajÄ…c obie drogi razem otrzymujemy drogÄ™ z u do v, czyli (u=x1, x2, & , xj= w= y1, y2, & , yk= v). Relacja P dzieli graf na klasy równoważnoÅ›ci. Każda klasa równoważnoÅ›ci zdefiniowana relacjÄ… drogi odpowiada spójnej skÅ‚adowej tego grafu. 18 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Algorytm wyznaczania spójnych skÅ‚adowych pð Chcemy okreÅ›lić spójne skÅ‚adowe grafu G. Przeprowadzamy rozumowanie indukcyjne. pð Podstawa: Graf Go zawiera jedynie wierzchoÅ‚ki grafu G i żadnej jego krawÄ™dzi. Każdy wierzchoÅ‚ek stanowi odrÄ™bnÄ… spójnÄ… skÅ‚adowÄ… . pð Indukcja: ZakÅ‚adamy, że znamy już spójne skÅ‚adowe grafu Gi po rozpatrzeniu pierwszych i krawÄ™dzi, a obecnie rozpatrujemy (i+1) krawÄ™dz {u, v}. pð jeżeli wierzchoÅ‚ki u, v należą do jednej spójnej skÅ‚adowej to nic siÄ™ nie zmienia pð jeżeli do dwóch różnych, to Å‚Ä…czymy te dwie spójne skÅ‚adowe w jednÄ…. x v u y 19 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Struktura danych dla wyznaczania spójnych skÅ‚adowych pð BiorÄ…c pod uwagÄ™ przedstawiony algorytm, musimy zapewnić szybkÄ… wykonywalność nastÄ™pujÄ…cych operacji: 1. gdy jest okreÅ›lony wierzchoÅ‚ek to znajdz jego bieżącÄ… spójnÄ… skÅ‚adowÄ… 2. poÅ‚Ä…cz dwie spójne skÅ‚adowe w jednÄ… pð ZaskakujÄ…co dobre wyniki daje ustawienie wierzchoÅ‚ków każdej skÅ‚adowej w strukturze drzewiastej, gdzie spójna skÅ‚adowa jest reprezentowana przez korzeÅ„. aby wykonać operacje (1) należy przejść do korzenia aby wykonać operacje (2) wystarczy korzeÅ„ jednej skÅ‚adowej okreÅ›lić jako potomka korzenia skÅ‚adowej drugiej. Przyjmijmy zasadÄ™ ze korzeÅ„ drzewa o mniejszej wysokoÅ›ci czynimy potomkiem. pð Przy takiej konstrukcji czas wykonania instrukcji (1) jest O(log n), czas wykonania instrukcji (2) jest O(1). Wyznaczenie wszystkich spójnych skÅ‚adowych to O(m log n) gdzie m jest liczbÄ… krawÄ™dzi a n liczbÄ… wierzchoÅ‚ków. 20 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Minimalne drzewa rozpinajÄ…ce pð Drzewo rozpinajÄ…ce (ang. spanning tree) grafu nieskierowanego G stanowi zbiór wierzchoÅ‚ków tego grafu wraz z podzbiorem jego krawÄ™dzi, takich że: Å‚Ä…czÄ… one wszystkie wierzchoÅ‚ki, czyli istnieje droga miedzy dwoma dowolnymi wierzchoÅ‚kami która skÅ‚ada siÄ™ tylko z krawÄ™dzi drzewa rozpinajÄ…cego. tworzÄ… one drzewo nie posiadajÄ…ce korzenia, nieuporzÄ…dkowane. Oznacza to że nie istniejÄ… żadne (proste) cykle. pð JeÅ›li graf G stanowi pojedynczÄ… spójnÄ… skÅ‚adowÄ… to drzewo rozpinajÄ…ce zawsze istnieje. Minimalne drzewo rozpinajÄ…ce (ang. minimal spanning tree) to drzewo rozpinajÄ…ce, w którym suma etykiet jego krawÄ™dzi jest najmniejsza ze wszystkich możliwych do utworzenia drzew rozpinajÄ…cych tego grafu. 21 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Minimalne drzewa rozpinajÄ…ce A A 28 24 28 15 C B D C B D 11 11 12 12 20 20 13 13 E F E F Graf nieskierowany Drzewo rozpinajÄ…ce 22 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Znajdowanie minimalnego drzewa rozpinajÄ…cego pð Istnieje wiele algorytmów. Jeden z nich to algorytm Kruskala, który stanowi proste rozszerzenie algorytmu znajdowania spójnych skÅ‚adowych. Wymagane zmiany to: należy rozpatrywać krawÄ™dzie w kolejnoÅ›ci zgodnej z rosnÄ…cÄ… wartoÅ›ciÄ… ich etykiet, należy doÅ‚Ä…czyć krawÄ™dz do drzewa rozpinajÄ…cego tylko w takim wypadku gdy jej koÅ„ce należą do dwóch różnych spójnych skÅ‚adowych. A A 24 24 (5) 28 15 (4) 15 C B D C B D 11 12 (2) 11 (1) 12 20 13 13 (3) E F E F Minimalne drzewo rozpinajÄ…ce Graf nieskierowany (w nawiasach podano kolejność dodawanych krawÄ™dzi) 23 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Znajdowanie minimalnego drzewa rozpinajÄ…cego pð Algorytm Kruskala jest dobrym przykÅ‚adem algorytmu zachÅ‚annego (ang. greedy algorithm), w przypadku którego podejmowany jest szereg decyzji, z których każdÄ… stanowi wybranie opcji najlepszej w danym momencie. Lokalnie podejmowane decyzje polegajÄ… w tym przypadku na wyborze krawÄ™dzi dodawanej do formowanego drzewa rozpinajÄ…cego. pð Za każdym razem wybierana jest krawÄ™dz o najmniejsze wartoÅ›ci etykiety, która nie narusza definicji drzewa rozpinajÄ…cego, zabraniajÄ…cej utworzenia cyklu. pð Dla algorytmu Kruskala można wykazać, ze jego rezultat jest optymalny globalnie, to znaczy że daje on w wyniku drzewo rozpinajÄ…ce o minimalnej wadze. pð Czas wykonania algorytmu jest O(m log m) gdzie m to jest wiÄ™ksza z wartoÅ›ci liczby wierzchoÅ‚ków i liczby krawÄ™dzi. 24 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Uzasadnienie poprawnoÅ›ci algorytmu Kruskala pð Niech G bÄ™dzie nieskierowanym grafem spójnym. (Dla niektórych etykiet dopuszczamy dodanie nieskoÅ„czenie malej wartoÅ›ci tak aby wszystkie etykiety byÅ‚y różne, graf G bÄ™dzie miaÅ‚ wobec tego unikatowe minimalne drzewo rozpinajÄ…ce, które bÄ™dzie jednym spoÅ›ród minimalnych drzew rozpinajÄ…cych grafu G o oryginalnych wagach). pð Niech ciÄ…g e1, e2, & , em oznacza wszystkie krawÄ™dzie grafu G w kolejnoÅ›ci zgodnej z rosnÄ…cÄ… wartoÅ›ciÄ… ich etykiet, rozpoczynajÄ…c od najmniejszej. pð Niech K bÄ™dzie drzewem rozpinajÄ…cym grafu G o odpowiednio zmodyfikowanych etykietach, utworzonym przez zastosowanie algorytmu Kruskala, a T niech bÄ™dzie unikatowym minimalnym drzewem rozpinajÄ…cym grafu G. 25 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Uzasadnienie poprawnoÅ›ci algorytmu Kruskala pð Należy udowodnić ze K i T stanowiÄ… to samo drzewo. JeÅ›li sÄ… różne musi istnieć co najmniej jedna krawÄ™dz, która należy do jednego z nich a nie należy do drugiego. pð Niech ei oznacza pierwsza taka krawÄ™dz spoÅ›ród uporzÄ…dkowanych krawÄ™dzi, to znaczy każda z krawÄ™dzi e1, e2, & , ei-1 albo należy do obu drzew K i T albo nie należy do żadnego z nich. pð IstniejÄ… dwa przypadki w zależnoÅ›ci czy krawÄ™dz ei należy do drzewa K czy do drzewa T. W każdym z tych przypadków wykażemy sprzeczność, co bÄ™dzie stanowić dowód, ze ei nie może istnieć, a stÄ…d że K=T, oraz że K stanowi minimalne drzewo rozpinajÄ…ce grafu G. 26 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Uzasadnienie poprawnoÅ›ci algorytmu Kruskala pð Przypadek 1: krawÄ™dz ei należy do T, ale nie należy do K. Jeżeli algorytm Kruskala odrzuca ei, oznacza to ze ei formuje cykl z pewna droga P, utworzona z uprzednio wybranych krawÄ™dzi drzewa K. Jeżeli krawÄ™dzie drogi P należą to K to ei należą także do T. A wiec P + ei utworzyÅ‚oby cykl w T co Droga P (linia ciÄ…gÅ‚a) należy jest sprzeczne z definicja drzewa zarówno do drzewa T jak i K, rozpinajÄ…cego. Stad niemożliwe jest aby krawÄ™dz ei należy tylko do T. ei należaÅ‚a do T a nie należaÅ‚a do K. 27 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Uzasadnienie poprawnoÅ›ci algorytmu Kruskala pðPrzypadek 2: krawÄ™dz ei należy do K, ale nie należy do T. Niech krawÄ™dz ei Å‚Ä…czy wierzchoÅ‚ki u i v. Ponieważ drzewo T jest spójne, musi istnieć w f w T pewna acykliczna droga z wierzchoÅ‚ka u do x v. Niech nosi ona nazwÄ™ Q. Ponieważ w skÅ‚ad Q nie wchodzi ei, Q + ei tworzy cykl prosty w u grafie G. 1. krawÄ™dz ei posiada najwyższÄ… wartość etykiety. ei v MusiaÅ‚oby to oznaczać ze K zawiera cykl co jest niemożliwe. Droga Q (linia ciÄ…gÅ‚a) 2. na drodze Q istnieje krawÄ™dz f która ma wartość etykiety wyższÄ… niż ei. Można by wiec usunąć f a należy do drzewa T, wprowadzić ei nie niszczÄ…c spójnoÅ›ci. A wiec można dodać krawÄ™dz rozpiÄ™te drzewo miaÅ‚oby wartość mniejsza niż ei i usunąć krawÄ™dz f wartość dla T co jest w sprzecznoÅ›ci z poczÄ…tkowym twierdzeniem ze T jest minimalne. 28 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Algorytm przeszukiwania w gÅ‚Ä…b pð Jest to podstawowa metoda badania grafów skierowanych. pð Bardzo podobna do stosowanych dla drzew, w których startuje siÄ™ od korzenia i rekurencyjnie bada wierzchoÅ‚ki potomne każdego odwiedzonego wierzchoÅ‚ka. pð Trudność polega na tym ze w grafie mogÄ… pojawiać siÄ™ cykle& Należy wobec tego znaczyć wierzchoÅ‚ki już odwiedzone i nie wracać wiÄ™cej do takich wierzchoÅ‚ków. pð Z uwagi na fakt, że w celu unikniÄ™cia dwukrotnego odwiedzenia tego samego wierzchoÅ‚ka jest on odpowiednio oznaczany, graf w trakcie jego badania zachowuje siÄ™ podobnie do drzewa. pð W rzeczywistoÅ›ci można narysować drzewo, którego krawÄ™dzie rodzic- potomek bÄ™dÄ… niektórymi krawÄ™dziami przeszukiwanego grafu G. pð Takie drzewo nosi nazwÄ™ drzewa przeszukiwania w gÅ‚Ä…b (ang. depth-first- search) dla danego grafu. 29 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Algorytm przeszukiwania w gÅ‚Ä…b Las przeszukiwania: dwa drzewa o korzeniach a, d a a b d b d c f e c f e Jedno z możliwych drzew a przeszukiwania Graf skierowany b d c f e Las przeszukiwania w gÅ‚Ä…b. 30 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Drzewo przeszukiwania w gÅ‚Ä…b 6 a 5 krawÄ™dz b d 4 wsteczna c f 1 3 e 2 pðPo (podczas) konstruowaniu drzewa przeszukiwania w gÅ‚Ä…b można ponumerować jego wierzchoÅ‚ki w kolejnoÅ›ci wstecznej (ang. post-order). 31 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Rekurencyjna funkcja przeszukiwania w gÅ‚Ä…b: void dfs enum MARKTYPE {VISITED, UNVISITED}; typedef struct CELL *LIST; typedef struct{ struct CELL { enum MARKTYPE mark; NODE nodeName; LIST successors; LIST next; } GRAPH[MAX]; }; void dfs(NODE u, GRAPH G) { LIST p; /* lista sÄ…siedztwa dla wierzchoÅ‚ka u */ NODE v; /* wierzchoÅ‚ek w komórce wskazywanej przez p */ G[u].mark = VISITED; p = G[u].successors; while (p != NULL) { v = p->nodeName; if (G[y].mark == UNVISITED) dfs(v, G); p = p->next; } } 32 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Znajdowanie cykli w grafie skierowanym pð Podczas przeszukiwania w gÅ‚Ä…b grafu skierowanego G można wszystkim wierzchoÅ‚kom przypisać numery zgodne z kolejnoÅ›ciÄ… wstecznÄ… w czasie rzÄ™du O(m). pð KrawÄ™dzie wsteczne to takie dla których poczÄ…tki sÄ… równe lub mniejsze koÅ„com ze wzglÄ™du na numeracje wstecznÄ…. pð Zawsze gdy istnieje krawÄ™dz wsteczna w grafie musi istnieć cykl. pð Prawdziwe jest również twierdzenie odwrotne. Aby stwierdzić czy w grafie wystÄ™puje cykl należy przeprowadzić numeracjÄ™ wstecznÄ… a nastÄ™pnie sprawdzić wszystkie krawÄ™dzie. pð CaÅ‚kowity czas wykonania testu cyklicznoÅ›ci to O(m), gdzie m to wiÄ™ksza z wartoÅ›ci liczby wierzchoÅ‚ków i liczby krawÄ™dzi. 33 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Sortowanie topologiczne pð Załóżmy, że graf skierowany G jest acykliczny. pð Dla każdego grafu możemy okreÅ›lić las poszukiwania w gÅ‚Ä…b, okreÅ›lajÄ…c numeracjÄ™ wstecznÄ… jego wierzchoÅ‚ków. pð Załóżmy, że (n1, n2, & , nk) okreÅ›la listÄ™ wierzchoÅ‚ków grafu G w kolejnoÅ›ci odwrotnej do numeracji wstecznej. To znaczy: n1 jest wierzchoÅ‚kiem opatrzonym numerem n, n2 wierzchoÅ‚kiem opatrzonym numerem n-1 i ogólnie wierzchoÅ‚ek ni jest opatrzony numerem n-i+1. pð Kolejność wierzchoÅ‚ków na tej liÅ›cie ma ta wÅ‚asność, że wszystkie krawÄ™dzie grafu G biegnÄ… od poczÄ…tku do koÅ„ca, tzn. poczÄ…tek poprzedza koniec. 34 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Sortowanie topologiczne pð Takie uporzÄ…dkowanie nazywamy topologicznym (ang. topological order), a proces znajdowania takiego uporzÄ…dkowania to sortowanie topologiczne (ang. topological sorting). pð Jedynie grafy acykliczne posiadajÄ… uporzÄ…dkowanie topologiczne. pð WykonujÄ…c poszukiwanie w gÅ‚Ä…b możemy je okreÅ›lić w czasie O(m). pð Jedna z możliwoÅ›ci: odkÅ‚adać kolejno znalezione wierzchoÅ‚ki na stos . Po zakoÅ„czeniu lista znajdujÄ…ca siÄ™ na stosie bÄ™dzie reprezentować uporzÄ…dkowanie topologiczne grafu. 35 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Sortowanie topologiczne UporzÄ…dkowanie topologiczne to (d,e,c,f,b,a) 1 2 4 6 d a b c d c e 3 5 f e b f a Las przeszukiwania w gÅ‚Ä…b Skierowany graf cykliczny 36 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Sortowanie topologiczne - zastosowania pð UporzÄ…dkowanie topologiczne przydaje siÄ™ wówczas, gdy istniejÄ… pewne ograniczenia odnoÅ›nie kolejnoÅ›ci w jakiej majÄ… być wykonywane zadania. pð JeÅ›li krawÄ™dz wiodÄ…cÄ… od wierzchoÅ‚ka u do wierzchoÅ‚ka v jest rysowana wówczas, gdy zadanie u musi zostać wykonane przed zadaniem v, to uporzÄ…dkowaniem zapewniajÄ…cym wykonanie wszystkich żądaÅ„ jest wÅ‚aÅ›nie uporzÄ…dkowanie topologiczne. pð Podobny przykÅ‚ad to graf wywoÅ‚aÅ„ nierekurencyjnego zbioru funkcji, kiedy należy przeanalizować każdÄ… funkcje dopiero po dokonaniu analizy funkcji jÄ… wywoÅ‚ujÄ…cej. pð JeÅ›li krawÄ™dzie wiodÄ… od funkcji wywoÅ‚ujÄ…cych do wywoÅ‚ywanych, kolejność, w której należy przeprowadzić takie analizy, to odwrócenie porzÄ…dku topologicznego, czyli uporzÄ…dkowanie wsteczne. pð Zapewnia to że każda funkcja zostanie przeanalizowana dopiero po dokonaniu analizy wszystkich innych wywoÅ‚ywanych przez niÄ… funkcji. 37 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Sortowanie topologiczne - zastosowania pðIstnienie cyklu w grafie reprezentujÄ…cym priorytety zadaÅ„ mówi o tym, że nie istnieje takie uporzÄ…dkowanie, dziÄ™ki któremu możliwe byÅ‚oby wykonanie wszystkich zadaÅ„. pðIstnienie cyklu w grafie wywoÅ‚aÅ„ pozwala stwierdzić wystÄ™powanie rekurencji. 38 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Problem osiÄ…galnoÅ›ci pð Naturalne pytanie zwiÄ…zane z grafem skierowanym jest: które wierzchoÅ‚ki sÄ… osiÄ…galne z danego wierzchoÅ‚ka u przy zaÅ‚ożeniu, że po grafie można siÄ™ poruszać tylko zgodnie z kierunkiem krawÄ™dzi? Taki zbiór wierzchoÅ‚ków okreÅ›la siÄ™ mianem zbioru osiÄ…galnoÅ›ci (ang. reachable set) danego wierzchoÅ‚ka u. pð Możemy wykorzystać rekurencyjnÄ… funkcje poszukiwania w gÅ‚Ä…b. pð CaÅ‚kowity czas wykonania takiego zapytania to O(m n). 39 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Znajdowanie spójnych skÅ‚adowych pð Do znajdowania spójnych skÅ‚adowych możemy użyć algorytmu poszukiwania w gÅ‚Ä…b. pð Traktujemy graf nieskierowany jako graf skierowany, w którym każda krawÄ™dz nieskierowana zostaÅ‚a zastÄ…piona dwiema krawÄ™dziami skierowanymi wiodÄ…cymi w obu kierunkach. pð Do reprezentacji grafu używamy list sÄ…siedztwa. pð Tworzymy las przeszukiwania w gÅ‚Ä…b grafu skierowanego. Każde drzewo w tym lesie odpowiada jednej skÅ‚adowej spójnoÅ›ci grafu nieskierowanego. pð Czas wykonania algorytmu O(m) (przy użyciu struktury drzewiastej, patrz poprzedni wykÅ‚ad, czas wykonania wynosi O(m log n)). 40 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Algorytm Dijkstry znajdowania najkrótszych dróg. pðRozpatrujemy graf G (skierowany lub nieskierowany), w którym wszystkie krawÄ™dzie zaetykietowano wartoÅ›ciami reprezentujÄ…cymi ich dÅ‚ugoÅ›ci. pðDÅ‚ugość (ang. distance) danej drogi stanowi wartość sumy etykiet zwiÄ…zanych z niÄ… krawÄ™dzi. Minimalna odlegÅ‚ość z wierzchoÅ‚ka u do wierzchoÅ‚ka v to minimalna dÅ‚ugość którejÅ› z dróg od u do v. 41 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Algorytm Dijkstry znajdowania najkrótszych dróg. pð Traktujemy wierzchoÅ‚ek s jako wierzchoÅ‚ek zródÅ‚owy. W etapie poÅ›rednim wykonywania algorytmu w grafie G istniejÄ… tzw. wierzchoÅ‚ki ustalone (ang. settled), tzn. takie dla których znane sÄ… odlegÅ‚oÅ›ci minimalne. W Graf G szczególnoÅ›ci zbiór takich wierzchoÅ‚ków zawiera również wierzchoÅ‚ek s. v s pð Dla nieustalonego wierzchoÅ‚ka v należy droga zapamiÄ™tać dÅ‚ugość najkrótszej drogi specjalna specjalnej (ang. special path) czyli takiej która rozpoczyna siÄ™ w wierzchoÅ‚ku zródÅ‚owym, wiedzie przez ustalone wierzchoÅ‚ki, i na ostatnim etapie przechodzi z obszaru ustalonego do wierzchoÅ‚ka v. 42 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Algorytm Dijkstry znajdowania najkrótszych dróg. pð Dla każdego wierzchoÅ‚ka u zapamiÄ™tujemy wartość dist(u). pð JeÅ›li u jest wierzchoÅ‚kiem ustalonym, to dist(u) jest dÅ‚ugoÅ›ciÄ… najkrótszej drogi ze zródÅ‚a do wierzchoÅ‚ka u. pð JeÅ›li u nie jest wierzchoÅ‚kiem ustalonym, to dist(u) jest dÅ‚ugoÅ›ciÄ… drogi specjalnej ze zródÅ‚a do u. pð Na czym polega ustalanie wierzchoÅ‚ków: znajdujemy wierzchoÅ‚ek v który jest nieustalony ale posiada najmniejszÄ… dist(v) ze wszystkich wierzchoÅ‚ków nieustalonych przyjmujemy wartość dist(v) za minimalnÄ… odlegÅ‚ość z s do v dostosowujemy wartoÅ›ci wszystkich dist(u) dla innych wierzchoÅ‚ków, które nie sÄ… ustalone, wykorzystujÄ…c fakt, że wierzchoÅ‚ek v jest już ustalony. Czyli porównujemy stare dist(u) z wartoÅ›ciÄ… dist(v)+etykieta(v, u) jeżeli taka (v, u) krawÄ™dz istnieje. pð Czas wykonania algorytmu jest O(m log n). 43 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Algorytm Dijkstry znajdowania najkrótszych dróg. Etapy wykonania algorytmu Dijkstry L ETAPY ustalania wierzchoÅ‚ków 28 24 MIASTO (1) (2) (3) (4) (5) H 0* 0* 0* 0* 0* 15 P 13 13 13* 13* 13* M W K M INF INF 33 33 33* 12 11 W INF INF 25 25* 25* 20 L INF 35 35 35 35 P H K 11 11* 11* 11* 11* 13 44 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Indukcyjny dowód poprawnoÅ›ci algorytmu pð W celu wykazania poprawnoÅ›ci algorytmu Dijkstry należy przyjąć, że etykiety krawÄ™dzi sÄ… nieujemne. pð Indukcyjny dowód poprawnoÅ›ci wzglÄ™dem k prowadzi do stwierdzenia że: 1. dla każdego wierzchoÅ‚ka ustalonego u, wartość dist(u) jest minimalnÄ… odlegÅ‚oÅ›ciÄ… z s do u, a najkrótsza droga do u skÅ‚ada siÄ™ tylko z wierzchoÅ‚ków ustalonych. 2. dla każdego nieustalonego wierzchoÅ‚ka u, wartość dist(u) jest minimalnÄ… dÅ‚ugoÅ›ciÄ… drogi specjalnej z s do u (jeÅ›li droga nie istnieje wartość wynosi INF). 45 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Indukcyjny dowód poprawnoÅ›ci algorytmu pðPodstawa: Dla k=1 wierzchoÅ‚ek s jest jedynym wierzchoÅ‚kiem ustalonym. Inicjalizujemy dist(s) wartoÅ›ciÄ… 0, co speÅ‚nia warunek (1). Dla każdego innego wierzchoÅ‚ka u, dist(u) jest inicjalizowane wartoÅ›ciÄ… etykiety krawÄ™dzi (s, u), o ile taka istnieje. Jeżeli nie istnieje, wartoÅ›ciÄ… inicjalizacji jest INF. Zatem speÅ‚niony jest również warunek (2). 46 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Indukcyjny dowód poprawnoÅ›ci algorytmu pð Krok indukcyjny: Załóżmy, ze warunki (1) i (2) za speÅ‚nione po ustaleniu k wierzchoÅ‚ków oraz niech v bÄ™dzie (k+1) ustalonym wierzchoÅ‚kiem. Warunek (1) jest wciąż speÅ‚niony ponieważ dist(v) jest najmniejsza dÅ‚ugoÅ›ciÄ… drogi z s do v. pð Załóżmy, że tak nie jest. MusiaÅ‚a by wiec istnieć hipotetyczna krótsza droga do v wiodÄ…ca przez w i u. Jednakże wierzchoÅ‚ek v zostaÅ‚ obrany jako k+1 ustalony, co oznacza, ze w tym momencie dist(u) nie może być mniejsze od dist(v), gdyż wówczas jako (k+1) wierzchoÅ‚ek wybrany zostaÅ‚by wierzchoÅ‚ek u. pð Na podstawie warunku (2) hipotezy indukcyjnej wiadomo, ze dist(u) jest minimalna dÅ‚ugoÅ›ciÄ… drogi specjalnej wiodÄ…cej do u. Jednak droga z s przez w do u jest drogÄ… specjalnÄ…, tak wiÄ™c jej dÅ‚ugość równa jest co najmniej dist(u). StÄ…d domniemana krótsza droga z s do v wiodÄ…ca przez w i u ma dÅ‚ugość równÄ… co najmniej dist(v), ponieważ pierwsza jej część, - z s do u ma dÅ‚ugość dist(u), a dist(u) Å‚ð dist(v). StÄ…d warunek (1) jest speÅ‚niony dla k+1 wierzchoÅ‚ków. Graf G Hipotetyczna krótsza droga do v v s wiodÄ…ca przez w i u. w u 47 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Indukcyjny dowód poprawnoÅ›ci algorytmu pðKrok indukcyjny ciÄ…g dalszy: Teraz należy pokazać, że warunek (2) jest speÅ‚niony po dodaniu do wierzchoÅ‚ków ustalonych wierzchoÅ‚ka v. pðWezmy pod uwagÄ™ pewien wierzchoÅ‚ek u, który wciąż pozostaje nieustalony po dodaniu v do wierzchoÅ‚ków ustalonych. W najkrótszej drodze specjalnej do u musi istnieć pewien wierzchoÅ‚ek przedostatni. WierzchoÅ‚kiem tym może być zarówno v, jak i pewien inny wierzchoÅ‚ek w. pðPrzyjmijmy, że wierzchoÅ‚kiem przedostatnim jest v. DÅ‚ugość drogi z s przez v do u wynosi dist(v) + wartość etykiety v ®ð u. pðPrzyjmijmy, że wierzchoÅ‚kiem przedostatnim jest w. Na podstawie warunku (1) hipotezy indukcyjnej można stwierdzić, że najkrótsza droga z s do w skÅ‚ada siÄ™ jedynie z wierzchoÅ‚ków, które zostaÅ‚y ustalone przed v, stÄ…d wierzchoÅ‚ek v nie wystÄ™puje w tej drodze. pðA wiÄ™c dÅ‚ugość drogi specjalnej do u siÄ™ nie zmienia po dodaniu v do wierzchoÅ‚ków ustalonych. pðPonieważ w momencie ustalania wierzchoÅ‚ka v przeprowadzona jest operacja dostosowywania dist(u), warunek (2) jest speÅ‚niony. Graf G WierzchoÅ‚ki ustalone Dwie możliwoÅ›ci okreÅ›lenia v przedostatniego wierzchoÅ‚ka s u w w drodze specjalnej do u. 48 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Algorytm Floyda-Warshalla znajdowania najkrótszych dróg. pð JeÅ›li potrzebne jest poznanie minimalnych odlegÅ‚oÅ›ci miedzy wszystkimi parami wierzchoÅ‚ków w grafie o n wierzchoÅ‚kach, które posiadajÄ… etykiety o wartoÅ›ciach nieujemnych, można uruchomić algorytm Dijkstry dla każdego z n wierzchoÅ‚ków jako wierzchoÅ‚ka zródÅ‚owego. pð Czas wykonania algorytmu Dijsktry wynosi O(m log n ), gdzie m oznacza wiÄ™kszÄ… wartość z liczby wierzchoÅ‚ków i liczby krawÄ™dzi. Znalezienie w ten sposób minimalnych odlegÅ‚oÅ›ci miedzy wszystkimi parami wierzchoÅ‚ków zajmuje czas rzÄ™du O(m n log n). pð JeÅ›li m jest bliskie swojej maksymalnej wartoÅ›ci m ð n2 to można skorzystać z implementacji algorytmu Dijkstry który dziaÅ‚a w czasie O(n2). Wykonanie go n razy daje czas rzÄ™du O(n3). pð Istnieje inny algorytm znajdowania minimalnych odlegÅ‚oÅ›ci miedzy wszystkimi parami wierzchoÅ‚ków, noszÄ…cy nazwÄ™ algorytmu Floyda- Warshalla. pð Jego wykonanie zajmuje czas rzÄ™du O(n3). Operuje na macierzach sÄ…siedztwa a nie listach sÄ…siedztwa i jest koncepcyjnie prostszy. 49 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Algorytm Floyda-Warshalla znajdowania najkrótszych dróg. pð Podstawa algorytmu jest dziaÅ‚anie polegajÄ…ce na rozpatrywaniu po kolei każdego wierzchoÅ‚ka grafu jako elementu centralnego (ang. pivot). pð Kiedy wierzchoÅ‚ek u jest elementem centralnym, staramy siÄ™ wykorzystać fakt, że u jest wierzchoÅ‚kiem poÅ›rednim miedzy wszystkimi parami wierzchoÅ‚ków. pð Dla każdej pary wierzchoÅ‚ków, na przykÅ‚ad v i w, jeÅ›li suma etykiet krawÄ™dzi (v, u) oraz (u, w) (na rysunku d+e) , jest mniejsza od bieżąco rozpatrywanej etykiety f krawÄ™dzi wiodÄ…cej od v do w, to wartość f jest zastÄ™powana wartoÅ›ciÄ… d+e. 0 0 Node u, v, w; for (v = 0; w < MAX; v++) for (w=0; w < MAX; w++) 1 1 dist[v][w] = edge[v][w]; & & u for (u=0; u< MAX; u++) d e for (v=0; v< MAX; v++) v w for (w=0; wf if( dist[v][u]+dist[u][w] < dist[v][w]) & & dist[v][w] = dist [v][u] + dist [u][w]; n-1 n-1 edge[v][w] etykieta krawÄ™dzi, wierzchoÅ‚ki numerowane 50 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Algorytm Floyda-Warshalla - PrzykÅ‚ad Macierz edge, która odzwierciedla poczÄ…tkowÄ… postać macierzy dist 0 28 24 0 1 2 3 4 5 15 0 0 24 INF INF INF 28 4 5 1 1 24 0 11 INF INF INF 2 INF 11 0 13 INF INF 12 11 20 3 INF INF 13 0 20 12 3 2 4 INF INF INF 20 0 15 13 5 28 INF INF 12 15 0 51 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Algorytm Floyda-Warshalla - PrzykÅ‚ad Macierz dist, po użyciu wierzchoÅ‚ka 0 jako elementu centralnego 0 28 24 0 1 2 3 4 5 15 0 0 24 INF INF INF 28 4 5 1 1 24 0 11 INF INF 52 2 INF 11 0 13 INF INF 12 11 20 3 INF INF 13 0 20 12 3 2 4 INF INF INF 20 0 15 13 5 28 52 INF 12 15 0 52 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Algorytm Floyda-Warshalla - PrzykÅ‚ad Macierz dist, po użyciu wierzchoÅ‚ka 1 jako elementu centralnego 0 28 24 0 1 2 3 4 5 15 0 0 24 35 INF INF 28 4 5 1 1 24 0 11 INF INF 52 2 35 11 0 13 INF 63 12 11 20 3 INF INF 13 0 20 12 3 2 4 INF INF INF 20 0 15 13 5 28 52 63 12 15 0 itd& itd& 53 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Algorytm Floyda-Warshalla - PrzykÅ‚ad Ostateczna postać macierzy dist. 0 28 24 0 1 2 3 4 5 15 0 0 24 35 40 43 28 4 5 1 1 24 0 11 24 44 52 2 35 11 0 13 33 25 12 11 20 3 40 24 13 0 20 12 3 2 4 43 44 33 20 0 15 13 5 28 36 25 12 15 0 54 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Uzasadnienie poprawnoÅ›ci algorytmu Floyda-Warshalla pð Na dowolnym etapie dziaÅ‚ania algorytmu Floyda- Warshalla odlegÅ‚ość z wierzchoÅ‚ka v do wierzchoÅ‚ka w stanowi dÅ‚ugość najkrótszej z tych dróg, które wiodÄ… jedynie przez wierzchoÅ‚ki użyte dotÄ…d jako elementy centralne. numery wyższe od k pð Ponieważ wszystkie wierzchoÅ‚ki zostajÄ… w koÅ„cu numery niższe od k użyte jako elementy centralne, elementy dist[v][w] zawierajÄ… po zakoÅ„czeniu dziaÅ‚aÅ„ minimalne dÅ‚ugoÅ›ci wszystkich możliwych dróg. v w pð Definiujemy k-drogÄ™ z wierzchoÅ‚ka v do wierzchoÅ‚ka w jako drogÄ™ z v do w takÄ…, że żaden jej wierzchoÅ‚ek poÅ›redni nie ma numeru wyższego k-droga od k. pð Należy zauważyć, że nie ma ograniczenia odnoÅ›nie tego, że v lub w majÄ… mieć wartość k lub mniejszÄ…. pð k=-1 oznacza że droga nie posiada wierzchoÅ‚ków poÅ›rednich. 55 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Dowód indukcyjny pð Teza indukcyjna S(k): jeżeli etykiety krawÄ™dzi maja wartoÅ›ci nieujemne, to po przebiegu k pÄ™tli, element dist[v][w] ma wartość najkrótszej k drogi z v do w lub ma wartość INF, jeżeli taka droga nie istnieje. pð Podstawa: PodstawÄ… jest warunek k = -1. KrawÄ™dzie i drogi skÅ‚adajÄ…ce siÄ™ z pojedynczego wierzchoÅ‚ka sÄ… jedynymi (-1) drogami. pð Krok indukcyjy Załóżmy ze S(k) jest speÅ‚nione i rozważmy co siÄ™ dzieje z elementami dist[v][w] w czasie k+1 przebiegu pÄ™tli. Załóżmy, że P jest najkrótszÄ… (k+1) drogÄ… wiodÄ…ca z v do w. Mamy do czynienia z dwoma przypadkami, w zależnoÅ›ci czy droga P prowadzi przez wierzchoÅ‚ek k+1 . k-drogÄ™ P można rozbić k-droga Q k-droga R v k+1 w na dwie k-drogi, Q oraz R. 56 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Dowód indukcyjny pð Przypadek 1: Jeżeli P jest k-drogÄ…, to znaczy, kiedy P nie wiedzie przez wierzchoÅ‚ek k+1, to na podstawie hipotezy indukcyjnej wartość elementu dist[v][w] jest równa dÅ‚ugoÅ›ci P po zakoÅ„czeniu k-tej iteracji. Nie można zmienić wartoÅ›ci dist[v][w] podczas przebiegu wykonywanego dla wierzchoÅ‚ka k+1 traktowanego jako element centralny, gdyż nie istniejÄ… żadne krótsze (k+1)-drogi. pð Przypadek 2: Jeżeli P jest (k+1)- droga, można zaÅ‚ożyć, że P przechodzi przez wierzchoÅ‚ek k+1 tylko raz, gdyż cykl nigdy nie może spowodować zmniejszenia odlegÅ‚oÅ›ci (przy zaÅ‚ożeniu że wszystkie etykiety maja wartoÅ›ci nieujemne). StÄ…d droga P skÅ‚ada siÄ™ z k-drogi Q, wiodÄ…cej od wierzchoÅ‚ka v do k+1, oraz k-drogi R, wiodÄ…cej od wierzchoÅ‚ka k+1 do w. Na podstawie hipotezy indukcyjnej wartoÅ›ci elementów dist[v][k+1] oraz dist[k+1][w] bÄ™dÄ… dÅ‚ugoÅ›ciami dróg odpowiednio, Q i R, po zakoÅ„czeniu k-tej iteracji. 57 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Dowód indukcyjny pð Ostatecznie wnioskujemy, że w (k+1) przebiegu, wartoÅ›ciÄ… elementu dist[v][w] staje siÄ™ dÅ‚ugość najkrótszej (k+1)-drogi dla wszystkich wierzchoÅ‚ków v oraz w. pð Jest to twierdzenie S(k+1), co oznacza koniec kroku indukcyjnego. pð Wezmy teraz, że k=n-1. Oznacza to, że wiemy iż po zakoÅ„czeniu wszystkich n przebiegów, wartość dist[v][w] bÄ™dzie minimalnÄ… odlegÅ‚oÅ›ciÄ… dowolnej (n-1)-drogi wiodÄ…cej z wierzchoÅ‚ka v do w. Ponieważ każda droga jest (n-1) drogÄ…, wiÄ™c dist[v][w] jest minimalnÄ… dÅ‚ugoÅ›ciÄ… drogi wiodÄ…cej z wierzchoÅ‚ka v do w. 58 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ 2011/2012 Podsumowanie informacji o algorytmach grafowych PROBLEM ALGORYTM(Y) CZAS WYKONANIA Minimalne drzewo rozpinajÄ…ce Algorytm Kruskala O(m log n) Znajdowanie cykli Przeszukiwanie w gÅ‚Ä…b O(m) UporzÄ…dkowanie topologiczne Przeszukiwanie w gÅ‚Ä…b O(m) OsiÄ…galność w przypadku Przeszukiwanie w gÅ‚Ä…b O(m) pojedynczego zródÅ‚a Spójne skÅ‚adowe Przeszukiwanie w gÅ‚Ä…b O(m) Najkrótsza droga Algorytm Dijskry O(m log n) dla pojedyncz. zródÅ‚a Najkrótsza droga dla Algorytm Dijskry O(m n log n) wszystkich par Algorytm Floyda O(n3) 59 29.11.2011 Prof. dr hab. Elżbieta Richter-WÄ…s