Kolokwium nr 2 (29.01.2009)

Zadanie 2
a) P
b) P (maksymalna klika może mieć wielkość 4 - przejrzenie wszystkich czwórek (n po 4) zajmie
nam czas ~ n^4)
c) NPC (każdy graf można pokolorować na delta+1 kolorów, więc nie dostajemy żadnej dodatkowej
informacji)
d) NPC (jw.)
e) P (tak jak w b)
f) P

Zadanie 6
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;
}