
a. (1, 2, 3, 4, 5, 6, 7)
b. (4, 5, 3, 6, 7)
c. (7, 6, 3, 5, 4, 2, 1)
d. (1, 3, 5, 4, 2, 3, 6)
Raspuns : c ,deoarece este singura succesiune de noduri care trece o singura data prin toate varfurile.
Varianta 32. Graful neorientat cu 8 noduri, numerotate de la 1 la 8, este
reprezentat cu ajutorul matricei de adiacenta alaturate. Pentru acest graf este adevarata afirmatia: (4p.)
a. Graful este hamiltonian
b. Graful nu are noduri de grad 0
c. Gradul maxim al unui nod este 3
d. Graful are trei componente conexe

Varianta 34. Graful neorientat cu 60 de noduri, numerotate de la 1 la 60, are numai muchiile [1,60], [60,20], [2,30] si [4,30]. Numarul componentelor conexe ale grafului este egal cu:
(4p.)
a. 3
b. 56
c. 54
d. 0
Raspuns b. deoarece din 60 de noduri scadem 6 noduri si adaugam 2(cele 2 componente conexe) rezultand 56.

conex? (6p.)
1:3,5
2:4
3:1,5
4:2,8
6:
7:10
8:4
9:
10:7
Raspuns :5 componente conexe , trebuie adaugate 4 muchii astfel incat graful sa fie conex.
Varianta 36. Se considera un graf neorientat cu 7 noduri numerotate de la 1 la 7 si muchiile [1,2],[1,3],[2,3],[2,4],[2,5],[2,6],[4,6],[5,7],[6,7]. Care este numarul minim de muchii care trebuie adaugate pentru ca acest graf sa devina eulerian? (4p.)
Raspuns : minim 8 muchii(muchiile albastre) (fiecare nod trebuie sa aiba grad par si trebuie sa existe toate muchiile )
Varianta 38. Urmatorii doi itemi se refera la un graf neorientat cu 7 noduri,nume-rotate de la 1 la 7 si muchiile [1,5], [2,3], [2,4], [2,5], [3,4], [4,5], [4,7], [5,6], [5,7].
1. Care este numarul minim de muchii care trebuie eliminate astfel încât graful sa aiba 3 componente conexe? (6p.)
Raspuns:eliminam [1,5] [5,6] (2 muchii ) si avem 1 si 6 doua componenta conexe {2,3,4,5,7} formeaza a treia componenata conexa .
2. Câte cicluri elementare distincte exista în graf? Doua cicluri sunt distincte daca difera prin cel putin o muchie.
Raspuns: 5 cicluri elementare
Rezolvare :
(2,5,7,4,3,2)
(2,3,4,2)
(3,4,5,2,3)
(3,2,5,7,4,3)
(3,2,4,7,5,3)
Varianta 39. Se considera un graf neorientat cu 8 noduri, numerotate de la 1 la 8, si muchiile [1,5], [1,6], [2,6], [3,4], [3,6], [3,7], [4,6], [6,8], [7,8]. Daca se elimina nodul 6 si toate muchiile incidente cu acesta câte componente conexe va avea subgraful rezultat?
Raspuns : 3 componenete conexe
cacat de probleme
RăspundețiȘtergere