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? (4p.)
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)
Răspuns: a.
pentru că graful este conex și dacă mut un nod nu se poate face ciclu.
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? (4p.)
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)
Răspuns: c.
pentru că reiese din desen.
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:
(4p.)
a. {1, 2, 5, 6, 10}
b. {6, 2, 5} c.
{6} d. {5, 2}
Răspuns: b.
pentru că 6 este ascendentul lui 8, 2 ascendentul lui 6 și 5 ascendentul lui 2.
Graful neorientat cu 8 noduri,
numerotate de la 1 la 8, este reprezentat cu ajutorul matricei de
adiacenţă alăturate. Pentru acest graf este adevărată afirmaţia: (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
Răspuns: d.
pentru că graful nu este hamiltonian, are nod cu grad 0 și gradul maxim al unui
nod este 4.
Se consideră graful neorientat cu 6
noduri, definit cu ajutorullistelor de adiacenţă alăturate. Care dintre
mulţimile următoare de noduri are toate elementele extremităţi ale unor lanţuri
delungime 2 cu cealaltă extremitate în nodul 5? (4p.)
1: 4,5,6
2: 5
3: 4
4: 1,3
5: 1,2,6
6: 1,5
a. {1,4,6} b. {2} c. {3}
d. {2,6}
Răspuns: a.
pentru că reiese din desen.
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: (4p.)
a. 3 b. 6 c.
17 d. 18
Răspuns: c.
pentru că 3 este rădăcina.
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: (4p.)
a. 3 b. 56 c. 54 d. 0
Răspuns: d.
pentru că nu există componente conexe în graf.
Într-un arbore cu rădăcină cu 10 noduri,
numerotate de la 1 la 10, nodul 10 este rădăcină, iar
între celelate 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: (4p.)
a. (0,1,2,3,4,5,6,7,8,9) b. (1,2,3,4,5,6,7,8,9,0) c. (2,3,4,5,6,7,8,9,10,0) d. (9,8,7,6,5,4,3,2,1,0)
Răspuns: c.
pentru că 10 este vârful și elementele merg în ordine descrescătoare de la el.
Stabiliţi care dintre următorii
vectori este vector de ”taţi” pentru arborele cu 7 noduri, numerotate de
la 1 la 7, cu rădăcina 1, reprezentat prin matricea de
adiacenţă alăturată: (4p.)
0 1 0 0 1 0 0
1 0 1 1 0 0 0
0 1 0 0 0 0 0
0 1 0 0 0 0 0
1 0 0 0 0 1 1
0 0 0 0 1 0 0
0 0 0 0 1 0 0
a. (1, 0, 2, 2, 1, 5, 5) b. (0, 1, 2, 2, 1, 5, 5) c. (3, 1, 0, 2, 1, 5, 6) d. (2, 1, 0, 2, 1, 5, 2)
Răspuns: b.
pentru că 1 este rădăcina.
