Zadania 1

fflfa/z) ; T(_n)= C-sź-riC ćdOC)

/    j=M

LPr/eprowadż pełny dowód (tj. wraz'/: przynależnością do NP) tego. że problem Podziału Zbmru A={ui,-..,a_;,....y_nj jest NP-zu pełny nawet wówczas, ^tiy n jest parzyste, zaś a_; są naturalne. Wskazówka : jeśii |A| jest nieparzyste, to pomnóż jego elementy przez odpowiednia liczbę k i ostatni z tak uzyskanych elementów ka„ rozbij na uwa.

Niech PP-probiem podziału; PP'-prc-blem podziału dla parzystej liczby elementów. Aby udowodnić, że problem podziału, jeśli ]AJ jest parzyste, jest problemem NP-trudnym wykaże, że za jego p-cmocą można rozwiązać ogólny problem podziału. Załóżmy, że manty ciąg A o nieparzystej liczbie elementów. Jeśli suma v.3g ciągu jest nieparzysta, to oznacza, że zbioru nic można przepołowić. Jeśii jest parzysta mnożymy wszystkie elementy ciągu A razy dwa. W ten sposób otrzymamy ciąg. którego suma wag jest podzieina przez 4, czyli połowa sumy wag (czyli waga połowy zbioru A) jest podzieJna przez 2. Następnie jeden z otrzymanych elementów (wszystkie są parzyste) dzielimy na dwia nieparzyste. W ten sposób otrzymujemy ciąg o parzystej liczbie elementów i możemy próbować go przepołowić algorytmem ??’. Mamy gwarancję,, że obie części przepołowionego elementu znajda się w jednym podzbiorze (izn. będą niejako traktowane jako jeden), gdyż są to jedyne elementy nieparzyste, w każdymi z podzbiorów suma wag musi być parzysta. Tak więc wykazałem, że PPaP?\ Zależność PP’ctPP jest oczyw ista, tak więc PP’ jest problemem NP-tntdnym.

2. Zaprojektuj algorytm wyznaczania indeksu chromatycznego grafu, który jest 4/3 przybliżony. Udowodnij, że jego e rzeczywiście nie przekracza 4/3. Przeanalizuj szczegółowo przypadek A(G) <2.

Niech A(G) oznacza maksymałny stopień wierzchołka w* grafie G. Do skonstruowania algorytmu wykorzystamy właściwość : x(G)= A(G) lub y(G)= A(G)-j-l (wg iw. Yisinga). Tak więc zwrócenie jako yJG) wartości A(G)+ i daje nam algorytm 4/3 przybliżony dla A(G) >3. Dla pozostałych wartości musimy działać optymalnie. Można to zrobić w następujący sposób:

-    jeśli A(G)=0, to %(G)=0, bo nie ma żadnych krawędzi,

-    jeśli A(G)= l, to y(G)= 1. bo nie ma sąsiednich fcraw*ędzi,

-    jeśli A(G)=2, to y(G)=2, jeśli nie mą nieparzystych cykli lub y_(G)=3, jeśli jest.

Złożoność takiego algorytmu będzie 0(n^z).

3. Jak wiadomo problem Cykl Hamiltona jest NPC- Rozważ, czy pozostaje on NT-zu pełny, gdy A(G)<2 ? Jeśli uznasz, że tak. to naszkicuj dowód iego faktu. Jeśli uznasz, że nie, to naszkicuj algorytm wielomianowy przyjmując, że G dany jest w postaci macierzy sąsiedztw a wierzchołków.

Jeśli A(G) <2, to problem Cykl Hamiltona jest problemem łatwym. Wiedząc, że maksymalny stopień wierzchołka jes: mniejszy niż 3, możemy zauważyć, że dochodząc do danego wierzchołka grafu możemy opuścić go tylko w jeden sposób (bo dochodzą do niego maksymalnie 2 krawędzie). Teraz już nie trudno spostrzec, że aby graf był Hamiltonowsłd (czyli można byłoby "obejść'’ wszystkie wierzchołki jednym cyklem), cały graf musi być jednym wielkim cyklem, czyli nie może mieć liści i musi być spójny. Przykładowy algorytm może-wyglądać następująco : proceduro Hamilton (G;grąph;n:integcr): i.j.krawędzie.m.integer. fcegin m:=0;

for i;=ł to n-1 do begin

krawędzie :=0;

for j;=i-rl to n do ifG(i,jj=l then

begin

krawędzie :=kro wedzie-r 1; m;=rn-rl; cud;

if krawędzie<2 retum niejesi; end;

U m<n Lhen rei urn jest end;

4. W każdym z poniższych pytań założono,-że 17 jest problemem klasy NP, zaś ‘"algorytm” jest algorytmem deterministyc z nyrn.

a) Przypuśćmy, że udowodniłoś, iż złożoność dowolnego algorytmu rozwiązującego Q jest D(2^U). Co symbolicznie ogłosisz .światu ?

1>) Przypuśćmy, ze znalazłeś algoiytm rozwiązujący IJ w czasie widomianowrin. Co symbolicznie ogłosisz światu ? c) Przypuśćmy, żc H jest NPC i znalazłeś dla fi algorytm działający w czasie wielomianowym. Co symbolicznie ogłosisz światu ?