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

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

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

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

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

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

Три примера

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

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

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