Exerciții 1349

O matrice de adiacență prin care poate fi reprezentat graful orientat cu 4 vârfuri, reprezentat în figura de mai jos, este:

Se consideră un graf orientat cu 8 vârfuri şi fără circuite. Numărul maxim de arce ale grafului este:

Un graf orientat are 12 arce, 3 componente tare conexe, iar fiecare vârf al său are gradul interior un număr nenul. Numărul maxim de noduri pe care le poate avea graful este:

Utilizând metoda backtracking se generează, în ordine lexicografică, toate şirurile de câte 6 cifre din mulţimea {0,1} cu proprietatea că au cel mult două cifre cu valori egale pe poziţii consecutive. Primele 5 soluții generate sunt, în această ordine: 001001, 001010, 001011, 001100, 001101. Scrieți a 7-a și a 8-a soluție, în ordinea generării acestora, separate prin exact un spațiu.

Matricea de adiacenţă a unui graf neorientat cu 5 noduri are 6 elemente nenule. Numărul minim de componente conexe ale grafului este:

Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte
patru litere din mulţimea A={a,b,c,d,e}, cuvinte care nu conţin două vocale alăturate.
Primele opt cuvinte generate sunt, în ordine: abab, abac, abad, abba, abbb, abbc, abbd,
abbe. Câte dintre cuvintele generate încep cu litera b şi se termină cu litera e?

Într-un graf neorientat două cicluri sunt disjuncte dacă nu au niciun nod comun. Pentru graful neorientat cu 9 noduri, reprezentat mai jos, se construiește o mulțime formată din cicluri elementare, cu proprietatea că oricare două dintre acestea sunt disjuncte.

Numărul maxim de cicluri dintr-o astfel de mulțime este:

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: