Текст. Урок 14. Степень (валентность) вершины. Цепь и цикл. Ориентированные графы

1. Определение степени вершины

В любом графе у каждой вершины есть рёбра, которые из неё выходят (или входят — в неориентированном графе направление не важно).

Определение:
Степень (валентность) вершины — это количество рёбер, инцидентных данной вершине (то есть выходящих из неё или входящих в неё).
Обозначается: $\mathrm{deg}(v)$ (от англ. degree).

Для неориентированного графа ребро считается один раз, независимо от того, смотрим мы «из вершины» или «в вершину».

Пример 1.
Рассмотрим граф:
Вершины: A, B, C, D.
Рёбра: A–B, A–C, B–C, B–D.

Найдём степени:

• Из A выходят рёбра в B и C → $\mathrm{deg}(A)=2$.

• Из B — рёбра в A, C, D → $\mathrm{deg}(B)=3$.

• Из C — рёбра в A, B → $\mathrm{deg}(C)=2$.

• Из D — только в B → $\mathrm{deg}(D)=1$.