Fie un arborele cu rădăcină, cu 9 noduri, numerotate de la 1 la 9. Care este vectorul „de taţi” al acestui arbore ştiind că nodurile 1, 2, 3, 4, 5, 6, 7, 8 au exact câte un descendent direct (fiu)?
| Varianta 1 |
(1,2,3,4,5,6,7,8) |
| Varianta 2 |
(1,2,3,4,5,6,7,8,9) |
| Varianta 3 |
(0,1,2,3,4,5,6,7,8) |
| Varianta 4 |
(0,1,2,3,4,5,6,7,8,9) |
Se consideră arborele cu 12 noduri, numerotate de la 1 la 12, definit prin următorul vector „de taţi”: (4, 8, 0, 3, 10, 1, 8, 3, 2, 4, 7, 10). Care dintre nodurile arborelui au exact un descendent direct (fiu)?
| Varianta 1 |
6, 9, 11 |
| Varianta 2 |
1, 2, 7 |
| Varianta 3 |
5, 12, 6, 9, 11 |
| Varianta 4 |
10, 1, 2, 7 |
Se consideră graful orientat cu 6 noduri, numerotate de la 1 la 6, şi arcele (1,2), (1,5), (1,6), (2,3), (4,3), (4,5), (6,5). Care este numărul minim de arce ce trebuie adăugate grafului astfel încât acesta să conţină cel puţin un circuit elementar de lungime 4?
Se consideră graful neorientat cu 6 noduri, numerotate de la 1 la 6, definit prin listele de adiacentă de mai jos. Câte muchii trebuie adăugate în acest graf astfel încât el să devină graf complet?
1: 3 5 2: 3 4 6 3: 1 2 5 4: 2 6 5: 1 3 6: 2 4
| Varianta 1 |
16 |
| Varianta 2 |
14 |
| Varianta 3 |
6 |
| Varianta 4 |
8 |
Fie graful orientat cu 8 vârfuri, numerotate de la 1 la 8, şi arcele (1,2), (2,3), (3,1), (4,5), (5,6), (5,7), (6,7), (7,4), (8,7). Care este numărul minim de arce ce trebuie adăugate astfel încât, pentru oricare două vârfuri x şi y din graf să existe cel puţin un drum de la nodul x la nodul y?
| Varianta 1 |
1 |
| Varianta 2 |
2 |
| Varianta 3 |
3 |
| Varianta 4 |
0 |
Care este vectorul de „taţi” pentru arborele cu 8 noduri, numerotate de la 1 la 8, şi muchiile [1,5], [2,3], [3,6], [3,8], [4,6], [5,7], [6,7], dacă se alege ca rădăcină nodul numerotat cu 6?
| Varianta 1 |
5 3 6 6 1 0 6 3 |
| Varianta 2 |
5 3 6 6 6 0 7 3 |
| Varianta 3 |
7 3 6 6 1 0 6 3 |
| Varianta 4 |
5 3 6 6 7 0 6 3 |
Fie graful orientat cu 6 vârfuri, numerotate de la 1 la 6, şi arcele (1,2), (2,3), (3,1), (4,5), (5,6), (3,5). Care este numărul minim de arce ce trebuie adăugate pentru ca toate vârfurile să aibă gradul interior egal cu gradul exterior?
| Varianta 1 |
2 |
| Varianta 2 |
3 |
| Varianta 3 |
4 |
| Varianta 4 |
5 |
Care este numărul minim de noduri cu gradul 1 pentru un graf neorientat conex cu 21 noduri şi 20 muchii?
Fie graful orientat cu 7 vârfuri, numerotate de la 1 la 7, şi arcele (1,2), (2,3), (3,1), (4,5), (5,6), (5,7), (6,7), (7,4). Care este numărul minim de arce şi care sunt respectivele arce ce ar trebui eliminate pentru ca graful parţial obţinut să nu mai conţină circuite?
| Varianta 1 |
|
| Varianta 2 |
|
| Varianta 3 |
|
| Varianta 4 |
|
Care este numărul minim de muchii ale unui graf neorientat conex, cu 100 de noduri?