1109144848

Zadanie 150. Jaka jest złożoność następującego problemu: Dany graf nieskierowany. Czy istnieje taki sposób pokolorowania jego krawędzi dwoma kolorami, czerwonym i niebieskim, aby każda krawędź była pokolorowana i aby nie pojawił się żaden niebieski cykl nieparzystej długości ani żaden czerwony cykl nieparzystej długości?

W Pewnej (Wschodniej) Krainie odbyły się wybory, w wyniku których do parlamentu weszła pewna liczba partii. Żadna z nich nie uzyskała większości, konieczne stało się zatem wyłonienie koalicji rządowej dysponującej więcej niż połową głosów. Każda z partii złożyła w związku z tym oświadczenie o następującej formie: wejdziemy do koalicji wtedy i tylko wtedy gdy otrzymamy następujące stanowiska: lista stanowisk. Listy stanowisk żądanych przez partie przecinają się czasem niepusto, a partie w swych żądaniach są nieugięte.

Oznaczmy przez KO AL problem istnienia większościowej koalicji, przy której można zaspokoić oczekiwania tworzących ją partii. Dane stanowi tu lista partii, wraz z ilością mandatów jakimi każda partia rozporządza i listą stanowisk jakich się domaga. Przez KOALj oznaczmy wariant problemu KOAL, w którym każda partia może żądać co najwyżej i stanowisk, a każdego stanowiska żąda co najwyżej j partii (brak któregość z indeksów oznacza, że nie ograniczamy tego parametru).

Zadanie 151. Jaka jest złożoność problemu KOAL2?

Wskazówka: Wolno skorzystać z NP-zupelności problemu istnienia, w grafie nieskierowa-nym o n wierzchołkach, zbioru wierzchołków niezależnych o mocy n/4-

Zadanie 152. Jaka jest złożoność problemu KOAL^l Zadanie 153. Jaka jest złożoność problemu KOAL^l

Komentarz: Nie potrafiłem niestety rozstrzygnąć jaka jest złożoność problemu KOAL². Dlatego pomyślałem, że może lepiej będzie, jeśli nie umieszczę tu takiego zadania.

Zadanie 154. Jaka jest złożoność problemu 3-kolorowania grafów, jeśli ograniczymy się do grafów o stopniu wierzchołków równym co najwyżej 4?

Zadanie 155. Rozważmy następujący Problem Trójek Klasowych (PTK).

Rodzice uczniów każdej klasy w szkole wybierają spośród siebie (do różnych niezmiernie ważnych zadań) trójkę - zwaną trójką klasową. Ponieważ można być rodzicem więcej niż jednego dziecka w szkole, można być członkiem więcej niż jednej takiej trójki.

Spośród członków tych trójek dyrektor szkoły chce powołać szkolny komitet rodzicielski, do którego należy dokładnie jeden członek każdej trójki klasowej. PTK jest problemem rozstrzygnięcia czy, dla danej listy trójek klasowych, powołanie takiego komitetu jest możliwe. Udowodnij, konstruując odpowiednią redukcję, że 3COL<pPTK.

Zadanie 156. Jaka będzie złożoność problemu z poprzedniego zadania, jeśli każde wystąpienie słowa trójka zamienimy w nim słowem dwójka?

Zadanie 157. Przez liczbę chromatyczną grafu nieskierowanego G = (V,E) rozumiemy najmniejszą liczbę naturalną n dla której istnieje funkcja l : V —> (1,2,... n} taka, że zachodzi formuła 'iz, y € V E(x,y) =S> l(x) l(y). Liczbę chromatyczną grafu G oznaczamy przez X(G)

Udowodnij, że jeżeli istnieje wielomianowy algorytm który, dla danego grafu G, zwróci zawsze jedną z liczb (x(G),x(G) + 1}, to PTIME=NP

18