Exerciții

Care sunt nodurile de tip frunză din arborele de mai jos dacă se alege ca rădăcină nodul 6?

Scrieți valorile în ordine crescătoare, separate prin exact un spațiu.

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?

Un arbore cu 11 noduri, numerotate de la 1 la 11, este memorat cu ajutorul vectorului de „taţi” t=(2,5,5,3,0,2,4,6,6,2,3). Mulţimea tuturor ascendenţilor nodului 8 este:

Un graf orientat este reprezentat cu ajutorul listelor de adiacenţă scrise mai jos.

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

Nodurile grafului care au gradul exterior egal cu 2 sunt:

Graful neorientat cu 8 noduri, numerotate de la 1 la 8, este reprezentat cu ajutorul matricei de adiacenţă de mai jos.

0 1 1 1 0 0 0 0
1 0 1 0 1 1 0 0
1 1 0 0 1 0 0 0
1 0 0 0 0 1 0 0
0 1 1 0 0 1 0 0
0 1 0 1 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Pentru acest graf este adevărată afirmaţia:

Se consideră graful neorientat cu 6 noduri, definit cu ajutorul listelor de adiacenţă alăturate.

1: 4,5,6
2: 5
3: 4
4: 1,3
5: 1,2,6
6: 1,5 

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?

Un arbore cu rădăcină are nodurile numerotate de la 1 la 18 şi este reprezentat prin vectorul de „taţi” t=(8,8,0,3,4,3,4,7,1,2,3,3,7,8,3,5,6,8). Numărul tuturor
descendenţilor nodului 3 este egal cu:

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:

Într-un arbore cu rădăcină, cu 10 noduri, numerotate de la 1 la 10, nodul 10 este rădăcină, iar între celelalte noduri există relaţia: nodul cu numărul i+1 este tatăl celui cu numărul i, pentru i∈{1,2,3,4,5,6,7,8,9}. Vectorul de „taţi” al arborelui astfel definit, este:

Se consideră graful neorientat cu mulţimea nodurilor {1,2,3,4,5,6,7,8} şi mulţimea muchiilor {[1,2], [2,3], [2,4], [4,7], [2,6], [1,5], [5,6], [6,8], [7,8]}.

Pentru a trasforma graful într-un arbore, putem elimina: