Exerciții

Utilizând metoda backtracking se generează, în ordine crescătoare, toate numerele naturale pare cu trei cifre, cu proprietatea că nu există două cifre egale alăturate și suma cifrelor este 10. Primele cinci numere generate sunt, în această ordine: 136, 154, 172, 190, 208. Al șaselea număr generat este:

Se consideră un graf neorientat cu 7 noduri și 21 de muchii. Indicați numărul minim de muchii care pot fi eliminate, astfel încât graful parțial obținut să aibă două componente conexe, cu cel puțin două noduri fiecare.

Utilizând metoda backtracking se generează, în ordine strict crescătoare, toate numerele de trei cifre din mulțimea {1, 2, 5, 7, 8}, numere cu proprietatea că au cel mult două cifre impare. Primele șapte numere generate sunt, în această ordine: 112, 118, 121, 122, 125, 127, 128. Al optulea număr generat este:

Într-un arbore cu rădăcină considerăm că un nod se află pe nivelul x dacă lanțul elementar care are o extremitate în nodul respectiv și cealaltă extremitate în rădăcina arborelui are lungimea x. Pe nivelul 0 se află un singur nod (rădăcina).

Pe fiecare nivel nenul al unui arbore cu rădăcină există cel puțin o frunză. Dacă ultimul nivel este 3, atunci numărul minim de noduri din arbore este:

Utilizând metoda backtracking se generează toate modalitățile de a scrie numărul 6 ca sumă de numere naturale impare. Termenii fiecărei sume sunt în ordine crescătoare. Cele patru soluții sunt obținute în această ordine: 1+1+1+1+1+1; 1+1+1+3; 1+5; 3+3.

Aplicând același algoritm, numărul soluțiilor obținute pentru scrierea lui 8 este:

Într-un arbore cu 50 de noduri, numerotate de la 1 la 50, rădăcina este nodul 1, iar tatăl oricărui alt nod i al său este nodul numerotat cu [i/2]. Lungimea lanţului cu o extremitate în nodul 14 și cealaltă extremitate în nodul 47 este:

Un arbore cu 9 noduri, numerotate de la 1 la 9, este reprezentat prin vectorul de “taţi” (3, 3, 0, 5, 2, 5, 2, 5, 8). Descendenții direcți (“fii”) ai nodului cu eticheta 5 sunt:

Numărul de noduri ale unui graf neorientat fără cicluri, cu 26 de muchii și 12 componente conexe este:

Într-un graf orientat putem avea cel mult un arc de la un nod la altul și nu putem avea arc de la un nod la el însuși.

Într-un graf orientat cel puțin două vârfuri au gradul intern 2, cel puțin un vârf are gradul intern 3 și cel puțin un vârf are gradul extern 3. Numărul minim de vârfuri ale grafului este:

Un arbore are 9 noduri, numerotate de la 1 la 9, și muchiile [1,2], [1,6], [1,8], [1,9], [2,3], [2,7], [4,5], [5,7]. Care dintre următoarele secvențe conține doar noduri care ar putea fi alese drept rădăcină astfel încât nodul 2 să aibă un număr minim de descendenți.