4 termin - 15.02.2010

1. Udowodnij, że problem KLIKI jest NP-zupełny nawet wówczas, gdy graf G jest nieeulerowski.

2. Oszacuj dokładnie (w sensie θ) funkcję A(n), jej czas działania T(n) oraz maksymalną głębokość drzewa wykonań rekurencyjnych P(n). Dziedziną funkcji jest zbiór liczb naturalnych. Odpowiedź uzasadnij.

function A(n:integer):integer;

var i,j,k,pOM: integer;

begin

pom:=0;

if n≤100 then for i:=1 to n² do for j:=1 to n² do for k:=1 to n² do pom:= i+j+k;

else pom:=A
+A
+n*n;

return pom;

end;

A(n)=…. T(n)=…. P(n)=….

3. Jak wiadomo rozstrzygniecie, czy dany graf jest 3-barwny jest NP-trudne. Na tej podstawie wykaż, że jeśli P≠NP to nie może istnieć całkowicie wielomianowy schemat aproksymacyjny dla problemu kolorowania wierzchołków grafu przy użyciu jak najmniejszej liczby barw.

4. Graf planarny jest maksymalny, gdy dodanie jakiejkolwiek krawędzi łączącej niesąsiednie wierzchołki psuje jego planarność. Maksymalny graf planarny (MPG) jest 3-barwny jedynie wtedy, gdy jest eulerowski. Przyjmując, że MPG dany jest w postaci macierzy sąsiedztwa wierzchołków, napisz algorytm dal jego liczby chromatycznej i oszacuj złożoność przy użyciu symbolu θ.

5. Rozważ problem o nazwie WSPÓLNY PODGRAF, który zdefiniowany jest następująco: Dane: 3 grafy A, B, C. Pytanie: Czy C jest podgrafem A i B. Pokaż, że WSPÓLNY PODGRAF
NPC.

6. Problem nieograniczone drzewo spinające, w skrócie NDS, zdefiniowany jest następująco:

Dany jest graf spójny G i liczba naturalna p; czy G zawiera drzewo spinające T, takie że ∆(T)≥p? Pokaż, że NDS
P.

7. Przypuśćmy, że algorytm A ma złożoność pesymistyczną f(n), zaś algorytm B ma złożoność pesymistyczną g(n). Na każde z poniższych pytań odpowiedź TAK, NIE lub NIE WIADOMO, a odpowiedź uzasadnij.

1. Czy w najgorszym przypadku danych A jest asymptotycznie szybsze od B, jeśli g(n)=Ω(f(n)log n)?

2. Czy w najgorszym przypadku danych A jest asymptotycznie szybsze od B, jeśli g(n)=0(f(n)log n)?

3. Czy w najgorszym przypadku danych A jest asymptotycznie szybsze od B, jeśli g(n)=θ(f(n)log n)?

4. Czy w najgorszym przypadku danych B jest asymptotycznie szybsze od A, jeśli g(n)=Ω(f(n)log n)?

5. Czy w najgorszym przypadku danych B jest asymptotycznie szybsze od A, jeśli g(n)=0(f(n)log n)?

6. Czy w najgorszym przypadku danych B jest asymptotycznie szybsze od A, jeśli g(n)=θ(f(n)log n)?

---