Grafuri

Se consideră un graf neorientat cu 50 noduri şi 32 muchii. Care este numărul maxim de vârfuri cu gradul 0 pe care le poate avea graful?

• 45

• 40

• 41

• 50

Se consideră un graf neorientat cu 80 de noduri şi 3160 muchii. Care este numărul de muchii ce pot fi eliminate astfel astfel încât graful parţial obţinut să fie arbore?

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

• $5^2$

• $5^4$

• $2^{10}$

• $4^{10}$

Se consideră un graf neorientat cu 5 noduri, etichetate cu câte o literă distinctă din mulţimea {a, b, c, d, e}, în care orice nod etichetat cu o vocală este adiacent cu toate nodurile etichetate cu consoane şi numai cu acestea, iar orice nod etichetat cu o consoană este adiacent numai cu nodurile etichetate cu vocale. Câte muchii are acest graf?

• 12

• 6

• 4

• 3

Se consideră graful neorientat cu 8 noduri, numerotate de la 1 la 8, şi muchiile [1,2], [1,6], [1,7], [2,3], [2,6], [3,6], [3,4], [4,5], [4,8], [5,6], [7,8].

Care este gradul minim al unui nod din acest graf?

Dacă n este un număr natural mpar mai mare decât 2, atunci un graf neorientat cu n noduri, în care fiecare nod este adiacent cu exact n-1 noduri, este întotdeauna:

• arbore

• graf eulerian

• graf neconex

• graf aciclic (graf care nu conţine niciun ciclu)

Care este gradul maxim posibil pentru un nod dintr-un arbore cu 10 noduri?

Un graf neorientat este complet dacă oricare două noduri distincte ale sale sunt adiacente.

Care este numărul de muchii care trebuie eliminate dintr-un graf neorientat, complet, cu 7 noduri, astfel încât graful parţial obţinut să fie arbore?

• 1

• 6

• 15

• 21

Un graf neorientat cu 8 noduri are gradele nodurilor egale cu 1,2,4,2,3,2,1,x. Pentru ce valoare a lui x graful este arbore?

• x<1

• x>3

• x<3

• nicio valoare