Zad1.

Nowaqq way:

K – problem kliki dla dowolnego grafu – wiadomo, że NPC,

KN – problem kliki dla grafu nieeulerowskiego.

K alfa KN: do Grafu G z problemu K dodajemy 1 wierzchołek łącząc go z wszystkimi wierzchołkami w G, oraz 2 wierzchołki, które łączymy krawędzią z tym wierzchołkiem dodanym wcześniej – mamy w ten sposób graf nieeulerowski. Jeśli w problemie K szukamy kliki o rozmiarze k, to w problemie KN będziemy szukać kliki o rozmiarze k' = k+1. Widać, że redukcja jest wielomianowa, i zachowuje problem również gdy max Klika w G wynosiłaby 1 (co nie działałoby gdybyśmy chcieli dodać tylko jeden wierzołek i połączyć go krawędzią z G jak w przypadku dowodu dla niehamiltonowskich).

Wg Giaro może być to redukcja z dowolnego NPC z szukaniem podgrafu, czyli np. ścieżka hamiltona, cykl hamiltona. Wszystkie rozwiązania byłyby poprawne.

Zad.2

Te 3 pętle w zasanie nas nie interesują, bo wykonają się dla ograniczonego n, co nie ma wpływu na ogólne rozwiązanie – przyjmujemy to za operację w czasie stałym O(1).

A(n) = 2A(n/3) + n². To, że jest tam sufit i podłoga „możemy pieprzyć” - słowa Giaro. Podane rozwiązanie rekurencyjne rozwiązujemy standardową metodą. To chyba każdy umie...

T(n) = 2T(n/3) + 1. Rozwiązujemy jak zawsze.

P(n) = Θ(log(n)). Dokładniej coś w stylu log₃(n/100) – można olać jeśli ma być w sensie Theta.

Zad.3

Stosunek rozwiązania naszego algo do algo optymalnego jest równy 1 + epsilon. Epsilon możemy wybrać dowolnie, może być więc dowolnie mały, ale od naszego wyboru zależy złożoność naszego algorytmu. Jeśli dla dowolnie małego epsilon nasz algorytm pozostanie wielomianowy, to mamy całkowicie wielomianowy schemat aproksymacyjny. - Tak to zrozumiałem z tłumaczenia Giaro.

To tytułem wstępu, teraz rozwiązanie. Weźmy za nasz epsilon liczbę 0.33 – czyli nasz algorytm musiałby rozwiązywać wielomianowo problem kolorowania z przybliżeniem względnym 1.33 (z wzoru powyżej). A to, że nie istnieje tak przybliżony algorytm dla tego problemu było robione u każdego ćwiczeniowca na zajęciach. Gdyby istniał to 3*1.33 < 4, więc musi być 3 i mielibyśmy wielomianowe rozwiązanie problemu który jest NPC. That's all.

Zad.4

Tu generalnie była tylko rozkminka, Giaro nie napisał żadnego algo, ale zastanawiał się, czy to, że jest to Maksymalny graf planarny nie ogranicza nam przypadku dwudzielności grafu do kilku konkretnych przypadków (pojedyncza krawędź, cykle parzyste) – ostatecznie nie wymyśliliśmy nic mądrego, ale generalnie algo polega na tym:

jeśli n=1 return 1;

jeśli dwudzielny return 2; //nie wiadomo czy aby na pewno trzeba to robić

// może wystarczy sprawdzenie kilku warunków

jeśli wszystkie stopnie wierzchołków są przyste return 3;

else return 4.

czas n² , złożoność liniowa względem rozmiaru macierzy nxn.

Zad.5

Z Giaro rozmawiałem tylko o moim rozwiązaniu – czyli redukcja z kliki:

A=B=G gdzie G to ten graf z problemu kliki.

C=K_k – klika rozmiaru k – tego szukanego w problemie Kliki.

Wielomianowość widać, zachowanie problemu mam nadzieję też. Wg Giaro tak jest ok.

Zad.6

Tutaj tak jak było pisane wcześniej – szukamy wierzchołka o stopniu co najmniej p – n². Potem budujemy drzewo zaczynając od znalezionego wierzchołka wraz z wszystkimi jego krawędziami incydentnymi – to też jest wielomianowe. Jeśli nie znajdziemy wierzchołka stopnia co najmniej p, to szukanego drzewka nie ma.

Zad.7

TAK, NIE WIADOMO, TAK, NIE, NIE WIADOMO, NIE. Tłumaczenie już gdzieś było.

Wszystkie rozwiązania zrobione lub zweryfikowane by Giaro.