Pagina informaticii

Teste de informatică pentru liceu, articole C#, C/C++, PHP

Probleme-întrebări din arbori şi grafuri

Rândul 1

1. Care este numărul maxim de componente conexe pe care le poate avea un graf neorientat cu 20 noduri şi 12 muchii?

2. Pentru arborele reprezentat prin vectorul “de taţi” T=(6,6,5,0,6,4,4,7), scrieţi care este nodul cu cei mai mulţi fii şi care sunt frunzele arborelui.

3. Se consideră un graf orientat cu 6 noduri numerotate de la 1 la 6 şi cu mulţimea arcelor formată doar din arcele:
- de la fiecare nod numerotat cu un număr neprim i (i>1) la toate nodurile numerotate cu numere ce aparţin mulţimii divizorilor proprii ai lui i (divizori diferiţi de 1 şi de i)
- de la nodul numerotat cu 1 la nodul numerotat cu 6
- de la fiecare nod numerotat cu un număr prim i la nodul numerotat cu i-1
Pentru graful dat, câte dintre nodurile grafului au gradul exterior strict mai mare decât gradul
interior?

4. Se consideră graful neorientat cu mulţimea vârfurilor {1,2,3,4,5,6} şi mulţimea muchiilor
{[1,2],[2,3],[3,4],[3,5],[4,5],[1,3],[2,6],[2,4],[4,6]}.
Care este numărul minim de muchii ce trebuie eliminate şi care sunt aceste muchii astfel
încât graful parţial obţinut să nu mai fie conex?

5. Se consideră graful neorientat cu 80 de noduri şi 3160 muchii. Care este numărul de muchii
ce pot fi eliminate astfel încât graful parţial obţinut să devină arbore?

6. Un arbore binar este un arbore cu rădăcină în care fiecare nod are cel mult 2 descendenţi direcţi (fii), iar înălţimea arborelui este reprezentată de numărul maxim de muchii ale unui lanţ elementar ce uneşte rădăcina cu un vârf terminal (frunză). Pentru un arbore binar cu exact 8 noduri, precizaţi care este înălţimea minimă posibilă?  

7. Care este numărul de muchii ale unui graf neorientat cu 12 noduri, în care fiecare nod este adiacent cu exact 11 noduri?  

8. Într-un graf orientat cu 7 noduri suma gradelor interioare ale tuturor nodurilor este egală cu 10. Care este valoarea sumei gradelor exterioare ale tuturor nodurilor?  

9. Într-un graf neorientat cu 6 noduri, numerotate de la 1 la 6, există câte o muchie între oricare două noduri numerotate cu numere consecutive şi câte o muchie între nodul numerotat cu 6 şi fiecare dintre celelalte noduri. Câte subgrafuri cu exact 3 noduri, toate adiacente două câte două, are graful dat? Scrieţi pentru fiecare dintre aceste subgrafuri nodurile din care este format.

10. Un graf neorientat cu 5 noduri are gradele nodurilor egale cu 1,2,2,1,x. Pentru ce valoare a lui x graful este arbore?  Justificare!
a. x=2 b. x<2 c. x>2 d. nicio valoare

11. Într-un arbore cu rădăcină fiecare nod neterminal are exact 2 descendenţi direcţi (fii).
Care este numărul de noduri din arbore dacă acesta are 8 frunze?
a. 8 b. 7 c. 15 d. 10

12. Graful neorientat cu 60 de noduri, numerotate de la 1 la 60, are numai muchiile [1,60],
[60,20], [2,30] şi [4,30]. Care este numărul componentelor conexe ale grafului?
 
13. 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?

14. Într-un graf orientat G cu 6 vârfuri numerotate cu numere distincte de la 1 la 6, există arc de la
vârful i la vârful j dacă şi numai dacă i<j şi j-i>1. Care sunt vârfurile din graf ce au gradul interior mai mare decât gradul exterior?

 

Rândul 2

1. Câte frunze are arborele cu rădăcină descris prin următorul vector ”de taţi”: (6,5,5,2,0,3,3,3,8,7,7)?

2. Într-un graf neorientat cu 10 muchii, fiecare nod are gradul un număr nenul. Doar trei dintre noduri au gradul un număr par, restul nodurilor având gradele numere impare. Care este numărul maxim de noduri pe care poate să le aibă graful?

3. Se consideră un arbore cu rădăcină în care doar 13 dintre nodurile arborelui au exact 2 descendenţi direcţi (fii), restul nodurilor având cel mult un descendent direct (fiu). Care este numărul frunzelor arborelui?

4. Se consideră un graf neorientat cu 10 noduri şi 7 muchii. Care este numărul maxim de componente conexe din care poate fi format graful?

5. Care dintre următoarele valori pot reprezenta gradele nodurilor unui graf neorientat cu 6
noduri?
a. 3 2 2 2 3 3
b. 4 2 2 2 3 2
c. 5 2 2 2 0 3
d. 5 2 2 2 1 2

6. Câte frunze are arborele cu 8 noduri şi rădăcina 1, reprezentat prin matricea de adiacenţă alăturată?
0 1 0 0 1 0 0 0
1 0 1 0 0 0 0 0
0 1 0 1 0 0 0 0
0 0 1 0 0 0 0 0
1 0 0 0 0 1 0 1
0 0 0 0 1 0 1 0
0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0

7. Se consideră un graf orientat cu 6 noduri care are următoarele proprietăti:
- suma gradelor externe ale tuturor varfurilor grafului este egală cu 6;
- sunt doar 3 vârfuri care au gradul intern egal cu 1.
Care este valoarea maximă pe care o poate avea gradul extern al unui vârf din graful dat?
Reprezentaţi prin liste de adiacenţă un graf care îndeplineşte condiţiile din enunţul problemei şi în care unul dintre vîrfuri are acest grad extern maxim.

8. Se consideră graful neorientat G cu 8 noduri, care are următoarele proprietăţi:
- suma gradelor tuturor nodurilor este 12
- graful are exact 3 noduri cu gradul 1
Care este numărul maxim de noduri de grad 0 ale grafului G?

9. Se consideră graful orientat G reprezentat prin listele de adiacenţă alăturate. Care este lungimea maximă a unui drum elementar din acest graf? Care sunt arcele care compun un drum cu aceste proprietăţi?

10. Se consideră un graf neorientat cu 5 noduri, etichetate cu literele 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?  

11. Care este gradul maxim posibil şi care este gradul minim posibil pentru un nod dintr-un graf cu n noduri, care este arbore?

12. Suma gradelor interne ale tuturor vârfurilor unui graf orientat este întotdeauna egală cu:
a. numărul valorilor de 1 aflate sub diagonala principală în matricea sa de adiacenţă
b. produsul gradelor externe ale tuturor vârfurilor grafului
c. suma tuturor valorilor aflate deasupra diagonalei principale în matricea sa de adiacenţă
d. suma gradelor externe ale tuturor vârfurilor grafului

13. Care dintre vectorii următori poate fi vectorul de taţi ai unui arbore cu rădăcină având 10
noduri, numerotate de la 1 la 10?  
a. (0,1,2,3,4,5,0,7,8,9) b. (1,2,3,4,5,7,6,8,9,0)
c. (10,10,10,10,10,10,10,10,10,0) d. (9,8,7,6,5,4,3,2,1,0)

14. Care dintre nodurile arborelui din figura alăturată pot fi considerate ca fiind rădăcină astfel încât astfel încât în arborele cu rădăcină rezultat fiecare nod să aibă cel mult doi descendenţi direcţi (fii)?

Despre autor
Author

Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică

Scrie un comentariu
Nume:

Comentariu:

15 + 10 =