Валентность вершин

Количество ребер, инцидентных вершине v, называется степенью (или валент­ностью) вершины v и обозначается d (v):

, .

Обозначим минимальную степень вершины графа G через d(G), а максималь­ную — через D(G):

, .

Если степени всех вершин равны k, то граф называется регулярным степени k:

При этом d(G) = D(G) = k.

а) граф G б) остовный подграф графа G

в) собственный подграф графа G г) правильный подграф графа G

Рис. 5. Подграфы графа G

Степень регулярности является инвариантом графа и обозначается r (G). Для нерегулярных графов r (G) не определено. На рис. 6 приведена диаграмма регулярного графа степени 3.

Рис. 6. Диаграмма регулярного графа степени 3

Если степень вершины равна 0 (то есть d (v) = 0), то вершина называется изолиро­ванной. Если степень вершины равна 1 (то есть d (v) = 1), то вершина называется концевой, или висячей.

Для орграфа число дуг, исходящих из вершины v, называется полустепенью исхо­да, а входящих - полустепенью захода. Обозначаются эти числа, соответственно, и .

Относительно введенных понятий имеет место теорема Эйлера: Сумма степеней вершин графа равна удвоенному количеству ребер:

, .