Grafuri - Clasa a XI-a

Într-un graf neorientat cu 20 muchii, fiecare nod al grafului are gradul un număr nenul. Doar patru dintre noduri au gradul un număr par, restul nodurilor având gradele numere impare.

Care este numărul maxim de noduri pe care poate să le aibă graful?

Variante de răspuns (una corectă)

• 32

• 36

• 38

• 34

Un graf neorientat cu 7 noduri, numerotate de la 1 la 7 are muchiile [1,5], [2,3], [2,4], [2,5], [3,4],

[4,5], [4,7], [5,6], [5,7].

Câte cicluri elementare distincte există în graf? Două cicluri sunt distincte dacă diferă prin cel puţin o muchie.

Variante de răspuns (una corectă)

• 7

• 4

• 5

• 6

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

[3,7], [4,6], [6,8], [7,8]. Dacă se elimină nodul 6 şi toate muchiile incidente cu acesta câte componente conexe va avea subgraful rezultat?

Graful neorientat G este dat prin matricea de adiacenţă următoare.

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

Câte vârfuri ale grafului G au gradul 1?

Variante de răspuns (una corectă)

• 0

• 1

• 2

• 3

Se consideră un graf neorientat complet cu 10 vârfuri. Câte lanţuri elementare distincte de lungime 3 există între vârful 2 şi vârful 4? Două lanţuri sunt distincte dacă diferă prin cel puţin o muchie.

Variante de răspuns (una corectă)

• 90

• 28

• 56

• 45

Se consideră graful neorientat cu 6 noduri, numerotate de la 1 la 6, definit prin listele de adiacentă de mai jos. Câte muchii trebuie adăugate în acest graf astfel încât el să devină graf complet?

1: 3 5

2: 3 4 6

3: 1 2 5

4: 2 6

5: 1 3

6: 2 4

Variante de răspuns (una corectă)

• 16

• 14

• 6

• 8

Într-un graf neorientat complet sunt 2016 muchii. Câte vârfuri are graful?

Se consideră un graf neorientat cu 6 noduri şi 9 muchii. Numărul de muchii ce trebuie adăugate, pentru ca graful obținut să fie complet, este:

Se consideră un graf neorientat cu 7 noduri și 21 de muchii. Indicați numărul minim de muchii care pot fi eliminate, astfel încât graful parțial obținut să aibă două componente conexe, cu cel puțin două noduri fiecare.

Variante de răspuns (una corectă)

Numărul de noduri ale unui graf neorientat fără cicluri, cu 26 de muchii și 12 componente conexe este:

Variante de răspuns (una corectă)

• 18

• 28

• 38

• 48