Exerciții 1366

Se consideră graful neorientat cu cinci noduri, reprezentat mai jos.

Numărul minim de muchii ce trebuie adăugate astfel încât, în graful obţinut, între oricare două noduri distincte să existe cel puţin un lanţ elementar de lungime 3, este:

Se consideră graful orientat cu 6 noduri reprezentat prin matricea de adiacenţă de mai jos. Care este numărul tuturor grafurilor parţiale distincte ale grafului dat? Două grafuri parţiale sunt distincte dacă matricele lor de adiacenţă sunt diferite.

0 1 0 1 0 1
0 0 0 0 1 0
0 0 0 0 0 0
0 0 0 0 1 0
1 0 0 0 0 1
0 0 1 0 0 0

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: