7/27/2019 Subiecte Grafuri Info Gr 3

1/3

1. Care dintre urmtoarele afirmaii este adevrat pentrugraful neorientat avnd mulimea nodurilor X={1,2,3,4,5}i mulimea muchiilor U={[1,2], [1,5], [2,3], [2,4],[3,4],[4,5]}? (4p.)

a. Este graf hamiltonian, dar nu este eulerian.b. Este graf eulerian, dar nu este hamiltonian.c. Este i graf hamiltonian i graf eulerian.d. Nu este graf hamiltonian, i nici nu este graf eulerian.

Raspuns: a) Deoarece graful format reprezinta un cilcuHamiltonian elemtentar care trece prin fiecare nod algrafului.

2. Se consider graful orientat cu nodurile numerotate de la

1 la 5 i arcele (1,2), (1,5), (2,1), (2,3), (2,5), (3,4), (5,2),(5,4). Care este lungimea maxim a unui drum de la nodul 1la nodul 4, format doar din arce distincte? (4p.)a. 5 b. 6 c. 4 d. 7Raspuns: d) Drumul maxim este format din nodurile 1-2-1-5-2-5-4.

3. Un graf neorientat cu nodurile numerotate de la1 la 4 este reprezentat prin matricea de adiacen

alturat. Care dintre afirmaiile de mai jos esteadevrat pentru acest graf? (4p.)a. Graful este arboreb. Graful nu este conexc. Graful este ciclicd. Graful are toate gradele nodurilor numere pare.

Raspuns: a)Graful este un arbore, deoarece nodul 1 esteradacina, care are ramificatie de dreapta nodul 2 si destanga nodul 3, iar nodul 3 are ramificatied de stanga.

4. Se consider graful orientat cu nodurile numerotate de la1 la 5 i arcele (2,1), (5,1), (1,2), (3,2), (5,2), (4,3), (2,5),(4,5). Care este lungimea maxim a unui drum de la nodul 4la nodul 1, format doar din arce distincte? (4p.)a. 6 b. 5 c. 4 d. 7

7/27/2019 Subiecte Grafuri Info Gr 3

2/3

Raspuns: a) Drumul maxim este format din nodurile 4-3-2-5-2-1.

5. Se consider graful neorientat cu nodurile numerotate de

la 1 la 6 i avnd muchiile[1,2], [2,3], [2,5], [2,6], [3,4], [4,5], [4,6], [5,6]. Ctelanuri , distincte i de lungime 3 exist de la nodul 1 lanodul 4n graful dat? Dou lanuri sunt distincte dac diferprin cel puin o muchie. (4p.)a. 2 b. 0 c. 4 d. 3

Raspuns: d) 3, si acestea sunt : 1-2-3-4, 1-2-6-4, 1-2-5-4.

6. Un arbore cu 9 noduri, numerotate de la 1 la 9, estememorat cu ajutorul vectorului de tait=(9,3,4,7,3,9,0,7,2). Mulimea tuturor nodurilor de tipfrunz este: (4p.)a. {8, 6, 1, 5} b. {1, 6} c. {8} d. {1, 6, 8}

Raspuns: a) Nodurile frunza, nodurile care nu au nici un

successor sunt nodurile 1,5,6 si 8.

7. Se consider graful orientat cu vrfurile numerotate de la1 la 7 i arcele (1,2),(1,7), (2,3), (3,2), (3,4), (4,3), (5,4), (5,6), (6,4), (7,6).Cte vrfuri din graful dat au gradul extern impar? (4p.)a. 4 b. 3 c. 1 d. 2Raspuns: 4 noduri ai gradul extern impar, si acestea suntnodurile 2,3,6,7 care au gradul 1.

8. Un arbore cu 9 noduri, numerotate de la 1 la 9, estememorat cu ajutorul vectorului de tait=(9,3,4,7,3,9,0,7,2). Care este numrul minim de muchiicare trebuie eliminate pentru ca lungimea celul mai lunglan, format din noduri distincte, cu o extremitate n rdcins fie 3? (4p.)

7/27/2019 Subiecte Grafuri Info Gr 3

3/3

a. 4 b. 3 c. 2 d. 5

Raspuns: