GrileGrafuriNeorientate

Care este numarul maxim de noduri de grad 3 ıntr-un graf neorientat cu 5 noduri?

• 2

• 3

• 4

• 5

Fie un graf neorientat in care fiecare nod are un numar par si nenul de vecini, astfel ıncât nu exista doua noduri având acelasi numar de vecini.

Care dintre urmatoarele variante ar putea reprezenta numarul de muchii ale unui astfel de graf?

• 10

• 15

• 16

• nu exista un astfel de graf

Se considera un graf neorientat cu 8 vârfuri numerotate de la 1 la 8 si urmatoarele muchii: {1,7},{1,8},{3,4},{3,5},{3,6},{3,7},{4,7},{5,6},{5,8},{6,7},{6,8},{7,8}. Care este numarul minum de culori cu care pot fi colorate vârfurile grafului astfel ıncât oricare doua vârfuri adiacente sa aiba culori diferite?

• 2

• 3

• 4

• 8

Un graf este reprezentat prin matricea de adiacenta cu 8 linii si 8 coloane, formata din 0 si 1, are urmatoarele trei proprietati:

(i) prima linie contine un singur element cu valoarea 1;

(ii) linia j contine de doua ori mai multe elemente nenule decât linia j−1, pentru orice j ∈ {2,3,...,8};

(iii) ultima linie contine un singur element cu valoarea 0.

Care este numarul total de elemente cu valoarea 0 din matrice?

• 777

• 769

• 528

• nu exista o astfel de matrice

Care dintre cele patru variante de mai jos nu poate reprezenta secventa gradelor vârfurilor 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 are 10 muchii și este conex. Numărul maxim de noduri ale sale este:

• 8

• 9

• 10

• 11

Care este numarul minim de noduri pe care il poate contine un graf neorientat cu 50 de muchii, si in care 15noduri sunt izolate?

• 25

• 26

• 65

• 66

Se considera un graf neorientat cu nodurile: 1,2,3,4,5,6,7,8 si muchiile: [1,3], [1,7], [2,6], [3,7], [5,2], [5,6], [8,4]. Cate componente conexe are graful?

• 1

• 2

• 3

• 8

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

• 2014

• 2016

• (2014 x 2015)/2