Zadania

przygotowawcze

na egzamin

1. Czy prawdziwe są zdania:

a) każdy podzbiór zbioru niezależnego jest niezależny;

b) każdy podzbiór zbioru dominującego jest dominujący;

c) każdy podzbiór zbioru nienadmiernego jest nienadmierny.

2. Czy prawdziwe jest zdanie: Jeśli D jest minimalnym zbiorem
dominującym w G, to dla każdego u



D istnieje v



V-D taki, że

N

G

(v)



D={u}.

3. Podać przykład grafu G, dla którego



t

(G)<



c

(G).

4. Opisać rodzinę drzew T, dla których zachodzi równość



t

(T)=(n(T)-n

1

(T)+2)/2.

5. Jeśli e jest krawędzią grafu G i G oraz G-e są spójne, to:

a)



w

(G)





w

(G-e);

b)



w

(G-e)





w

(G)+1;

c)



w

(G-e)





w

(G)+2.

6. Czy prawdziwe są zdania:

a) istnieje graf G taki, że



(G)>n/3;

b) Jeśli graf G nie ma wierzchołków izolowanych oraz
diam(G) > 5, to



(Gd)=2, gdzie Gd jest dopełnieniem

grafu G.

7. Czy prawdziwe są zdania:

a) każdy zbiór dominujący jest zbiorem nienadmiernym;

b) każdy zbiór nienadmierny jest zbiorem dominującym.

8. Na czym polegają zagadnienia Nordhausa-Gadduma?

9. Zbiór PN[v,D] jest zbiorem prywatnych sąsiadów
wierzchołka v względem zbioru D, jeśli:

a) PN[v,D]= N

G

(v) – N

G

(D-{v});

b) dla każdego wierzchołka w



PN[v,D] jest N

G

(w)



D





;

c) dla każdego wierzchołka w



PN[v,D] istnieje wierzchołek

u



v taki, że u jest sąsiadem w i u



D.

10. Podać przykład grafu G, dla którego



w

(G) <



w

(G).

11. Pokazać, że różnica między liczbami



c

oraz



w

może być dowolnie duża.

12. Jeśli D jest zbiorem totalnym dominującym, to:

a) <D>

jest spójny;

b) <D>

= mK

2

;

c) dla każdego wierzchołka v ze zbioru V-D jest
|N

G

(v)



D|



1.

13. Udowodnij, że niezależny zbiór S jest maksymalny
niezależny wtedy i tylko wtedy, gdy jest niezależny
i dominujący.

14. Jeśli T jest drzewem, to:

a)



c

(T)=



con

(T);

b)



w

(T)=



c

(T);

c)



t

(T)=



w

(T).

15. Jeśli D jest zbiorem spójnym dominującym, to:

a) <D>

w

jest spójny;

b) <D> jest drzewem;

c) dla każdych dwóch wierzchołków u,v należących do D
istnieje dokładnie jedna (u-v)-ścieżka, której wierzchołki
należą do D.

16. Czy prawdziwe są stwierdzenia:

a) jeśli G jest wolny od pazura, to



(G)=ir(G);

b) dla każdego spójnego podgrafu spinającego H grafu G
mamy



c

(H)





c

(G).