Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

4. Степени вершины

Число дуг, которые имеют вершину своей начальной вершиной, называется полустепенъю исхода вершины аналогично, число дуг, которые имеют своей конечной вершиной, называется полустепенъю захода вершины

Таким образом, на рис. 1.3 полустепень исхода вершины обозначаемая через равна и полустепень захода вершины обозначаемая через равна

Совершенно очевидно, что сумма полустепеней захода всех вершин графа, а также сумма полустепеней исхода всех вершин равны общему числу дуг графа т. е.

где число вершин и число дуг графа

Для неориентированного графа степень вершины определяется аналогично — с помощью соотношения и когда не может возникнуть недоразумений, мы будем обозначать степень вершины через

<< Предыдущий параграф Следующий параграф >>
Оглавление