Probleme rezolvate informatica: Probleme rezolvate 3

Realizat de catre :

Apostolache Diana Raluca
Badea Cristian
Focsa Alexandru
Onea Cristian

1. Care dintre următoarele propoziţii NU este adevărată pentru graful orientat cu 6 vârfuri,numerotate de la 1 la 6 şi ale cărui arce sunt: (2,1), (3,6), (4,1), (4,3), (4,5),(5,2), (6,4)? (4p.)

a. vârful numerotat cu 6 aparţine unui circui

b. vârful numerotat cu 1 are gradul extern 0

c. gradul intern al vârfului numerotat cu 4 este 1

d. graful nu are circuite

2. Care este numărul de circuite distincte ale grafului 0 0 1 0 0 0

orientat dat prin matricea de adiacenţă alăturată?             1 0 1 0 1 1
Două circuite sunt distincte dacă diferă prin cel                0 0 0 0 0 0
puţin un arc.(4p.)                                                                 0 0 1 0 0 0
                                                                                            0 0 0 0 0 0
                                                                                            0 0 0 1 1 0
a. 0             b. 1               c. 2                    d. 3

3. Câte dintre nodurile arborelui din figura alăturată pot fi considerate ca fiind rădăcină astfel încât fiecare nod să aibă cel mult doi descendenţi? (6p.)

Raspuns : 6 (adica 4, 6, 7, 8, 9, 0)

4. Se consideră un graf neorientat cu 5 noduri şi 9 muchii. Care dintre următoarele şiruri de numere pot fi gradele nodurilor grafului? (4p.)

a. 4, 2, 6, 4, 2
b. 2, 2, 1, 2, 2
c. 1, 1, 1, 1, 1
d. 4, 3, 3, 4, 4

5. Care este numărul maxim de muchii pe care îl poate avea un graf neorientat cu 6 noduri şi 3 componente conexe?

Raspuns: 6 muchii

6. Se consideră graful neorientat din figura alăturată. Care este numărul minim de muchii ce se pot elimina astfel încât graful parţial obţinut să aibă exact 3 componente conexe? (4p.)

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

7. Se consideră un graf orientat cu 5 vârfuri şi 8 arce. Care dintre următoarele şiruri de numere pot fi gradele exterioare ale vârfurilor acestui graf? (4p.)

a. 2, 3, 1, 1, 1
b. 2, 2, 6, 5, 1
c. 1, 0, 1, 1, 1, 1
d. 1, 1, 0, 2, 1

  8. Se consideră un graf neorientat cu 10 vârfuri astfel încât între oricare două vârfuri distincte există muchie. Câte lanţuri distincte de lungime 3 există între vârful 2 şi vârful 4? Lungimea unui lanţ este egală cu numărul de muchii din care este compus. Două lanţuri sunt distincte dacă diferă prin cel puţin o muchie. :
a. 90               b. 28                    c. 45               d. 56

   9. Se consideră graful orientat din figura alăturată. Câte dintre vârfurile grafului au gradul intern egal
cu gradul extern?
a. 3             b. 2             c. 1               d. 4

Varfurile care au gradul intern egal cu cel extern sunt: 1, 3, 5.


10. Variabila n memorează un număr natural nenul. Care este numărul total de grafuri orientate distincte cu n noduri? Două grafuri orientate sunt distincte dacă matricele lor de adiacenţă sunt diferite. (4p.)

a. 4n(n-1)/2 b. 3 n(n-1)/2 c. 4 n(n-1)d. 2 n(n-1)/2
Exemplu: Luam graful orientat cu 2 noduri.

Apoi inlocuim n cu nr. de noduri (care sunt 2). 42(2-1)/2= 42*1/2= 41 = 4, adica numarul de cazuri.Un graf orientat complet cu n noduri are n*(n-1) muchii. Numărul de submulţimi din mulţimea muchiilor este 2.

11. Care este numărul maxim de muchii pe care-l poate avea un graf neorientat cu 6 noduri, care nu este conex? (4p.)

a. 4 b. 15 c. 12 d. 10

12. Fie T un arbore cu rădăcină. Arborele are 8 noduri numerotate de la 1 la 8 şi este descris prin următorul vector „de taţi”: (4,1,6,0,1,1,4,7). Care sunt frunzele arborelui? (6p.)

Raspuns:   1 2 3 4 5 6 7 8   , iar arborele va arata astfel:
                  4 1 6 0 1 1 4 7
                                                                                                                                                                                               - plecam cu numarul care ii corespunde (este deasupra) lui 0;
- apoi ne uitam care numere ii corespund deasupra cifrei 4;
- apoi facem pentru fiecare cifra in parte, iar numere care nu au descendenti se numesc „frunze” : 2, 3, 5, 8.

13. Care dintre următoarele afirmaţii este adevărată pentru orice graf neorientat G cu 5 noduri şi 6 muchii? (4p.)
a. G are cel puţin un ciclu;
b. G este conex;
c. G are gradele tuturor nodurilor numere pare;
d. G nu poate avea noduri cu gradul 0.

14. Fie T un arbore cu rădăcină. Arborele are 8 noduri numerotate de la 1 la 8 şi este descris prin următorul vector „de taţi”: (3,5,0,3,3,5,5,5). Care este nodul cu cei mai mulţi descendenţi direcţi (fii)? (6p.)
Raspuns: 1 2 3 4 5 6 7 8 , arborele este:

                    3 5 0 3 3 5 5 5



