Grafuri - test grila

Un graf neorientat are 10 muchii și este conex. Numărul maxim de noduri ale sale este:

• 8

• 9

• 10

• 11

Un arbore cu 10 noduri, numerotate de la 1 la 10, este reprezentat prin vectorul de „taţi” (6,5,7,5,9,9,6,7,0,5). Numărul nodurilor de tip “frunză” ale arborelui este:

• 4

• 5

• 6

• 7

Indicați valorile ce pot reprezenta numărul de fii ai fiecăruia dintre cele șase noduri ale unui arbore

cu rădăcină.

• 0,0,0,1,2,3

• 0,0,0,0,2,3

• 0,0,0,3,3,3

• 1,1,1,1,1,1

Se consideră graful neorientat cu 5 noduri a cărui matrice de adiacenţă are toate elementele 1, cu excepţia celor de pe diagonala principală, care sunt nule. Care este numărul minim de muchii care pot fi eliminate astfel încât graful parţial obţinut să fie format din 3 componente conexe?

• 4

• 6

• 7

• 8

Fie graful orientat G cu 5 vârfuri, numerotate cu 1,2,3,4,5, şi arcele (1,2), (1,3), (1,4), (2,3), (4,2), (4,5), (5,2), (2,4). Care dintre următoarele vârfuri au gradul extern egal cu gradul intern?

• 2 si 4

• 4 si 5

• 1 si 2

• 3 si 4

Se consideră un arbore cu rădăcină memorat cu ajutorul vectorului de ”taţi” T=(2,0,1,1,1,2). Stabiliţi care dintre nodurile arborelui sunt situate pe nivelul 3, dacă

rădăcina este situată pe nivelul 1?

• 3 4 5

• 1

• 2 6

• 1 2 6

Se consideră un graf neorientat 5 noduri şi 3 muchii. Care este numărul maxim de noduri cu grad 1 care pot exista în graf?

• 2

• 3

• 4

• 5

Un graf neorientat are 40 de noduri si 40 de muchii. Numărul numărul maxim de componente conexe ale grafului este ?

• 30

• 31

• 32

• 29

Numărul minim de noduri cu gradul 1 pentru un graf neorientat conex cu 21 noduri şi 20 muchii este:

• 1

• 2

• 3

• 11