GRAFURI

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-1Pentru graful dat, care este lungimea celui mai mare drum, format doar din noduri distincte?

• 6

• 5

• 3

• 4

Se considera graful neorientat cu 6 noduri, definit cu ajutorul listelor de adiacenta alaturate. Care dintre multimile urmatoare de noduri are toate elementele extremitati ale unor lanturi de lungime 2 cu cealalta extremitate în nodul 5?

1: 4,5,6

2: 5

3: 4

4: 1,3

5: 1,2,6

6: 1,5

• 1,4,6

• 2

• 3

• 2,6

Se considera graful neorientat cu multimea nodurilor {1,2,3,4,5,6,7,8} si multimea muchiilor {[1,2], [2,3], [2,4], [4,7], [2,6], [1,5], [5,6], [6,8], [7,8]}.

Pentru atrasforma graful într-un arbore, putem elimina:

• muchiile [1,5] si [1,2]

• muchia [5,6]

• nodul 3

• muchiile [2,6] si [4,7]

Câte dintre vârfurile grafului neorientat G, reprezentat prin matricea de adiacenta alaturata, au gradul un numar par?

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

• 1

• 3

• 2

• 5

Câte dintre vârfurile grafului neorientat G, reprezentat prin matricea de

adiacenta alaturata, 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

• 2

• 1

• 3

• 0

Un graf neorientat este reprezentat prin matricea de adiacenta alaturata. Câte grafuri partiale distincte, formate doar din noduri cu gradul egal cu 2, se pot obtine din graful dat? Doua grafuri sunt distincte daca matricele lor de adiacenta difera.

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

• 2

• 1

• 3

• 0

Graful neorientat G este dat prin matricea de adiacenta alaturata. Câte vârfuri ale grafului G au gradul 1?

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

• 1

• 2

• 3

• 0

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

• 24

• 4

• 46

• 2 LA PUTEREA 6

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

• 1

• 2

• 7

• 12