Resize of:

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

Nazwisko

Imię

Ocena [

Uwaga! Zero nie jest liczbą naturalną.

| 2-1 | Które z poniższych zdań byłyby prawdziwe dla każdych zagadnień III, II₂ € NP, gdyby V jć NP1 Wypełnij poniższą tabelkę, stawiając krzyżyk w odpowiednich rubrykach.

Tak Nie

	><
	X
	Y

Tak Nie

jeżeli III € V i II₂ € P, to Ilialla jeżeli III € NPT i II₂ 6 P, to Diorllj jeżeli III € NP \ P i II3 € P, to IIioIIj jeżeli III € NPC i II3 € P, to Iliallj jeżeli III € P i II₂ € NPT, to II10H3

jeżeli nj € NP \ P i II₂ € NPT, to DioDj jeżeli III 6 NPC i II3 6 NPT, to Ilialls jeżeli III € P i II3 6 NP \ P, to Iliall3 jeżeli n_t 6Np\p, n₂ ę.NP\p, ton,an₂ jeżeli II, € NPC i II3 € NP \P, to Iliall3

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

Problem Ograniczone z Dołu Kolorowanie ODK(fc, 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 0GK(fc, 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 Z,- i kolumnie Wj powinno zawierać: (1) literę A, o ile zdanie Z, jest prawdziwe dla wszystkich liczb naturalnych k, c spełniających warunek Wj; (2) literę B, o ile zdanie Z,- nie jest prawdziwe dla żadnych liczb naturalnych k, c spełniających warunek Wj] (3) literę C, w pozostałych przypadkach. Uwaga! Przyjmij, ieP NP.

	wx		w3	Wa	Ws
Z\	C	fe	C		c
zJ			7,	B	?>
Z3	c	A	c.	A	C
Za	A-	A	A	A	A
Zs	_A_	ls-	-A_		A

(Zi) ODK(fc,c) € NPC (Z₂) OGK(A:,c) € NPC (Z₃) ODK(k,c)eP (Z₄) OGK(*,c)€?>

(Z*) OGK(Jfc,c)aODK(jfc,c)

(Wj) c = 1, A: dowolne (W₂) k = I, c dowolne (W₃) c = 2, k dowolne (W«) k = 2,c dowolne (W₅) c parzyste, k parzyste

| 15-1 Niech KG(<?) będzie następująco sformułowanym zagadnieniem: dany jest graf G należący do klasy G czy x(G) < Przyjmując, że

T+    1)    G\ jest klasą grafów    planarnych;    4)    Ga jest    klasą grafów eulerowskich;

2)    Gi jest klasą grafów    niceulerowskich;    5)    0$    jest    klasą grafów stopnia A < 4;    P

T~    3)    Gs jest klasą grafów    pełnych rzędu n > 5;    6)    Gt jest    klasą grafów spójnych;    tSPC

narysuj jak wyglądałby digraf relacji a dla zagadnień KG(£i), KG(£3), KG(£j), KG(<7₄), KG(£₃), KG(&), gdyby

Strona