Как найти степени вершин графа: пошаговое решение

Дано: неориентированный граф на шести вершинах $A, B, C, D, E, F$ со списком рёбер $AB, AC, AD, AF, BC, BD, CD, CE, DE, EF$. Найти: степень каждой вершины, сумму степеней и число рёбер.

Степень вершины - это число инцидентных ей рёбер, поэтому считать её можно буквально по списку: сколько раз буква встретилась, такова и степень. Ответ: $\deg A = 4$, $\deg B = 3$, $\deg C = 4$, $\deg D = 4$, $\deg E = 3$, $\deg F = 2$; сумма степеней равна 20, рёбер в графе 10. Калькулятор сверху открыт ровно на этом графе: сними или добавь ребро, и степени пересчитаются вместе с рисунком.

Решение по шагам

Дано. Неориентированный граф без петель и кратных рёбер, множество вершин $V = \{A, B, C, D, E, F\}$, множество рёбер

$$E = \{AB,\ AC,\ AD,\ AF,\ BC,\ BD,\ CD,\ CE,\ DE,\ EF\}.$$

Найти. Степени всех вершин, сумму степеней, число рёбер $|E|$ и число вершин нечётной степени.

Шаг 1. Считаем, сколько раз каждая вершина встретилась в списке. Идём по списку рёбер и напротив каждой буквы ставим палочку. Вершина $A$ входит в рёбра $AB$, $AC$, $AD$, $AF$ - четыре раза. Вершина $B$ входит в $AB$, $BC$, $BD$ - три раза. И так до конца списка.

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

Шаг 2. Проверяем ответ по матрице смежности. Матрица смежности $\mathbf{A}$ простого графа - это таблица из нулей и единиц, где $a_{ij} = 1$, если вершины $i$ и $j$ соединены ребром. Для нашего списка она выглядит так:

$$\mathbf{A} = \begin{pmatrix} 0 & 1 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}.$$

Степень вершины равна сумме элементов её строки (она же сумма столбца - матрица симметрична):

$$\deg v_i = \sum_{j=1}^{n} a_{ij}.$$

Складываем построчно: $0+1+1+1+0+1 = 4$ для $A$, дальше $3$, $4$, $4$, $3$, $2$. Совпало со списком рёбер - значит, ни одно ребро не потеряно и не посчитано дважды.

Шаг 3. Считаем сумму степеней и число рёбер. Складываем полученные степени:

$$\sum_{v \in V} \deg v = 4 + 3 + 4 + 4 + 3 + 2 = 20.$$

По лемме о рукопожатиях сумма степеней равна удвоенному числу рёбер, отсюда

$$|E| = \frac{1}{2} \sum_{v \in V} \deg v = \frac{20}{2} = 10.$$

В исходном списке ровно десять рёбер - проверка сошлась.

Шаг 4. Смотрим на чётность. Нечётную степень имеют только $B$ и $E$ (по 3), остальные четыре вершины чётные. Нечётных вершин две, то есть чётное число, - иначе сумма степеней не могла бы быть целым чётным числом 20.

Ответ. $\deg A = 4$, $\deg B = 3$, $\deg C = 4$, $\deg D = 4$, $\deg E = 3$, $\deg F = 2$; сумма степеней $20$; число рёбер $|E| = 10$; вершин нечётной степени две - $B$ и $E$.

Лемма о рукопожатиях: откуда берётся сумма степеней

Формула $\sum \deg v = 2|E|$ выглядит как отдельная теорема, но доказывается в одну строку двойным подсчётом. Посчитаем число пар «вершина и инцидентное ей ребро». С одной стороны, каждая вершина даёт столько таких пар, какова её степень, и всего их $\sum_{v} \deg v$. С другой стороны, каждое ребро имеет ровно два конца и даёт ровно две пары, значит их $2|E|$. Одна и та же величина посчитана двумя способами, поэтому

$$\sum_{v \in V} \deg v = 2|E|.$$

Бытовое название формулы - про рукопожатия: если в компании каждый пожал кому-то руку, общее число рукопожатий вдвое меньше, чем сумма «личных счётчиков» всех участников.

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

Второе практическое следствие - быстрая проверка существования графа. Граф на 7 вершинах, где каждая имеет степень 3, невозможен: сумма степеней была бы $7 \cdot 3 = 21$, а это нечётное число. А вот на 8 вершинах такой граф есть, и рёбер в нём $8 \cdot 3 / 2 = 12$.

Список рёбер, матрица и рисунок: где искать степень

В задачах граф приходит в одном из четырёх видов, и приём подсчёта каждый раз свой.

