Test

1. Fie G un graf neorientat conex cu 20 de noduri și 99 de muchii. Numărul maxim de muchii ce pot fi eliminate astfel încât graful să rămână conex este:

50 80 79 81

2. Care este numărul maxim de vârfuri izolate pe care le poate avea un graf neorientat cu 8 noduri și 12 muchii?

1 3 0 2

3. Graful neorientat G={(1,2),(1,3),(2,3),(4,5),(4,1),(2,5)} este:

hamiltonian eulerian arbore aciclic

4. Se consideră graful neorientat G={(1,2),(1,3),(2,3),(3,4),(6,5),(4,6),(4,5)}. Care este numărul cel mai mic de muchii care trebuie adăugate pentru ca graful să devină eulerian?

1 4 3 2

5. Numărul grafurilor parțiale ale unui graf neorientat cu n vârfuri și m muchii este 2^m. Afirmația este:

Adevărată Falsă

6. Care este nodul din graful neorientat G={(1,6),(2,6),(6,4),(4,3),(3,5)} ce poate fi ales ca rădăcină, astfel încât să se formeze un arbore a cărui rădăcina să aibă 3 descendenți direcți?

3 4 6 1

7. Câţi fraţi are nodul 1 din arborele cu rădăcină cu 7 noduri, numerotate de la 1 la 7, având următorul vector de tați: (5,1,5,1,0,7,5)?

1 3 2 0

8. Care este gradul maxim posibil şi care este gradul minim posibil pentru un nod dintr-un graf cu n noduri, care este arbore?

n-1 și 0 n-1 și 1 n și 0 n și 1

9. Numărul minim de muchii care pot fi eliminate astfel încât graful G={(1,2),(1,4),(2,4),(4,3),(3,1),(3,5),(5,6),(3,6)} să devină arbore este:

0 1 2 3

10. Un graf neorientat și conex are n noduri și n-1 muchii. Care este numărul minim de muchii ce trebuie adăugate astfel încât să se obțină un ciclu?

1 (n²-3n-2)/2 (n²-n)/2 0