ГДЗ по вероятности и статистике, 7 класс, Высоцкий, номер 129: Графы

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

Если вершина является изолированной (не соединена ни с одной другой), то её степень равна 0. Если к вершине подходит одно ребро, её степень равна 1, и так далее.

Рассмотрим произвольное ребро e нашего графа. По определению, ребро соединяет две вершины. Назовём эти концы ребра u и v.

Когда мы считаем степень вершины u, мы учитываем это ребро e как одно из выходящих из u. Значит, ребро e увеличивает значение °(u) на 1.

Аналогично, когда мы считаем степень вершины v, мы также учитываем это же ребро e как одно из выходящих из v. Значит, ребро e увеличивает значение °(v) на 1.

Важный вывод: Каждое отдельное ребро графа участвует в подсчёте степеней ровно двух вершин. Следовательно, каждое ребро добавляет единицу к сумме степеней дважды: один раз для первого конца и один раз для второго конца.

Пусть у нас есть граф с множеством вершин V={v_1,v_2,…,v_n} и множеством рёбер E. Пусть m — общее число рёбер в графе (|E|=m).

Вычислим сумму степеней всех вершин графа:

Мы можем пересчитать эту сумму другим способом: не по вершинам, а по рёбрам. Для каждого ребра e_j∈E (где j меняется от 1 до m) мы выяснили на Шаге 2, что оно даёт вклад в общую сумму S, равный 2 (так как оно заканчивается в двух разных вершинах, увеличивая их степени на 1 каждая).

Так как всего в графе m рёбер, и каждое из них вносит вклад 2 в сумму степеней, то общая сумма равна:

То есть:

Для наглядности рассмотрим простой пример. Пусть у нас есть треугольник (граф из 3 вершин и 3 рёбер).

• Вершина A: соединена с B и C. Степень °(A)=2.
• Вершина B: соединена с A и C. Степень °(B)=2.
• Вершина C: соединена с A и B. Степень °(C)=2.

Сумма степеней: 2+2+2=6.

Число рёбер: 3.

Удваиваем число рёбер: 2·3=6.

Равенство 6=6 выполняется. Доказательство верно.