TEST-GRAFURI-CLS-XIA

Se consideră un graf neorientat cu 50 noduri şi 32 muchii. Care este numărul maxim de vârfuri cu gradul 0 pe care le poate avea graful?

• 45

• 40

• 41

• 50

Se consideră un graf neorientat cu 5 noduri, etichetate cu câte o literă distinctă din

mulţimea {a, b, c, d, e}, în care orice nod etichetat cu o vocală este adiacent cu toate

nodurile etichetate cu consoane şi numai cu acestea, iar orice nod etichetat cu o consoană

este adiacent numai cu nodurile etichetate cu vocale. Câte muchii are acest graf?

• 12

• 6

• 4

• 3

Matricea de adiacenţă a unui graf neorientat G are numărul valorilor de 1 egal cu jumătate

din numărul valorilor de 0. Care dintre numerele de mai jos poate fi numărul de noduri ale grafului G?

• 12

• 14

• 11

• 13

Care este numărul maxim de noduri de grad 3 într-un graf neorientat cu 5 noduri?

• 4

• 5

• 3

• 2

Se consideră graful neorientat cu 7 noduri, numerotate de la 1 la 7, şi muchiile[1,3],[2,3], [3,4], [3,5], [5,4], [1,2], [2,5], [2,4], [6,7], [3,6]. Care dintre următoarele succesiuni de noduri reprezintă un lanţ care trece o singură dată prin toate

nodurile grafului?

• (1 2 3 4 5 6 7)

• (4, 5, 3, 6, 7)

• (7, 6, 3, 5, 4, 2, 1)

• (1, 3, 5, 4, 2, 3, 6)

Se consideră graful neorientat cu 6 noduri, definit cu ajutorul listelor de adiacenţă alăturate. Care dintre mulţimile următoare de noduri are toate elementele extremităţi ale unor lanţuri elementare de lungime 2 cu cealaltă extremitate în nodul 5?

1:4,5,6

2:5

3:4

4:1,3

5:1,2,6

6:1,5

• {1,4,6}

• {2}

• {3}

• {2,6}

Graful neorientat cu 60 de noduri, numerotate de la 1 la 60, are numai muchiile: [1,60],[60,20], [2,30] şi [4,30]. Numărul componentelor conexe ale grafului este egal cu:

• 3

• 56

• 54

• 0

Se consideră un graf neorientat cu 7 noduri, numerotate de la 1 la 7 şi muchiile [1,5],[2,3], [2,4], [2,5], [3,4], [4,5], [4,7], [5,6], [5,7].Câte cicluri elementare distincte există în graf?

• 4

• 5

• 6

• 3

Se consideră un graf neorientat cu 7 noduri, numerotate de la 1 la 7 şi muchiile [1,5],[2,3], [2,4], [2,5], [3,4], [4,5], [4,7], [5,6], [5,7].Care este lungimea maximă a unui ciclu elementar din acest graf?

• 5

• 3

• 4

• 6