Вероятность и статистика · Графы и деревья

Граф, вершина и ребро

Как описывать сеть связей, считать степени и проверять число рёбер.

6 минут на чтениеЗаданий для самопроверки: 3

Чему научимся

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

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

План рассуждения и проверка понимания

Уточните модель: ориентированный или неориентированный граф, разрешены ли петли и повторные рёбра, что считается вершиной.
Составьте список рёбер и для каждой вершины посчитайте число концов рёбер; петлю при допустимости учитывайте дважды.
Сложите степени и сравните сумму с 2|E|; дополнительно проверьте, что число вершин нечётной степени получилось чётным.

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

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

Схема к теме

Наглядная модель: Граф, вершина и ребро

Как описывать сеть связей, считать степени и проверять число рёбер.

Граф, вершина и ребро → граф
Граф, вершина и ребро → вершина
Граф, вершина и ребро → ребро
Граф, вершина и ребро → степень

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

Проверка пониманияОбъясните тему своими словами

Объясните на примере звезды с четырьмя листьями, почему сумма степеней равна восьми, число рёбер равно четырём и форма нарисованных линий не влияет на эти значения.

В хорошем объяснении есть:

Степень центра и степени листьев посчитаны отдельно и затем сложены.
Каждое ребро учтено ровно у двух концов, что связывает сумму степеней с 2|E|.

Сеть без лишней геометрии

Граф — модель объектов и связей между ними. Объекты называют вершинами, связи — рёбрами. Запись $G=(V,E)$ задаёт множество вершин и множество рёбер. В простом неориентированном графе ребро соединяет две различные вершины, направления нет, а повторных рёбер между одной парой не бывает.

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

Степень вершины

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

Три примера

У графа с рёбрами $AB,BC,CA$ три вершины, три ребра, степень каждой вершины 2. Сумма степеней 6 равна $2\cdot3$ .
Центр соединён с четырьмя листьями, других рёбер нет. Степень центра 4, остальных — по 1; сумма 8, значит рёбер 4.
Если степени пяти вершин равны 2, 2, 2, 1, 1, то сумма 8 и рёбер 4. Такая последовательность реализуется цепочкой из пяти вершин.

Проверка и ошибки

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

Формула, смысл и ограничения

Главные формулы с расшифровкой

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

Формула словами: Для конечного неориентированного графа; петля вносит в степень вершины 2.

От простого к сложному

Проверьте себя

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

Открываем задание…

Источники и соглашения

Объяснения и задачи — авторские. Источники помогают проверить определения, условия и школьную привязку. Обозначения и параметризация указаны в статье.