Un arbore cu 4
noduri, numerotate de la 1
la 4
, NU poate fi reprezentat prin vectorul de „taţi”:
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
Utilizând metoda backtracking, se generează toate posibilitățile de a forma succesiuni de câte 5
genuri muzicale distincte din mulțimea {jazz, rock, latino, house, pop}
, astfel încât în fiecare succesiune genul latino
precede genul house
. Două succesiuni sunt distincte dacă genurile muzicale sunt în altă ordine.
Primele cinci soluţii generate sunt, în această ordine:
(jazz, rock, latino, house, pop)
(jazz, rock, latino, pop, house)
(jazz, rock, pop, latino, house)
(jazz, latino, rock, house, pop)
(jazz, latino, rock, pop, house)
Imediat înainte de (pop, latino, house, jazz, rock)
este generată soluția:
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
Considerăm că înălțimea unui arbore cu rădăcină este egală cu cea mai mare dintre lungimile lanțurilor elementare care au o extremitate în rădăcină și cealaltă extremitate în oricare dintre “frunzele” arborelui.
Se consideră arborele cu 9
noduri, numerotate de la 1
la 9
, și muchiile [1,2]
, [2,3]
, [2,5]
, [3,7]
, [4,5]
, [5,6]
, [5,8]
, [8,9]
. Scrieți nodurile care pot fi alese drept rădăcină, astfel încât înălțimea arborelui să fie maximă.
Scrieți nodurile în ordine crescătoare, separate prin exact un spațiu!
Un graf orientat are 8
vârfuri, numerotate de la 1
la 8
, și arcele (1,7)
, (1,8)
, (3,5)
, (3,7)
, (4,3)
, (4,7)
, (6,3)
, (6,5)
, (6,7)
, (6,8)
, (8,5)
, (8,7)
. Numărul vârfurilor care au gradul extern nul este:
Varianta 1 |
1 |
Varianta 2 |
2 |
Varianta 3 |
3 |
Varianta 4 |
4 |
Se consideră următoarea operație prin care se transformă un arbore cu rădăcină: se elimină din arbore nodul „frunză” numerotat cu valoarea minimă, marcându-se nodul „tată” al acestuia. Scrieți vectorul de „tați” al unui arbore cu 6
noduri, numerotate de la 1
la 6
, în care nodul 1
este rădăcină, știind că dacă asupra acestui arbore se efectuează de patru ori succesiv operația de transformare menționată mai sus, se marchează, în această ordine, nodurile 5
, 1
, 1
, 1
.
Scrieți elementele vectorului de tați separate prin exact un spațiu, de exemplu 0 1 2 3 4 5
!
Se consideră un graf neorientat conex şi fără cicluri, în care gradul oricărui nod este mai mic sau egal cu 4
. Dacă șase dintre nodurile sale au gradul egal cu 1
, atunci numărul maxim de noduri cu gradul egal cu 4
este:
Varianta 1 |
0 |
Varianta 2 |
1 |
Varianta 3 |
2 |
Varianta 4 |
3 |