Ступінь вершин

Для неорієнтованого графу число ребер, що зв'язані з вершиною х_і, називається ступенем вершини G(х_і), причому петля враховується двічі.

Для орієнтованого графу G = <X, Г> число дуг, що входять у вершину називається напівступенем заходу р(х_і)

" x_i (p(x_i) ³ |Г^-1 (x_i)|);

число дуг, що виходять з вершини x_i - напівступенем виходу s(x_i)

" x_i (s(x_i) ³|Г (x_i)|).

Приклад. Для неорієнтованого графу ступінь вершин х₁, х₂, х₃, х₄ дорівнює відповідно 1, 4, 3, 4 (дуга вважається двічі).

Рис. 17.1. Неорієнтований граф та ступені його вершин s(x1)=1, s(x2)=4, s(x3)=3, s(x4)=4