Exerciții 1349

Indicați câte componente tare conexe are graful orientat G=(V,E) unde V={1, 2, 3, 4, 5, 6, 7, 8, 9, 10} iar E={(1,2), (1,7), (1,10), (2,6), (3,2), (3,5), (3,9), (4,3), (4,6), (5,2), (6,1), (8,7), (9,6), (9,8)}.

Fie un graf neorientat G cu 1002 noduri numerotate cu numere naturale consecutive de la 1 la 1002. Știind că oricare două noduri de aceeași paritate sunt adiacente, indicați cum trebuie modificat graful, astfel încât acesta să devină eulerian.

Fie un arbore cu rădăcină care are 5000 de noduri iar fiecare nod are maxim 4 fii. Indicați care este înălțimea minimă a arborelui

Numărul de circuite elementare diferite (care au cel puțin un arc diferit) care trec prin nodul A din graful orientat alăturat este?

În graful neorientat G cu 100 de noduri, două noduri i și j sunt adiacente dacă |𝑖 − 𝑗| = 8 sau |𝑖 − 𝑗| = 12. Numărul de componente conexe ale grafului este:

Secvența gradelor dintr-un graf neorientat este formată din gradele tuturor nodurilor grafului, aranjate în ordine descrescătoare. Indicați care dintre următoarele secvențe nu poate fi secvență a gradelor pentru niciun graf?

I: 7, 6, 5, 4, 4, 3, 2, 1
II: 6, 6, 6, 6, 3, 3, 2, 2
III: 7, 6, 6, 4, 4, 3, 2, 2
IV: 8, 7, 7, 6, 4, 2, 1, 1

Pentru graful orientat de mai jos, indicați între care perechi de noduri există drum de lungime 5?

Fie graful orientat G=(V,E) unde card(V)=20 iar E={(i,j)|i<j,i,j∈V}. Numărul de componente tare conexe ale grafului G este:

Un arbore binar complet este un arbore cu rădăcină în care fiecare nod are exact doi fii sau niciunul. Ştiind că rădăcina se găseşte pe nivelul 0, numărul maxim de noduri de pe nivelul 5 dintr-un astfel de arbore este?

Se consideră un graf neorientat cu 10 vârfuri numerotate de la 1 la 10, graf cu proprietatea că există muchie între vârfurile i și j dacă și numai dacă i și j sunt numere prime între ele. Care este suma gradelor vârfurilor acestui graf?