To tylko jedna z 5 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
TEORIA GRAFÓW
Definicje
Graf (nieskierowany) - G = (V;E) _ struktura składaj¡ca się ze: zbioru wierzchołków V = {v1; v2; : : : ; vn} oraz zbioru krawędzi E = {e1; e2; : : : ; Em}
Graf skierowany - dla każdej krawędzi (oznaczanej tutaj jako łuk) para wierzchołków incydentnych jest par¡ uporz¡dkowan¡ {u; vg}. Zatem w grafie skierowanym {u; v} != {v; u} ({u; v} i {v; u} oznacza dwa różne łuki, podczas gdy w grafie nieskierowanym (u; v) i (v; u) to ta sama krawędź, tzn. (u; v) = (v; u)). Rozmiar grafu będziemy identy_kować przez liczbę wierzchołków n oraz liczbę krawędzi (łuków) m. Droga - (ścieżka) z wierzch. v1 do vk w grafie skierowanym G to ci¡g łuków {{v1; v2}; {v2; v3}; …; {vk-1; vk}}, który możemy jednoznacznie określić poprostu przez ci¡g (permutację) wierzchołków, przez które droga ta przebiega, tj. {v1; v2; : : : ; vk-1; vk}. Wagą drogi będziemy określać sumę wag łuków ją tworzących.
Cykl - droga zamknięta, tzn. taka, że v1 = vk.
Graf acykliczny - graf nie zawierający cykli.
Graf spójny (nieskierowany) - graf, dla którego istnieje droga między każdą parą wierzchołków. Spójny graf skierowany to taki, którego wersja nieskierowana jest spójna.
Drzewo - spójny, nieskierowany graf acykliczny. W drzewie, jak w każdym grafie spójnym (nieskierowanym), istnieje droga między każdą parą wierzchołków. Zatem dołączenie nowej krawędzi spowoduje powstanie cyklu, a usunięcie jakiejkolwiek krawędzi z drzewa spowoduje jego rozspójnienie. Wreszcie, w drzewie m = n-1.
Drzewo rozpinające (spinające) - T = (V T ;ET ) _ podgraf (nieskierowanego, spójnego) grafu G = (V;E), który jest spójny i V T = V . Graf spójny może zawierać wiele (do n^(n-2)) różnych drzew rozpinających, z których to o najmniejszej wadze nazywamy Minimalnym Drzewem Rozpinającym (Spinającym) - MST (ang. Minimum Spanning Tree).
Struktury grafowe
Macierz wag O(n2)
tablica 2-wymiarowa o rozmiarze n _ n, w której wartość na przecięciu i-tego wiersza i j-tej kolumny oznacza wagę krawędzi (i;j) (łuku fi; jg). Jeśli dany graf nie zawiera krawędzi (i; j) to w odpowiadającej jej komórce macierzy wpisujemy wartość ∞. Wartości wyróżnione (zera, wartości ujemne, nieskończoności, znaki nienumeryczne) znajdują się też na przekątnej macierzy (brak krawędzi typu (i; i)). Zauważmy również, że macierz dla grafu nieskierowanego jest zawsze symetryczna (w takim wypadku można również przechowywać tylko połowę macierzy).
Lista krawędzi O(m)
tablica 2-wymiarowa o rozmiarze m _ 3 (lub 3 tablice liniowe o długości m), gdzie pierwsza kolumna (tablica) zawiera wierzchołki początkowe, druga kolumna (tablica) _ wierzchołki końcowe , a trzecia kolumna (tablica) _ wagi wszystkich krawędzi grafu. Krawędzie nieistniejące nie muszą być tutaj przechowywane.
(…)
…
polega na dołączaniu kolejno krawędzi w porządku ich niemalejących wag , o ile dołączana krawędź nie utworzy cyklu z już wybranymi krawędziami. Ważna jest efektywna metoda na sprawdzanie cykli - np. tablica o dł n do malowania wierzchołków, tablica do przechowywania ilości elementów poddrzew
Złożoność obliczeniowa: Kolorowanie wierzchołków - O(n)
Posortowanie struktury - O(m logm)
Sprawdzanie kolejno…
… będzie n - 1. Intuicyjnie, najkorzystniej jest zastosować do tego algorytmu struktury pozwalające na efektywne wyszukiwanie wierzchołków incydentnych w danym, a więc np. połączone listy sąsiadów.
Złożoność obliczeniowa: n-1 iteracji (dołączanie wierzchołków)
Znalezienie kolejnego wierzchołka do dołączenia będzie w takim wypadku wymagało przejrzenia list struktury odpowiadających wierzchołkom…
… należy jeszcze dokonać relaksacji łuków wychodzących z ustalonego _ O(n).
O(n2)
Możliwa jest jednak taka implementacja algorytmu, aby osiągnąć złożoność O(mlog n)
Bellman - Ford
Umożliwia, w przeciwieństwie do algorytmu Dijkstry, wyznaczanie najkrótszych dróg z wyznaczonego węzła do pozostałych przy dodatnich i ujemnych wagach. Warunkiem jest, aby graf nie zawierał cykli o ujemnej wadze, osiągalnych…
... zobacz całą notatkę
Komentarze użytkowników (0)