Типы конечных графов

Число ребер, связанных с вершиной n_i (петля учитывается два­жды), называется степенью вершины и обозначается deg (n_i).

deg (n₂)=4

deg (n₅)=0

Степень изилирования вершины равна 0. Легко показать, что в любом графе сумма степеней всех вершин равна удвоенному числу ребер, а число вершин нечетной степени всегда четно.

В орграфе различают положительные d ⁺ (n_i) и отрицательные d ^- (n_i) степени вершин, которые равны соответственно числу исходящих из n_i и заходящих в n_i дуг.

Очевидно, что суммы положительных…………………………….