Pagina informaticii

Teste de informatică pentru liceu, articole C#, C/C++, PHP

Test grilă grafuri

1. Care din următoarele afirmații este adevărată:
a. Un ciclu eulerian trece prin toate vârfurile grafului
b. Un graf este conex dacă nu are vârfuri izolate
c. Suma gradelor tuturor vârfurilor este număr par
d. În matricea de adiacență asociată grafului, numărul valorilor de 1 este egal cu numărul muchiilor din graf

2. Un graf complet cu n vârfuri nu este întotdeauna:
a. graf cu n(n-1)/2 muchii
b. graf conex
c. graf eulerian
d. graf hamiltonian

3. Graful neorientat cu 4 noduri și matricea de adiacență
0101
1001
0000
1100
câte cicluri are?
a. 2
b. 0
c. 3
d. 1

4. Câte muchii are un graf complet cu 10 vârfuri:
a. 40
b. 45
c. 9
d. 55

5. Câte grafuri parțiale se pot obține dintr-un graf cu 5 muchii:
a. 20
b. 32
c. 10
d. 16

6. Despre un graf cu 50 de vârfuri și 48 de muchii putem spune că:
a. este eulerian
b. este arbore
c. are cel puțin un vârf izolat
4. este neconex

7. Se consideră un graf cu 8 noduri și 15 muchii. Putem spune că numărul vârfurilor izolate este:
a. cel mult 2
b. cel mult 1
c. exact 1
d. nu are vârfuri izolate

8. Fie un graf neorientat cu 18 noduri în care nodurile pot fi partiționate în 3 mulțimi disjuncte și nevide A, B, C care au 5, 6, respectiv 7 vârfuri și care au proprietatea că orice muchie din graf are o extremitate într-o mulțime și cealaltă extremitate în altă mulțime. Care este numărul maxim de muchii pe care-l poate avea acest graf?
a. 18
b. 210
c. 21
d. 107

9. Eliminând o muchie dintr-un arbore se obține:
a. cel puțin un nod izolat
b. tot un arbore
c. cel puțin un ciclu
d. un graf neconex

10. Într-un graf cu 16 noduri, două noduri i și j sunt adiacente dacă și numai dacă i mod 2 = j mod 2. Câte componente conexe are graful?
a. 1
b. 2
c. 16
d. 8

11. Într-un graf conex cu 60 de vârfuri și 120 de muchii, care este numărul maxim muchii ce pot fi eliminate astfel încât graful să rămână conex:
a. 60
b. 59
c. 1
d. 61

12. Un graf hamiltonian cu n de noduri:
a. are gradul fiecărui vârf cel puțin n div 2
b. are gradul fiecărui vârf cel mult n div 2
c. este complet
d. nu are noduri izolate

13. Într-un graf neorientat cu n noduri și p componente conexe, care este numărul maxim de muchii ce trebuie adăugate astfel încât să devină conex:
a. n-1
b. p-1
c. n
d. n-p

14. Numărul maxim de muchii al unui graf cu 20 de noduri și 5 componente conexe este:
a. 120
b. 15
c. 190
d. 25

15. Într-un graf bipartit cu 30 de vârfuri și în care gradul fiecărui vârf este 1 sau 2, numărul minim de componente conexe este:
a. 2
b. 1
c. 15
d. 14

16. În graful complet cu 6 noduri, numărul ciclurilor hamiltoniene distincte (două cicluri sunt distincte dacă au cel puțin o muchie diferită) este:
a. 6
b. 5
c. 720
d. 120

Răspunsuri

1. c
2. c
3. d
4. b
5. b
6. d
7. a
8. d
9. d
10 b
11. d
12. d
13. b
14. a
15. b
16. d

Despre autor
Author

Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică

Scrie un comentariu
Nume:

Comentariu:

15 + 10 =