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

Совокупность рёбер, инцидентных вершине , называется звездой вершины Число рёбер графа, инцидентных вершине называется степенью вершины обозначение deg , т.е. deg = .

ТЕОРЕМА. Сумма степеней всех вершин графа равна удвоенному числу его рёбер, т.е. .

Доказательство. В сумме каждое ребро учтено дважды.<

Если deg = 0, то – изолированная вершина. Если deg = 1, то – концевая вершина. Если все вершины имеют одинаковую степень r, то граф называют регулярным (однородным) степени r. Пример графа степени

0: ...; степени 1:; степени 3:; K_з.з:

Рис. 5.2