Grafuri1

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

• 24

• 4

• 4⁶

• 2⁶

Într-un graf neorientat, relația dintre două vârfuri între care există o muchie se numește adiacență.

• ADEVĂRAT

• FALS

Care dintre următoarele afirmații sunt corecte?

• Într-un graf neorientat o muchie poate fi adiacentă cu un vârf.

  
  

• Într-un graf neorientat două muchii pot fi adiacente.

  
  

• Într-un graf neorientat o muchie poate fi incidentă cu un vârf.

  
  

• Într-un graf neorientat două vârfuri pot fi incidente.

  
  

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

• 4¹⁴

• 2¹⁴

• 4²⁸

• 64

Î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?

• 32

• 36

• 10

• 16

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

Pentru graful neorientat din figura de mai jos, care este numărul de muchii ale celui mai lung lanţ, format din noduri distincte, ce are ca extremităţi nodurile 1 şi 3?

• 2

• 3

• 1

• 4

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?

(a)  

Care este numărul minim de muchii ce pot fi eliminate din graful de mai jos astfel încât în graful parţial rezultat să existe exact un vârf de grad 0?

• 1

• 3

• 2

• 5

Care este numărul maxim de noduri de grad 3 într-un graf neorientat cu 5 noduri?

• 4

• 5

• 3

• 2