Zadania

Formułka: Ponieważ udowodniliśmy, że KLIKA a PNP. stąd, wiedząc, że problem KLIKA jest trudny, wynika, że problem PNP jest także trudny.

Na koniec procedurka (problem decyzyjny - czy istnieje klika): proceduro KLIKA {graf G_T rozmiar k)

f

\

1.    obciąż wszystkie krawędzie w G jedynkami (wbrew pozorom złożoność jest 0(1), a nie 0(n')_; ponieważ w praktyce nie musimy przechodzić całego grafu, po prostu zapamiętujemy, że wszystkie krawędzie mają wagę 1 i z faktu tego korzystamy w procedurze NAjCEĘZSZY_PODGRAF za każdym razem, gdy potrzebujemy informację o wadze danej krawędzi)

2.    wagasum=NAJCIEŻSZY_PODGRAF(G,k);

3.    if (waga5iirn==k*(k-l)/2) return TRUE;

else return FALSE

57. Udowodnij, że problem znalezienia w grafie ścieżki prostej o długości k (ezyli składającej się z k krawędzi) jest problemem NP-zupełnym.

1.    ŚCffiŻKAJPROSTAe NP

Dowód: Każde świadectwo możemy zweryfikować w czasie wielomianowym, (definicje gdzie indziej). Tzn. jeśli mamy podany graf G i jakiś zbiór k-krawędzi tego grafu, to w czasie wielomianowym możemy spraw^:dzić, czy jest to ścieżka prosta w tym grafie. Nawet jeśli krawędzie są podane w dowolnej kolejności, to na pewno w czasie OGr) jesteśmy to w stanie stwierdzić. Algorytmu nie przytaczam, zresztą nie jest on najistotniejszą czścią zadania (na egzaminie pominąłem i wszystko było OK), zresztą jest prosty.

2.    GRaFJPÓŁHAMIŁTONOWSKI (problem trudny z założenia) a ŚCIEŻKAJPROSTA Mamy graf Gon wierzchołkach.

Twierdzenie: Graf G jest pólhamiltonowsld e=> W grafie G istnieje ścieżka prosta długości n-1.

Dowód w prawo: Wynika bezpośrednio z definicji grafu pólhamiltonowsłdego - posiada on ścieżkę prosta przechodzącą przez wszystkie n wierzchołków, a wiec mającą długość n-1.

Dowód w lewo: To także wynika bezpośrednio z definicji. Ścieżka prosta to taka ścieżka, w której wierzchołki nie powtarzają się. Skoro ma ona długość n-1 to znaczy, że przechodzi przez n wierzchołków, a więc jest ścieżką Hamiltona w grafie G.

Jak widać więc, mając algorytm rozwiązywania problemu ścieżki prostej bez trudu możemy rozwiązać każdy problem grafu połhamiltonowskiegc.

Formułka. Skoro udowodniliśmy, że problem ścieżki prostej jest NP, oraz że jest problemem trudnym (ponieważ jest z nim w relacji alfa inny problem trudny) wnioskujemy, że problem ten jest NP-zupełny.

3$. Zaprojektuj algorytm poszukiwania w grafie obciążonym najkrótszego cyklu. Zastosuj algorytm Dijkstry. Oszacuj złożoność przedstawionego aigory^mu.

Przykladowy algorytm:

Dla każdej krawędzi (wl,w2) w grafie G:    0(n²)

{

1.    Usuń tę krawędź z grafu.

2.    Znajdź najkrótszą drogę między' wierzchołkami \vł a w2 (algorytm Dijkstry')    0(n~)

Jeśli taka droga nie istnieje to idź do punktu 5.

3.    Do orrzymanej długości drogi dodaj wagę usuniętej krawędzi.

4.    Tak otrzymana wagę cyklu porównaj z dotąd otrzymanym najlepszym wynikiem i ewentualnie skoryguj go.

5.    Dodaj krawędź spoiwo te m do grafu.

Po wykonaniu całego algorytmu najlepszy uzyskany wynik będzie określa! najkrótszy' cykl w całym grafie.

Złożoność całego algorytmu: 0(n")* 0(n^:)= O(rf)

Myślę, że odpowiednio manipulując algorytmem Dijkstry; możnaby uzyskać algorytm o złożoności 0(n³), ale zostawiam to na razie.

59. Definicje

P - klasa problemów; które są ograniczone wiclomianowo