Kolokwium nr 2 (29.01.2009)

Zadanie 2

Zweryfikuj czy problem największej kliki w grafie pozostaje NP-trudny, czy staje się wielomianowy w przypadku, gdy ograniczymy się do danych wejściowych, w których:

a) graf jest podany wraz z poprawnym pokolorowaniem wierzchołkowym używającym 2 kolorów: P

b) ...4 kolorów: P (maksymalna klika może mieć wielkość 4 - przejrzenie wszystkich czwórek (n po 4) zajmie nam czas ~ n^4)

c) ...delta+1 kolorów: NPC (każdy graf można pokolorować na delta+1 kolorów, więc nie dostajemy żadnej dodatkowej informacji)
d) n kolorów: NPC (jw.)

e) graf wejściowy jest kubiczny (tzn. 3-regularny): P (tak jak w b)

f) graf wejściowy ma indeks chromatyczny <= 2: P

Zadanie 3

Mamy 5 problemów, między którymi istnieje relacja alfa jak na rysunk. Pominięto jedynie pętle. Do każdego z nich przypisz jedną z 4 klas, do której należy: P, NPI, NPC, NPT\NP

pamiętam że na obu dolnych krawędziach napisałam NPC, na prawym P, na lewym NPI i na samej górze NPT/NP...

Zadanie 4

Niech A będzie algorytmem krawędziowego kolorowania grafów spójnych, który wykorzystuje dokładnie min{2delta, m} kolory. Podaj przykład grafu o 6 wierzchołkach, który zostanie pokolorowany optymalnie przez algorytm A. Które z poniższych stwierdzeń są prawdziwe? Każdą odpowiedź uzasadnij.

a) A jest 2-przybliżony

b) A jest 2-absolutnie przybliżony
c) A jest delta-absolutnie przybliżony
d) A jest 3/2-przybliżony

e) nie istnieje stała keR+ taka że A jest k-absolutnie przybliżony

I zaznaczyłem a) d), bo jakoś tak wyszło z tego co nabazgrałem w brudnopisie. Jakoś to udowodniłem, ale to raczej była taka se paplanina. (Nie wiem czy to są dobre odpowiedzi, ale tak mi się wydaje).

Zadanie 5.

Udowodnij, że jeżeli P!=NP to nie stnieje wielomianowy algorytm 1-absolutnie przybliżony dla problemu minimalnego pokrycia wierzchołkowego grafu.

Napisałem coś koło tego, że jakby skopiować graf dla którego algorytm pomylił się o 1 i wywołać go dla wszystkich n kopii naraz (w sensie że będą stanowiły składowe spójności większego grafu) to algorytm pomyli się o n.

Zadanie 6

Dany jest graf G zapisany w postaci macierzy sąsiedztwa A(G) oraz procedura o nazwie CliqueOdd(Gn,k), która zwraca true gdy w grafie Gn mającym wszystkie wierzchołki nieparzystego stopnia istnieje klika rozmiaru k, bądź false, gdy takiej kliki nie ma. Wykorzystując tę procedurę napisz program obliczający rozmiar największej kliki w grafie G, tzn napisz podprogram przekształcający A(G) w A(Gn), a następnie podprogram znajdujący rozmiar największej kliki w Gn.

najpierw sprawdzałem po kolei dla każdego wierzchołka czy był parzystego stopnia, jeśli nie był to super, jeśli był to dorabiałem mu jeden wierzchołek bodajże ze wskaźnikiem na siebie żeby był nieparzystego stopnia bo mam funkcje która dla takich działa.

otrzymywałem zmodyfikowany graf "Gn":

Kod:

function funkcja(Graf):integer{

// gdzie n to ilosc wierzcholkow

while( !CliqueInnOdd(Grag, n){

if ( n == 2) return 0;

n=n-1;

}

return n;

}