Zadania

49. Klika a Pokrycie wierzchołkowe

Niccii G=(V.E) i k oznacza istnienie kliki. Załóżmy, że [V;=n. Zbuduję "raf G' taki. że G’ ma pokrycie wierze ho i ko we o rozmiarze co najmniej n-k jeżeli G ma klikę o rozmiarze co najmniej k. Graf G=G aa przykład jest grafem komplementarnym do G. Pokażę, że G ma klikę o rozmiarze co najmniej koGm3 pokrycie wierzchołkowe o rozmiarze co najmniej n-k. Niech K będzie dowolną kliką w G. Ponieważ nie ma krawędzi w G połączonych z wierzchołkami w K pozostałe n-jKj wierzchołków w G musi pokrywać wszystkie wierzchołki w G. Podobnie, jeżeli Sjest pokryciem wierzchołkowym G, wtedy V-S musi tworzyć pełny podgraf w G ponieważ w innym przypadku pewne krawędzie byłyby nie pokryte

50. Klika a Zbiór Niezależny

Dany jest graf G=(V,E), buduję graf komplementarny do grafu G, oznaczam go G^I=(V,E). Łatwo zauważyć, że K jest kliką w* G <=> K jest zbiorem niezależnych wierzchołków w G.

51. Jeżeli Ii! a n₂ i IK e P, to n_x jest w P.

Niech p będzie wielomianowym ograniczeniem na algorytm II;. Niech X będzie daną dla n_t o rozmiarze n. Wiech/ rozmiar T(X) jest przynajmniej p(n), ponieważ w najgorszymi przepadku program T razy pisze symbol za każdym krokiem. Kiedy algorytm na IK otrzymuje T(x), wykonuje co najmniej q(p(n)) kroków. Tak więc całkowita liczba pracy potrzebnej do . transformacji X do T(X), a następnie użycia algorytmu Elz, celem uzyskania prawidłowej odpowiedzi na III jest p(n)żq(p(n)), co jest wielomianową funkcją n.

52. Hanoi

procedurę Hanoi(A^B,C:Regąi:int);    0(2^C) - wykładnicza

begin

if n=l then move(A,C) else begin

Hanoi(A,C,B,n-I);

move(A,C):

Hanoi(B.A,C.n-l);

end;

end;

53. Dane jest pudełko, Do tego pudełka wkładane są kule wg. następującego algorytmu: Najpierw wkładana jest największa pasująca kula a kolejne kule są wkładane w przypadkowej kolejności. Udowodnij, że algorytm ten jest 2-względnie przybliżony.

Załóżmy, że pudełko ma pojemność 2P. Rozpatrzmy dwie sytuacje:

a)    rozmiar największej pasującej kuli jest>JP.

Tutaj dowód jest natychmistowy, ponieważ ta jedna kula już zapełnia pudełko w przeszło połowie, co daje e<2 niezależnie od tego, jakie są inne kule.

b)    rozmiar największej pasującej kuli jest<P.

Z założenia wynika ważna rzecz: WSZYSTKIE kule są mniejsze niż P. Jeśli mamy kule większe, to są one większe niż 2?, nie mieszczą się w pudełku, więc możemy ich w ogóle nie brać pod uwagę. Z tego znowu wynika, że jeśli w eźmiemy następną (po największej pasującej) kale (dowolną) to zmieści się ona w pudelku. 1 dopóki nie zapełnimy pudełka do przeszło połowy, na pewno każda brana kula się zmieści. Tak więc, jeśli iyLko starczy nam kuł - na pewno zapełnimy pudełko w przeszło p-olowie, co kończy cc wód. A co. jeśi; zabraknie nam ku! ? Oznacza to. że zapełniliśmy pudełko w sposób optymalny dla danego zbioru kul i ewl (ponieważ włożyliśmy wszystkie kule. jakie w ogóle dało się włożyć, czyli wszystkie kule mniejsze niż 2P).    _    _~ ~    ' '

54. Dany jest graf skierowany o n wierzchołkach zapisany w postaci macierzy przejść A, z. takim bajerem: jest to macierz boolowska, tj. zamiast jedynek i zer mamy wartości TRUE i FA.LSE. Dany jest też algorytm badający, czy istnieje droga z. wierzchołka fromW do wierzchołka tooW: function CzyDroga(A,wl,w2,.\) begin