Как найти сумму степеней вершин графа

Что такое степень вершины

Граф — это набор точек (вершин) и отрезков (рёбер), соединяющих некоторые пары точек. Степенью вершины называют количество рёбер, выходящих из этой вершины. Степень вершины $v$ обозначают $\deg(v)$.

Если из вершины не выходит ни одного ребра, её степень равна 0 — такую вершину называют изолированной.

Как вычислить сумму степеней всех вершин

Чтобы найти сумму степеней, нужно:

1. Посчитать степень каждой вершины графа (сколько рёбер у неё «торчит»).
2. Сложить все полученные числа.

Пример. Рассмотрим граф с пятью вершинами $A, B, C, D, E$ и рёбрами: $AB, AC, BC, CD, DE$. Степени вершин:

• $A$: соединена с $B$ и $C$ → степень 2
• $B$: соединена с $A$ и $C$ → степень 2
• $C$: соединена с $A, B, D$ → степень 3
• $D$: соединена с $C$ и $E$ → степень 2
• $E$: соединена с $D$ → степень 1

Сумма степеней: $2 + 2 + 3 + 2 + 1 = 10$.

Главное свойство: сумма степеней и количество рёбер

Посчитаем число рёбер в том же графе: $AB, AC, BC, CD, DE$ — всего 5. Сумма степеней равна 10, то есть ровно в 2 раза больше числа рёбер.

Это не случайность. Каждое ребро соединяет две вершины, поэтому при подсчёте степени каждой вершины оно учитывается дважды. Отсюда вытекает теорема о рукопожатиях:

$\sum_{v \in V} \deg(v) = 2 \cdot |E|$

где $|V|$ — количество вершин, $|E|$ — количество рёбер.

Как применить свойство на практике

Найти число рёбер, зная степени вершин

Если в задаче даны степени всех вершин (например, «в графе 4 вершины, каждая степени 3»), нужно:

• вычислить сумму степеней: $4 \times 3 = 12$;
• разделить её на 2: $12 \div 2 = 6$ рёбер.

Это работает и для графа, где степени неодинаковы. Главное — сложить все степени и поделить пополам.

Проверить, может ли существовать граф с заданными степенями

Сумма степеней всегда чётна (так как она равна $2|E|$). Если в условии указаны степени, дающие нечётную сумму, такого графа не существует. Это быстрый способ отсеять ошибочные варианты.

Типовые ошибки

• Забывают учесть все вершины (особенно изолированные — их степень 0, но они влияют на количество вершин).
• Путают понятие «степень» с числом соседей — при подсчёте важно считать каждое ребро ровно один раз для каждой вершины.
• В графах с петлями (если они допускаются) петля даёт вклад 2 в степень вершины, а не 1. В большинстве школьных задач петли не встречаются.

Примеры задач

Задача 1. Граф имеет 7 вершин степени 4 и 6 вершин степени 3. Сколько рёбер в графе?

• Сумма степеней: $7 \cdot 4 + 6 \cdot 3 = 28 + 18 = 46$.
• Число рёбер: $46 \div 2 = 23$.

Задача 2. У графа 8 вершин, сумма степеней равна 14. Возможен ли такой граф?

• Проверка: $14$ — чётное число, значит, да. При этом средняя степень вершины $14/8 = 1,75$, что реалистично (например, несколько изолированных вершин и пара «звёздочек»).

Теперь вы знаете, как находить сумму степеней вершин графа и пользоваться этим свойством для поиска числа рёбер или проверки существования графа.