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).