Матрица смежности удобна тем, что даёт мгновенную проверку: она симметрична, а на главной диагонали у простого графа стоят нули. Если симметрия нарушена, граф либо ориентированный, либо в условии опечатка. Кстати, у матрицы смежности есть и более тонкое применение: элемент её $k$-й степени считает маршруты длины $k$ между вершинами, а техника возведения разобрана в задаче как возвести матрицу в степень.

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

Петли, кратные рёбра и ориентированный граф

Три оговорки закрывают почти все нестандартные варианты условия.

Петля даёт вклад 2. Ребро, у которого оба конца в одной вершине, входит в неё дважды, поэтому увеличивает степень на два, а не на один. В матрице смежности петля обычно записывается как $a_{ii} = 2$ именно для того, чтобы сумма строки по-прежнему равнялась степени. Лемма о рукопожатиях при этом остаётся верной.

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

У ориентированного графа степеней две. Вместо одной величины считают полустепень захода $\deg^{-} v$ (число входящих дуг, сумма столбца матрицы) и полустепень исхода $\deg^{+} v$ (число исходящих, сумма строки). Лемма превращается в равенство

$$\sum_{v \in V} \deg^{+} v = \sum_{v \in V} \deg^{-} v = |E|,$$

то есть каждая сумма равна числу дуг, а не удвоенному. Множитель 2 здесь исчезает, и это отдельная ловушка на экзамене.

Что даёт последовательность степеней

Выписанные по убыванию степени называют степенной последовательностью графа: у нашего примера это $(4, 4, 4, 3, 3, 2)$. По ней видно многое, не рисуя граф.

Максимальная степень $\Delta = 4$ и минимальная $\delta = 2$ ограничивают структуру: в простом графе на $n$ вершинах степень не превышает $n - 1$, у нас $4 \le 5$ - условие выполнено. Средняя степень равна $2|E|/n = 20/6 \approx 3{,}33$, и она же показана пунктиром на диаграмме в калькуляторе. Если все степени одинаковы, граф называют регулярным: цикл $C_6$ регулярен степени 2, полный граф $K_6$ - степени 5.

Число нечётных вершин отвечает на вопрос об обходе всех рёбер. У связного графа с нулём нечётных вершин есть эйлеров цикл, с двумя - эйлеров путь между ними, с четырьмя и более - ни того ни другого. В нашем примере нечётных ровно две, $B$ и $E$, значит эйлеров путь существует и начинается он в одной из них. Историю самого критерия и разбор исходной задачи Эйлера смотри в статье про семь мостов Кёнигсберга.

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

Частые ошибки

• Ребро отмечено только у одного конца. Каждое ребро обязано увеличить две степени. Если сумма степеней получилась нечётной или не делится на 2 нацело, скорее всего потеряна вторая отметка.
• Петлю посчитали за единицу. Петля добавляет к степени 2. С единицей ломается и лемма о рукопожатиях, и чётность.
• Число рёбер приравняли сумме степеней. $|E|$ - это половина суммы: у нас $20/2 = 10$, а не 20.
• В ориентированном графе взяли множитель 2. Там $\sum \deg^{+} v = |E|$ без удвоения, потому что дуга даёт вклад один раз в исход и один раз в заход, а суммы считаются раздельно.
• На рисунке приняли пересечение линий за вершину. Вершины - только помеченные кружки; пересечения рёбер на плоском чертеже к степеням отношения не имеют.
• Получили нечётное число нечётных вершин. Такого графа не существует: это верный признак ошибки в подсчёте, а не экзотического примера.

FAQ

Чему равна степень изолированной вершины? Нулю: изолированная вершина не входит ни в одно ребро. В матрице смежности ей отвечает строка из одних нулей, а в списке смежности - пустой список соседей.

Может ли степень вершины быть больше числа вершин? В простом графе нет: у каждой вершины не больше $n - 1$ соседей, потому что петли и кратные рёбра запрещены. В мультиграфе с кратными рёбрами и петлями степень не ограничена ничем.

Как найти число рёбер, зная только степени? Сложить все степени и поделить пополам: $|E| = \frac{1}{2}\sum \deg v$. Для регулярного графа степени $k$ на $n$ вершинах формула упрощается до $|E| = nk/2$.

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

Коротко

1. Степень вершины - число инцидентных ей рёбер; петля даёт вклад 2.
2. По списку рёбер степень равна числу вхождений буквы, по матрице смежности - сумме строки, по списку смежности - длине списка соседей.
3. Для графа из условия: $\deg A = 4$, $\deg B = 3$, $\deg C = 4$, $\deg D = 4$, $\deg E = 3$, $\deg F = 2$.
4. Сумма степеней $20 = 2|E|$, значит рёбер $|E| = 10$; нечётных вершин две - $B$ и $E$, и это чётное число, как и обязано быть.
5. У ориентированного графа считают отдельно полустепени захода и исхода, и каждая их сумма равна $|E|$ без множителя 2.