GrileGrafuri-Arbori

Pentru un graf G, un arbore partial este un graf conex, fără cicluri, continând acelasi număr de noduri ca G si doar muchii din G (dar nu neapărat toate). Numărul de arbori partiali ai grafului de mai jos este egal cu :

• 12

• 11

• 15

• 16

• 9

Fie G un graf neorientat conex, cu multmea de varfuri V, avand proprietatile: (a) fiecare varf are cel mult 3 vecini ̧si (b) exista un varf u∈V astfel ıncat pentru orice v∈V avem d(u, v)≤5, unde d(u, v) reprezinta lungimea celui mai scurt drum dintre varfurile u si v (ca numar de muchii). Care este numarul maxim de varfuri din G?

• 46

• 94

• 125

• 190

• 180

Care dintre cele patru variante de mai jos nu poate reprezenta secvent ̧a gradelor varfurilor unui graf neorientat?

• (1,1,1,2,2,3)

• (1,1,3,3,3,5)

• (1,1,2,3,4,5)

• (1,4,4,4,4,5)

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

• 0

• 1

• 2

• nicio valoare

Fie un arbore binar cu 15 noduri. Numarul nodurilor cu cel putin un fiu este cel mult:

• 14

• 8

• 7

• 1

• 13

Fie un graf neorientat cu multimea nodurilor{1, 2, ..., 2015}. Doua noduri i si j sunt unite printr-o muchie daca si numai daca max(i,j) = 2*min(i,j) sau max(i,j) = 2*min(i,j)+1. Care este numarul de muchii ale acestui graf?

• 2015

• 2016

• 2014

• (2014×2015)/2

• 4058210

Care este ınaltimea maxima a unui arbore cu radacina, avand 11 noduri, ̧stiind ca fiecare nod intern (care nu este radacina sau frunza) are mai multe noduri fiu decat parintele sau? (Inaltimea arborelui este numarul de muchii ale celui mai lung drum de la radacina la o frunza.)

• 2

• 4

• 10

• nu exista un asemenea arbore

• 3

Care este numarul maxim de componente conexe pe care le poate avea un graf neorientat cu 73 de noduri si 219 muchii?

• 53

• 52

• 54

• 51

• 50

Care este numarul minim de componente conexe pe care le poate avea un graf neorientat cu 73 de noduri si 72 muchii?

• 1

• 67

• 5

• 2

• nu exista

Care este numarul minim de componente conexe pe care le poate avea un graf neorientat cu 61 de noduri si 42 muchii?

• 19

• 20

• 18

• 17

• 21