Exerciții

Câte grafuri neorientate cu 4 vârfuri există?

Într-un graf neorientat, relația dintre două vârfuri între care există o muchie se numește adiacență.

Câte grafuri neorientate, distincte, cu 4 vârfuri, se pot construi? Două grafuri se consideră distincte dacă matricele lor de adiacenţă sunt diferite.

Care dintre următoarele afirmații sunt corecte?

Câte grafuri neorientate, distincte, cu 8 vârfuri, se pot construi? Două grafuri se consideră distincte dacă matricele lor de adiacenţă sunt diferite.

Se consideră un graf orientat cu 6 noduri numerotate de la 1 la 6 şi cu mulţimea arcelor formată doar din arcele:

• de la fiecare nod numerotat cu un număr neprim i (i>1) la toate nodurile numerotate cu numere ce aparţin mulţimii divizorilor proprii ai lui i (divizori diferiţi de 1 şi de i)
• de la nodul numerotat cu 1 la nodul numerotat cu 6
• de la fiecare nod numerotat cu un număr prim i la nodul numerotat cu i-1

Pentru graful dat, care este lungimea celui mai mare drum, format doar din noduri distincte?

Câte frunze are arborele cu rădăcină descris prin următorul vector ”de taţi”: (6,5,5,2,0,3,3,3,8,7,7)?

Într-un graf neorientat cu 20 muchii, fiecare nod al grafului are gradul un număr nenul. Doar patru dintre noduri au gradul un număr par, restul nodurilor având gradele numere impare.

Care este numărul maxim de noduri pe care poate să le aibă graful?

Se consideră un arbore cu rădăcină în care doar 13 dintre nodurile arborelui au exact 2 descendenţi direcţi (fii), restul nodurilor având cel mult un descendent direct (fiu). Care este numărul frunzelor arborelui?

Se consideră un arbore cu 11 muchii. Care este numărul de noduri ale arborelui?