Test grafuri neorientate

Un graf neorientat are 7 noduri, numerotate de la 1 la 7, și 8 muchii, dintre care șase sunt: [1,2], [2,4], [2,7], [3,4], [4,5], [4,6]. Știind că unul dintre lanțurile elementare care au lungimea maximă este 1, 2, 7, 5, 4, 6, indicați care ar putea fi celelalte două muchii ale grafului.

• [1,4] și [4,7]

• [1,5] și [5,7]

• [2,5] și [4,7]

• [2,6] și [4,7]

Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, are muchiile [1,2], [1,3], [2,3], [4,6]. Indicați numărul de componente conexe ale acestuia.

• 1

• 3

• 7

• 6

Un graf neorientat eulerian cu 5 noduri are un nod cu gradul 4. Indicați numărul minim de muchii ale grafului.

• 6

• 5

• 8

• 10

Se consideră un graf neorientat conex cu n noduri şi m muchii. Pentru a obţine exact 2componente conexe, numărul minim de muchii care trebuie eliminate este egal cu:

• gradul minim din graf

• gradul maxim din graf

• m-1

• n-1

• (𝐦−𝟏)/𝟐

Numărul de subgrafuri distinct ale unui graf neorientat cu n noduri este:

• 2ⁿ

• 2^n-1

• 2^m

• 2^(n-1)

Indicați numărul de noduri ale unui graf neorientat, complet, cu 300 de muchii.

• 20

• 30

• 299

• 300

Un graf neorientat complet are 4 noduri. Indicați o valoare care NU poate fi numărul de muchii ale unui subgraf al acestui graf.

• 0

• 1

• 2

• 3

Un graf neorientat are 40 de noduri și 5 componente conexe, fiecare dintre acestea fiind arbore. Indicați numărul de muchii ale grafului.

• 33

• 35

• 40

• 41

Un graf neorientat cu 8 noduri, numerotate de la 1 la 8, are muchiile [1,2], [1,6], [4,6], [3,6], [6,5], [5,3], [3,4], [7,8], [8,2]. Trei noduri care nu aparţin niciunui ciclu în acest graf pot fi:

• 1, 3, 4

• 2, 7, 8

• 3, 5, 7

• 5, 6,7

Indicați numărul de noduri ale unui graf neorientat, complet, cu 210 muchii.

• 14

• 15

• 20

• 21