Степени вершин

Число дуг, которые имеют вершину x_i своей начальной вершиной, называется полустепенью исхода вершины x_i. Обозначается d_о(x_i).

Число дуг, которые имеют вершину x_i своей конечной вершиной, называется полустепенью захода вершины x_i. Обозначается d_t(x_i).

Например: для графа, изображенного на рисунке, имеем:

d_о(x₁)=2 d_t(x₁)=2

d_о(x₂)=2 d_t(x₂)=2

d_о(x₃)=0 d_t(x₃)=2

d_о(x₄)=1 d_t(x₄)=1

d_о(x₅)=2 d_t(x₅)=2

d_о(x₆)=3 d_t(x₆)=1

Для любого графа G

где n – количество вершин в графе;

m – количество дуг в графе.