Resize of*

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

Wypełnij

2-1 | Które z poniższych zdań byłyby prawdziwe dla każdych zagadnień III, II₂ € AfT, gdyby V A HV1

poniższą tabelkę, stawiając krzyżyk w odpowiednich rubrykach.

Tak Nie

	X
V
X
X
X

jeżeli III € P i Ela € P, to Ilialla jeżeli III € MVZ i II₂ € P, to Italii . jeżeli III € J4V \ V i II₂ 6 V, to n₂alli jeżeli ni € MVC i II₂ € P, to n₂ani jeżeli Hi € V i II₂ € to Dian₂

Tak Nie

jeżeli Hi € UV \ V i n₂ € NVX, to niaH₂ jeżeli Hi € “P i H₂ € to n₂cd3i jeżeli ni € bf'PX i n₂ € to n₂crlli jeżeli ni € JfV \ V, H₂ € //”'PC, to n₂alli jeżeli n_t e JfPC i n₂ € MVC, to n₂ani

1

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

Problem Ograniczone z Dołu Kolorowanie ODK(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 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 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! Przyjmy, że V MV.

	wl	w2	w3	w<	W6
Zx	*		$	CB	3	|(Zi) ODK(k,c) 6 MV1	|(Wi) c = 1, k dowolne
Z7	A	A	A	A	A	1(Za) OGK(fc,c) € V	|(W2) k = 1, c dowolne
Z3	A	A	A	A	A	|(Z,) ODK{k,c)ę//V	l(W3) c = 2, k dowolne
Zi			$	3	3	1 (.Za) OGK(k,e)iV	H(W«) k = 2, c dowolne
Zs	c	A	C	A	c	|(Z*) ODK(k, c)aOGK(fc, c)	((W5) c nieparzyste, k nieparzyste

I 15-1

(57¥

Niech KG(£) będzie następująco sformułowanym zagadnieniem: Przyjmując, że

dany jest graf G należący do klasy G\

czy

Ga jest klasą grafów eulerowskich; N PC Gs jest klasą grafów stopnia A < 4; P Gt jest klasą grafów spójnych; N P C

T₊ 1) Q\ jest klasą grafów planarnych;

N PC 2)    {?₂ jest klasą grafów nieeulerowskich;

T„3) Ga jest klasą grafów pełnych rzędu n > 5;

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