Zadania

;T'v

if (A[iJjoAjJ.i]) thcn return (falsc); end;

rerum (lnie);

cud;

T(n)=T(n-l)4-2T(n-2)

41. Podaj jak najwięcej szczególnych przypadków problemu OKG, dla którego staje się on wielomianów o rozwiązywalny.

a)    n=k-graf k dzielny,

b)    graf jest drzewem,

c)    graf jest cyklem,

d)    graf jest kołem

42. Podział a Suma Podzbioru

Problem Sumy Podzbioru jest zdefiniowany w następujący sposób:

dane : skończony podzbiór A, rozmiar S(a)eNT, dla każdego as A i dodatnia liczba całkowita k. pytanie : czy istnieje podzbiór A’ęgA taki, że suma rozmiarów elementów w A' jest dokładnie równa k ?

Mamy dany problem podziału. Niech S(a₁)-K_>S(ą₁p⁼2b. Juko limit k dla problemu sumy podzbioru przyjmijmy o. Jeżeli istnieje podział A, wtedy odpowiedź dla problemu sumy podzbioru brzmi - "tak”. Jeżeli odpowiedź dla problemu sumy podzbioru brzmi "tak”, to istnieje podzbiór A’cA taki, żc X(asA’> S(a) = I(asA) S(a) procedurę pod2ia](A[l..nj):boolean; begin suma.-O;

for i:=l to n do suma:=suma-^A[i]; j:=suma/2;

if Suma Podzbiom(A(] j) = true then return (true)

elsc retum (false);

end;

43. Suma Podzbioru a Podział trzeba dodać elementy (sum,sum-t) procedurę SumaPodzbiora(A(I,...,n],p:integer):boolean; begin suma:=0; for i;=l to n do suma:=suma+A[i]; v:=2p-suma; for i;=l to n+1 do ifion+l then B[i]:=A[i] eise B[i]:=y;

if Podział(S}=irue then return (trać)

elss retum (false);

end;

44. Przypuśćmy że mamy n programów' i 2 dyski. Niech Li będzie ilością miejsca potrzebną do zachowania i-tego programu i L pojemnością każdego dysku. Pokaż, że określenie mai liczby tych programów, które mogą być zapisane na 2 dyskach jest problemem NPH. n -- programów. L; - rozmiar potrzebny na i-ty program, 2 dyski.

L - pojemność dysku PARTITtON a PROBLEM

P(P;mition) - zbiór elementów z wagami, czy możemy go podzielić na 2 rów ne części

9fl