Степени вершин графа

Степенью (или валентностью) вершины v графа G называется число принадлежащих ей ребер. Степень вершины обозначается через deg v. На рис. 6.1

степени вершин 1, 4 и 6 равны двум, deg v₂ = 3, deg v₅ = 1, deg v₃ = 0.

Вершина степени 0 называется изолированной, вершина степени 1 - висячей (или концевой). Вершина смежная с каждой другой вершиной графа называется доминирующей.

Лемма о рукопожатиях (об эстафете). Сумма степеней всех вершин графа - четное число, равное удвоенному числу m его ребер:

В самом деле, каждое ребро e = (u, v) при вычислении этой суммы считается дважды, один раз при вычислении deg u, другой - при вычислении deg v.

Возможная интерпретация леммы такова: в каждом рукопожатии участвуют 2 руки, поэтому общее число пожатых рук четно (при условии, что каждая рука учитывается столько раз, сколько ее пожимали).

Следствие. В любом графе число вершин нечетной степени четно.

Это следует из леммы и из того, что сумма степеней всех вершин четной степени четна.

На рис. 6.1 граф имеет 2 вершины нечетной степени (v₂ и v₅).

Дата добавления: 2014-01-11