Ogólnie
Na poczatku definicja grafu, potem kilka algorytmów:
- Problem najkrótszej ścieżki
- Minimalne drzewo rozpinające
- Przeszukiwanie grafu
- Problem komiwojażera
Na poczatku definicja grafu, potem kilka algorytmów:
Graf to – w uproszczeniu – zbiór wierzchołków, które mogą być połączone krawędziami, w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków. Grafy to podstawowy obiekt rozważań teorii grafów.
Wierzchołki grafu zwykle są numerowane i czasem stanowią reprezentację jakichś obiektów, natomiast krawędzie mogą wówczas obrazować relacje między takimi obiektami. Krawędzie mogą mieć wyznaczony kierunek, a graf zawierający takie krawędzie jest grafem skierowanym. Krawędź może posiadać także wagę, to znaczy przypisaną liczbę, która określa na przykład odległość między wierzchołkami (jeśli na przykład graf jest reprezentacją połączeń między miastami). W grafie skierowanym wagi mogą być zależne od kierunku przechodzenia przez krawędź (np. jeśli graf reprezentuje trud poruszania się po jakimś terenie, to droga pod górkę będzie miała przypisaną większą wagę niż z górki).
Problem najkrótszej ścieżki jest zagadnieniem szczególnie istotnym w informatyce. Polega on na znalezieniu w grafie ważonym najkrótszego połączenia pomiędzy danymi wierzchołkami. Szczególnymi przypadkami tego problemu są problem najkrótszej ścieżki od jednego wierzchołka do wszystkich innych oraz problem najkrótszej ścieżki pomiędzy wszystkimi parami wierzchołków.
Okazuje się, że żeby znaleźć najkrótszą ścieżkę pomiędzy dwoma wierzchołkami grafu trzeba (w pesymistycznym przypadku) znaleźć najkrótsze ścieżki od wierzchołka wyjściowego do wszystkich innych wierzchołków. Problem najkrótszej ścieżki od jednego z wierzchołków do wszystkich innych można więc zobrazować jako problem znalezienia najkrótszej drogi pomiędzy dwoma miastami. W takim wypadku wierzchołkami grafu są skrzyżowania dróg, krawędziami – drogi, a wagi krawędzi odwzorowują długość danego odcinka drogowego. Do znalezienia najkrótszej ścieżki pomiędzy dwoma wierzchołkami zazwyczaj używane są algorytmy:
Dijkstra(G,w,s): dla każdego wierzchołka v w V[G] wykonaj d[v] := nieskończoność poprzednik[v] := niezdefiniowane d[s] := 0 Q := V dopóki Q niepuste wykonaj u := Zdejmij_Min(Q) dla każdego wierzchołka v – sąsiada u wykonaj jeżeli d[v] > d[u] + w(u, v) to d[v] := d[u] + w(u, v) poprzednik[v] := u
Drzewem rozpinającym (ang. Spanning Tree) grafu G nazywamy drzewo, które zawiera wszystkie wierzchołki grafu G, zaś zbiór krawędzi drzewa jest podzbiorem zbioru krawędzi grafu.
Konstrukcja drzewa rozpinającego polega na usuwaniu z grafu tych krawędzi które należą do cykli.
Minimalne drzewo rozpinające (ang. MST, Minimum Spanning Tree ) jest to drzewo rozpinające danego grafu o najmniejszej z możliwych wag, tj. takie, że nie istnieje dla tego grafu inne drzewo rozpinające o mniejszej sumie wag krawędzi.
Istnieją trzy deterministyczne algorytmy o złożoności liniowo-logarytmicznej znajdujące dla zadanego grafu minimalne drzewo rozpinające. Są to:
Przeszukiwanie grafu lub inaczej przechodzenie grafu to czynność polegająca na odwiedzeniu w jakiś usystematyzowany sposób wszystkich wierzchołków grafu w celu zebrania potrzebnych informacji. Często podczas przejścia grafu rozwiązujemy już jakiś problem, ale przeważnie jest to tylko wstęp do wykonania właściwego algorytmu.
Powszechnie stosuje się dwie podstawowe metody przeszukiwania grafów:
funkcja przeszukiwanie_wszerz (Start, Cel) dodaj_do_kolejki(Kolejka, Start) dopóki nie_pusta(Kolejka) Wierzchołek:= pobierz_z_kolejki(Kolejka) jeżeli Wierzchołek = Cel zwróć Wierzchołek /* i zakończ funkcję */ dla każdego Syna w Wierzchołek jeżeli nie_odwiedzony(Syn) zapamiętaj_że_odwiedzony(Syn) dodaj_do_kolejki(Kolejka, Syn)
Procedura pomocnicza 'wizytacja' (A) //Q-oznacza węzeł jeżeli węzeł A nie jest odwiedzony zaznacz węzeł A jako odwiedzony; dla każdego węzła X przyległego do A wykonaj: wizytacja(x); procedura 'przeszukiwanie zstępujące' //oznacz wszystkie węzły jako nieodwiedzone wybierz dowolny węzeł X grafu i wykonaj: wizytacja(X);
Cykl Hamiltona to taki cykl w grafie, w którym każdy wierzchołek grafu przechodzony jest tylko jeden raz (oprócz pierwszego wierzchołka). Znalezienie cyklu Hamiltona o minimalnej sumie wag krawędzi jest równoważne rozwiązaniu problemu komiwojażera. Grafy zawierające cykl Hamiltona nazywamy hamiltonowskimi.
Problem komiwojażera (TSP - ang. traveling salesman problem) jest to zagadnienie z teorii grafów, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.
Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość pomiędzy każdą parą miast.
Symetryczny problem komiwojażera polega na tym, że odległość pomiędzy miastami A i B jest zawsze taka sama. W asymetrycznym problemie komiwojażera odległość od miasta A do miasta B może być inna, niż odległość od miasta B do miasta A.
Problem ten jest NP-trudny.
W wersji decyzyjnej problemu, danymi są graf i pewna liczba n, należy odpowiedzieć czy istnieje trasa komiwojażera krótsza od n.
Tak sformułowany problem jest NP-zupełny.