Exerciții

Care este numărul maxim de muchii pe care îl poate avea un graf neorientat cu 6 noduri şi 3 componente conexe?

Se consideră graful neorientat din figura următoare. Care este numărul minim de muchii ce se pot elimina astfel încât graful parţial obţinut să aibă exact 3 componente conexe?

Se consideră un graf orientat cu 5 vârfuri şi 8 arce. Care dintre următoarele şiruri de numere poate fi şirul gradelor exterioare ale vârfurilor acestui graf?

Se consideră un graf neorientat complet cu 10 vârfuri. Câte lanţuri elementare distincte de lungime 3 există între vârful 2 şi vârful 4? Două lanţuri sunt distincte dacă diferă prin cel puţin o muchie.

Se consideră graful orientat din figura de mai jos. Câte dintre vârfurile grafului au gradul intern egal cu gradul extern?

Variabila n memorează un număr natural nenul. Care este numărul total de grafuri orientate distincte cu n noduri? Două grafuri orientate sunt distincte dacă matricele lor de adiacenţă sunt diferite.

Care este numărul maxim de muchii pe care-l poate avea un graf neorientat cu 6 noduri, care nu este conex?

Fie T un arbore cu rădăcină. Arborele are 8 noduri etichetate cu numere naturale de la 1 la 8 şi este descris prin următorul vector „de taţi”: (4,1,6,0,1,1,4,7). Care sunt frunzele arborelui?

Scrieți etichetele în ordine crescătoare, separate prin exact un spațiu.

Care dintre următoarele afirmaţii este adevărată pentru orice graf neorientat G cu 5 noduri şi 6 muchii?

Dacă G este un graf neorientat cu 11 noduri şi 13 muchii, fără noduri cu gradul 0, atunci numărul maxim de componente conexe pe care le poate avea graful este: