Exerciții

Care dintre vârfurile grafului neorientat G, reprezentat prin matricea de adiacenţă următoare, au gradul 0?

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

Pentru reprezentarea unui arbore cu rădăcină, cu 9 noduri, etichetate cu numerele naturale de la 1 la 9, se utilizează vectorul de “taţi”: T=(5,0,2,7,3,3,2,4,7).

Din câte muchii este format un lanţ elementar de lungime maximă, în arborele dat?

Un graf neorientat este reprezentat prin matricea de adiacenţă de mai jos.

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

Câte grafuri parţiale distincte, formate doar din noduri cu gradul egal cu 2, se pot obţine din graful dat? Două grafuri sunt distincte dacă matricele lor de adiacenţă diferă.

Graful orientat G este reprezentat prin matricea de adiacenţă următoare.

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

Câte vârfuri din graful dat au gradul interior egal cu gradul exterior?

Graful neorientat G este dat prin matricea de adiacenţă următoare.

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

Câte vârfuri ale grafului G au gradul 1?

Care dintre următoarele propoziţii este falsă pentru graful orientat G, dat prin matricea de adiacenţă următoare?

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

Care dintre următorii vectori NU poate reprezenta vectorul „de taţi” al unui arbore cu rădăcină, cu 5 noduri, numerotate de la 1 la 5?

Care dintre următoarele propoziţii NU este adevărată pentru graful orientat cu 6 vârfuri, numerotate de la 1 la 6 şi ale cărui arce sunt: (2,1), (3,6), (4,1), (4,3), (4,5), (5,2), (6,4)?

Care este numărul de circuite distincte ale grafului orientat dat prin matricea de adiacenţă alăturată? Două circuite sunt distincte dacă diferă prin cel puţin un arc.

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

Se consideră un graf neorientat cu 5 noduri şi 9 muchii. Care dintre următoarele şiruri de numere poate fi şirul gradelor nodurilor grafului?