Resize of

Kolokwium ze Złożoności Obliczeniowej Algorytmów

Nazwisko

Imię

yc

1 czerwca 2002

Ocena [

Uwaga! Zero nie jest liczbą naturalną.

Wpell

2-1 | Które z poniższych zdań byłyby prawdziwe dla każdycli zagadnień 111, Ilj 6 AfP, gdyby P / NP1 poniższą tabelkę, stawiając krzyżyk w odpowiednich rubrykach.

Tak Nie

Tak Nie

	><
X
X
X

jeżeli n_t € V i n₂ G P, to Iliallj jeżeli Ilj G NPX i Ilj G P, to Iljarij jeżeli III G AfP \ P i Ilj G P, to fljall; jeżeli III € A(PC i Ilj G P, to n₃ani jeżeli ni G P i n₂ 6 NPX, to n,cdlj

jeżeli n_s G NP\P i II₂ G NVX, to Iliallj jeżeli ni g v i nj g npc, to iiiaii₃ jeżeli ni G A^rPX i Hj G NPC, to IIian₃ jeżeli ni G NP \ P, II₃ G A(PC, to iiiaii₃ jeżeli Hi G NPC i II₃ G A(PC, to IIian₃

| 2-1 | Niech ODK(A:,e) i OGK(Jt,c) będą następująco sformułowanymi zagadnieniami:

Problem Ograniczone z Dołu Kolorowanie 0DK(Jfc, c): dany jest graf G; czy G można pokolorować co najwyżej k kolorami w taki sposób, że każdy wykorzystany kolor został przydzielony co najmniej c wierzchołkom? Problem Ograniczone z Góry Kolorowanie OGK(k, c): dany jest graf G; czy G można pokolorować co najwyżej k kolorami w taki sposób, że każdy wykorzystany kolor został przydzielony co najwyżej c wierzchołkom?

Wypełnij poniższą tabelkę, stawiając w każdym polu literę A, B lub C. Pole znajdujące się w wierszu źf, i kolumnie Wj powinno zawierać: (1) literę A, o ile zdanie Zi jest prawdziwe dla wszystkich liczb naturalnych k, c spełniających warunek Wj; (2) literę B, o ile zdanie Zi nie jest prawdziwe dla żadnych liczb naturalnych Jfc, c spełniających warunek W fi (3) literę C, w pozostałych przypadkach. Uwaga! Przyjmij, ieP £ NP.

	Wx	w7	w3	Wa	w*
	<Ł	A	C	h	c
Zi	?>	fi		'fi	'fi
Zi	c	fi	c.	fi	c
Za	A	A	A	A	A
Zi		fi	c	^A6	c

(Zi) ODK(Jt.c) G NPC (Z₇) OGK(k.c) € NPC (Z₃) ODK(*,c)€P (Z«) OGK(k,c) G P (Zi) ODK(Jfc, e)aOGK(fc, c)

(Wi) c = 3, * dowolne (Wj) Jt « 3, c dowolne (Wj) c = 4, k dowolne (W«) k = 4, c dowolne (Wj) c nieparzyste, k nieparzyste

|    | 1S-1 Niech KG((?) będzie następująco sformułowanym zagadnieniem: dany jest graf G należący do klasy G\

czy x(G) < 47 Przyjmując, że

7+ 1) Gi jest klasą grafów planarnych;    4) G* jest klasą grafów eulerowskich;

HP C 2) Gj jest klasą grafów nieeulerowskich;    5) Gi jest klasą grafów stopnia A < 4; V

T- 3) Gi jest klasą grafów pełnych rzędu n > 5; 6) Gt jest klasą grafów spójnych; t\J P£

narysuj jak wyglądałby digraf relacji a dla zagadnień KG(ffi), KG(£j), KG(&), KG (Ga), KG(<?j), KG ((✓«), gdyby

Strusia ł