Exerciții

Se consideră graful orientat din figura de mai jos. Care este numărul minim de arce ce trebuie adăugate grafului astfel încât oricare două vârfuri din graf să fie unite prin drumuri elementare?

Pentru graful neorientat din figura de mai jos, care este numărul de muchii ale celui mai lung lanţ, format din noduri distincte, ce are ca extremităţi nodurile 1 şi 3?

Care este nodul ce poate fi ales ca rădăcină a arborelui din figura de mai jos, astfel încât fiecare nod care nu este de tip frunză să aibă un număr impar de descendenţi direcţi (fii)?

Care este numărul minim de arce ce trebuie adăugate în graful orientat din figura de mai jos astfel încât fiecare vârf să aparţină unui circuit?

Care este numărul nodurilor de tip frunză din arborele cu rădăcină, cu 8 noduri, numerotate de la 1 la 8, reprezentat prin vectorul ”de taţi” (2,0,6,2,4,4,5,5)?

Care este numărul minim de muchii ce pot fi eliminate din graful de mai jos astfel încât în graful parţial rezultat să existe exact un vârf de grad 0?

Într-un arbore cu rădăcină nivelul unui nod este egal cu lungimea lanţului format din noduri distincte care uneşte rădăcina cu acel nod. Rădăcina se află pe nivelul 0. Dacă toate frunzele se află pe nivelul 3 şi oricare nod neterminal aflat pe un nivel k are exact k+1 descendenţi direcţi (fii), care este numărul de noduri din acest arbore?

Care este numărul maxim de noduri de grad 3 într-un graf neorientat cu 5 noduri?

Într-un arbore cu rădăcină, nivelul unui nod este egal cu lungimea lanţului format din noduri distincte care uneşte rădăcina cu acel nod. Care dintre noduri trebuie ales ca rădăcină în arborele din figura de mai jos astfel încât pe fiecare nivel să se găsească un număr impar de noduri?

Care este numărul minim de muchii ce trebuie mutate în graful din figura de mai jos astfel încât acesta să fie conex şi fiecare nod să aparţină unui ciclu?