-( explicatiile sunt ca la ex.12 ).Nodul cu cei mai mult descendenti este 5.

15. Dacă G este un graf neorientat cu 11 noduri şi 13 muchii, fără noduri cu gradul 0, atunci
numărul maxim de componente conexe pe care le poate avea graful este: (4p.)
a. 2 b. 4 c. 3 d. 5

16. Fie n un număr natural, n>4. Orice graf neorientat cu n noduri şi n muchii : (4p.)
a. are gradele tuturor nodurilor numere pare
b. este conex
c. are cel puţin un ciclu
d. este arbore.

17. Fie T un arbore cu rădăcină. Arborele are 8 noduri numerotate de la 1 la 8 şi este descris prin următorul vector „de taţi”: (4,5,0,3,4,5,4,5). Care sunt frunzele arborelui?
Raspuns: 1 2 3 4 5 6 7 8 , arborele este:

                  4 5 0 3 4 5 4 5
Frunzele arborelui sunt: 1, 2, 6, 7, 8.

  18. Dacă G este un graf neorientat cu 8 noduri şi 2 componente conexe, atunci graful are cel mult: (4p.)
a. 28 de muchii
b. 12 muchii
c. 21 de muchii
d. 16 muchii
Raspuns: 2 componente conexe : 1-2-3-4-5-6-7 si 8 ;muchii: (7*6)/2=21.

  19. Dacă T este un arbore cu rădăcină cu 100 de noduri, care este numărul minim de frunze pe care le poate avea T?
Raspuns: 1

20. Care este numărul minim de
muchii pe care le poate avea graful
neorientat G, dacă graful din figura
1 reprezintă un subgraf al lui G,
iar graful reprezentat în figura 2
este graf parţial al lui G?(4p.)

a.8       b.7      c.5.                d.6

(Figura 1) (Figura 2)
Raspuns:

21. Se consideră un arbore cu rădăcină, cu 100 noduri, numerotate de la 1 la 100. Dacă nodul 13 are exact 14 fraţi şi nodul 100 este tatăl nodului 13, care este numărul total de
descendenţi direcţi (fii) ai nodului 100?
Raspuns: 15 fii.
Daca nodul 13 este fiu al nodului 100 si are 14 fii, atunci numarul total de descendenti este 15. (14+1=15).

22. Care dintre următoarele afirmaţii referitoare la graful neorientat G, reprezentat în figura alăturată, este adevărată? (4p.)

a.Graful parţial al lui G obţinut prin eliminarea
muchiilor: [5,6], [2,5], [2,3], [2,10],[10,8],[1,3], este
un arbore.
b. Graful conţine un singur ciclu.
c. Cel mai lung lanţ, care conţine numai noduri
distincte, are lungimea 8.
d. Numărul nodurilor de grad par este egal cu
numărul nodurilor de grad impar.

   23. Se consideră graful orientat G, cu 6 vârfuri, definit cu ajutorul listelor de adiacenţă alăturate.Construiţi matricea de adiacenţă corespunzătoare grafului orientat G1, cu 6 vârfuri, în care există arc între vârfurile distincte i şi j dacă şi numai dacă în graful G există cel puţin un drum de la i la j.(6p.)

   1: 2 6       Raspuns: 0 1 1 0 0 1
   2: 3                             0 1 0 0 0 0
   3:                                 0 0 0 0 0 0
   4: 3                             0 0 1 0 0 0
   5: 4 6                         0 0 1 0 0 0
   6: 3                             0 0 1 0 0 0



  24. Se consideră un arbore G, cu rădăcină, memorat cu ajutorul vectorului de taţi următor:
T=(2,0,4,2,4,7,2). Care dintre următoarele afirmaţii este adevărată? (4p.)
a. Nodurile 1,4 şi 6 sunt fraţi.
b. G este conex şi prin eliminarea unei muchii oarecare din G, graful obţinut nu este conex.
c. Prin eliminarea muchiei [6,7] se obţine un graf parţial, conex.
d. Arborele G are 5 frunze.

25. Câte vârfuri ale grafului din figura alăturată, au gradul interior mai mare decât gradul exterior? (6p.)

Raspuns: 3 (adica varfurile 3, 5 si 6)
!!Sunt 2 (3 si 5) dar la varinatele de raspuns arata ca sunt 3 (3,5,6).

26. Se consideră un graf neorientat dat prin listele de adiacenţă alăturate.Care este numărul maxim de muchii care pot fi eliminate din graf astfel încât graful parţial rezultat să fie conex ? (6p.)
1: 2 3
2: 1 3 4
3: 1 2 4 5
4: 2 3 5
5: 3 4
Raspuns: 3

27. Într-un graf orientat G cu 6 vârfuri numerotate cu numere distincte de la 1 la 6, există arc de la i la j dacă şi numai dacă i<j şi j-i>1. Câte vârfuri din graf au gradul interior maimare decât gradul exterior?
Raspuns: 3
1: grad int: 5, grad ext: 2;
2: grad int: 5, grad ext: 2;
3: grad int: 4, grad ext: 3;
4: grad int: 3, grad ext: 4;
5: grad int: 2, grad ext: 5;
6: grad int: 1, grad ext: 5;
-muchiile de la 1 la 5, sunt datorita conditiei i<j (ex:1<2; 2<3), iar restul sunt datorita conditiei j-i>1(ex: 6-1=5>1)

Probleme rezolvate 3

2 comentarii: