Дискретная математика

Способы задания графов

• Часть 1
• | 2
• | 3
• | 4
• | 5
• | 6

            Степенью или валентностью вершины   v   графа (орграфа) называется число дуг, инцидентных ей при этом каждая петля вносит вклад равный 2.

 Степень вершины   v    обозначается как deg v. Степень изолированной верши-ны равна 0. Вершина, степень которой равна 1, называется висящей или концевой.

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

            Полустепенью исхода из вершины   v   орграфа называется число выходящих из v   дуг и обозначается     degv.

            Для вершины   v1    графа рис.3.2        degv1 = 3,     degv1 = 1,     deg v1 = 4.

Утверждение 1 Для любого конечного графа (орграфа) сумма степеней всех вершин графа  равна удвоенному числу его дуг, т.е. 

,                                                                               (3.1) 

где m- число дуг графа, n- число его вершин.

            Равенство (3.1) является очевидным следствием того, что вклад каждой дуги графа в сумму из левой части (3.1) равен  2.

Утверждение 2. Сумма элементов  i - ой строки или  i -ого столбца матрицы смежности графа равна степени  i -ой  вершины 

                                   deg v =   =                                                      (3.2) 

предыдущаяследующая