----------------------------------------------------------------------------------------
Care dintre următoarele șiruri de numere poate fi vectorul gradelor unui graf neorientat cu 6 noduri?
----------------------------------------------------------------------------------------
Teorie.
Definiție Într-un graf neorientat se numește grad al unui vârf numărul de vârful adiacente cu acesta (sau numărul de muchii incidente cu acesta). Gradul unui vârf x se notează d(x) (degree).
Observații:
- un vârf cu gradul 0 se numește izolat. În graful de mai sus, vârful 6 este izolat.
- un vârf cu gradul 1 se numește terminal. În graful de mai sus, vârful 9 este vârf terminal.
- gradul maxim al unui vârf într-un graf cu n vârfuri este n-1.
Teoremă: Într-un graf neorientat, suma gradelor tuturor vârfurilor este dublul numărului de muchii.
Consecințe:
- Suma gradelor tuturor vârfurilor este număr par.
- Într-un graf neorientat, numărul de vârfuri de grad impar este întotdeauna par.
----------------------------------------------------------------------------------------
a) 2,0,1,2,3,3 => suma grade=11 (incorect)
b) 1,2,1,3,4,2 => suma grade=13 (incorect)
c) 5,1,0,2,2,2 => suma grade=12		=> nr. vf. impar=2
d) 2,5,1,2,1,1 => suma grade=12		=> nr. vf. impar=4
---------------------------------------------------------------------------------------
La o analiza mai atentă...
c) Din vârful 1 se duc 5 muchii (unde? la 2,3,4,5,6), dar gr(3)=0 (incorect)
--------------------------------------------------------------------------------------
Răspuns corect: d)

