Zadania

32. Wiadomo, że problem odpowiedzi na pytanie, czy y(G)<3 jest NP-zupclny nawet wówczas, gdy jest planarny.

Przedyskutu j złożoność obliczeniową następujących problemów zakładając najlepszą możliwą strukturę danych i

w iedząc, że G jest planarny.

a)    -/.(G)<1, e) '/(G) >1,

b)    x(G)<2, O x(G) >2,

c)    y(G)<3, g) xfG) >3.

<i) ;:(G)<4,

a)    C(n) - trzeba sprawdzić, czy' graf nie ma krawędzi (lub sąsiedztwa), czyli zbadać stopień każdego wierzchołka, możemy założyć, że graf mamy w postaci list sąsiedzrwa. Wystarczy', że jeden z wierzchołków będzie miał jednego sąsiada a wynik jest negatywny (nie musimy sprawdzać wszystkich krawędzi). Stąd złożoność jest 0(n) a nie O(iT).

b)    wielomianowa C(n²) - czy graf dwudzielny, można to sprawdzić kolorując graf odpowiednim algorytmem (ale nie zachłannie !), np. przechodząc z wierzchołka do wierzchołka po krawędzi. Jeśli graf nie jest spójny to do każdej składowej spójności przechodzimy dopiero wtedy, gdy całą bieżącą już pokolorowaliśmy (inaczej mówiąc sprawdziliśmy już wszystkie krawędzie - przejścia). Jeżeli jest dwudzielny da się pokolorować,

c)    jest NP,

d)    0(1)- odpowiedź jest natychmiastowa - TAK (dla grafów planarnych)

e)    0(1) - TAK (chyba oczywiste ?)

f)    0(n) -jak przypadek a)    [ (?£2) o -(x<l), xsC]

g) 0(n²) - jak przypadek b)    [ (x23) <=> -,(x<2), xeC]

33. Jak wiadomo, graf jest pólhamiltoDowski, jeżeli zawiera drogę przechodzącą przez każdy wierzchołek dokładnie raz. Odpowiedź na pytanie : Czy dany graf G jest pólhamiltonowski - jest problemem. Korzystając z tego faktu naszkicuj dowód tego, że Problem Komiwojażera jest NP-tmdny.

Cykl Hamiltona - gdy istnieje w grafie cykl, który przechodzi przez wszystkie wierzchołki dokładnie raz. Komiwojażer -mamy graf obciążony, każda krawędź ma określoną wagę, należy obejść wszystkie wierzchołki tak, aby suma wag była najmniejsza. NPC - decyzyjny czy istnieje w grafie droga ? Dopełniamy graf, który dodajemy na wejściu G, krawędzie dorysowane maja wagę 2, a te które były 1, K - ilość krawędzi przzcd dopełnieniem. Gdy obejdziemy krawędzie, to suma wag <X to oznacza, że szliśmy po cyklu Hamiltona (każdej krawędzi nadano -wagę =1 => suma = K).

Graf Hamiltonowski cc Komiwojażer Procedurę grafHani(G:graph):bcoIean;

Be gin

h:-G; (gdzie jest krawędź=l, nie ma krsw*ędzi=2) if k(h)=n-H then success else failure;    (pólhamiltonowski)

if k(G)=n then succes else false;    (hamiltonowski)

ena;

34. Las G (zbiór drzew) zapisano w postaci macierzy sąsiedzrwa wierzchołków. Napisz program znajdujący liczbę drzew w lesie i oszacuj jego złożoność obliczeniową, liczba drzew' = n~m

procedurę ildizew(n:integer,M:matrix)ńnteger, begin

for i:=l to n-1 do forj:=i-rl to n do Hcznik:=licznik+M[i,j]; retum(n-lic2nik/2); end;    ^    ^

35. Oszacuj złożoność obliczeniową funkcji path działającej na grafie n-wier/cholkowym G=(V(G),£(G)), jeśli edge(i,j)^{ true, gdy i=j lub {i,j}sE(G) “ false, w przeciwnym przypadku function path(s.t,n:iuteger):boolean; begin

if n-1 then return (edge(s,t)); for i:-l to n do

if puih(s,i,r) div 2) and path(i,r,n div 2) tben

rcturą (true);