Графы: основы — вершины, рёбра, степени и способы задания

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

Что такое граф#

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

Уточнения по видам. Если ребро — упорядоченная пара, граф ориентированный (стрелки от «откуда» к «куда»): так задают односторонние дороги и ссылки между страницами. Если у ребра есть число — вес (расстояние, цена, время), граф взвешенный. Пара вершин может соединяться несколькими рёбрами (мультиграф) или ребром из вершины в неё же (петля) — в базовых задачах их обычно запрещают. Отдельный важный вид — двудольный граф: вершины делятся на две доли, и каждое ребро соединяет вершины разных долей.

Две вершины смежны, если соединены ребром. Ребро и вершина инцидентны, если вершина — конец ребра. Пример: в графе с вершинами $V=\{A,B,C,D\}$ и рёбрами $E=\{AB,AC,BC,CD\}$ вершины $A$ и $B$ смежны, а $A$ и $D$ — нет; ребро $CD$ инцидентно вершинам $C$ и $D$.

Степень вершины и лемма о рукопожатиях#

Степень вершины $\mathrm{deg}(v)$ — число рёбер, инцидентных вершине (петля считается дважды). Вершина степени 0 называется изолированной, степени 1 — висячей. В примере выше: $\mathrm{deg}(A)=2$, $\mathrm{deg}(C)=3$, $\mathrm{deg}(D)=1$.

Главное наблюдение вводной главы: если просуммировать степени всех вершин, каждое ребро посчитается дважды — у него же два конца. Отсюда лемма о рукопожатиях:

Название честное: на вечеринке каждый факт «два человека пожали руки» увеличивает «число рукопожатий» у двух людей сразу. Следствие — на зачёте любят спрашивать: граф с 5 вершинами, у каждой степень 3, имеет $\frac{5\cdot 3}{2}=7,5$ рёбер? Так не бывает! Сумма степеней обязана быть чётной, поэтому граф, у которого нечётное число нечётных вершин, не существует. Число вершин нечётной степени всегда чётно — прямое следствие леммы о рукопожатии.

Ещё одна классика — полный граф $K_n$: все пары вершин соединены. Каждая из $n$ вершин связана с $n-1$ остальными, и каждое ребро посчитано дважды: $|E(K_n)|=\frac{n(n-1)}{2}$. Для $K_5$ это $\frac{5\cdot 4}{2}=10$ рёбер. Кстати, это в точности $C_n^2$ из комбинаторики — выбрать пару вершин из $n$.

Как задать граф для компьютера#

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

Матрица смежности — это по сути матрица из нулей и единиц: на пересечении строки $i$ и столбца $j$ стоит 1, если ребро $ij$ есть. Для ориентированного графа единицы асимметричны, для взвешенного вместо единиц пишут веса. Матрица удобна для плотных графов и для быстрых алгебраических трюков, но для сети с миллионом вершин и миллионом рёбер таблица на $10^{12}$ ячеек — разорение, поэтому на практике чаще используют списки смежности.

1. 1
   Задача: в компании из 7 человек каждый дружит ровно с тремя. Возможно ли это?
2. 2
   Считаем сумму степеней: $7\cdot 3=21$. Число нечётное — а должно быть $2|E|$.
3. 3
   Вывод: такой компании не существует, лемма о рукопожатиях запретила её за одну строку.
4. 4
   Сравните: «каждый дружит ровно с четырьмя» даёт $7\cdot 4=28$, рёбер $14$ — препятствий нет, и граф действительно строится.

Пути, циклы и связность#

Маршрут (путь) — чередующаяся последовательность вершин и рёбер $v_0{e}_1{v}_1{e}_2\dots e_k{v}_k$, где каждое ребро соединяет соседние вершины последовательности. Длина пути — число рёбер. Путь называется простым, если вершины не повторяются. Цикл — замкнутый путь, у которого начало совпадает с концом (в простом цикле все вершины различны, кроме первой и последней).

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

• Дерево — связный граф без циклов; в нём ровно $n-1$ ребро (см. урок о деревьях)
• Двудольный граф — вершины делятся на две доли, рёбра идут только между долями; критерий: нет циклов нечётной длины
• Изоморфные графы — одинаковы с точностью до переименования вершин; проверить изоморфизм на глаз бывает непросто
• Взвешенный граф — на каждом ребре число: километры, минуты, цена; вся навигация живёт именно на взвешенных графах

Быстрая эвристика для связности на контрольной: сумма степеней должна быть хотя бы $2(n-1)$ — столько даёт дерево. Если у графа $n$ вершин и меньше $n-1$ рёбер, он заведомо несвязен. Работает в обе стороны только как необходимое условие: ребра может хватать, а связности — нет (два отдельных треугольника).

Закрепим словарь числами. Возьмите граф из примера выше: вершины $A,B,C,D$, рёбра $AB,AC,BC,CD$. Степени: $\mathrm{deg}(A)=2$, $\mathrm{deg}(B)=2$, $\mathrm{deg}(C)=3$, $\mathrm{deg}(D)=1$; сумма $8$ равна удвоенному числу рёбер $2\cdot 4$ — лемма сходится. Компонента связности одна: из D через C добираемся до всех. Цикл есть ровно один — треугольник ABC; добавьте ребро AD, и циклов станет два, удалите CD — D превратится в изолированную вершину. Одна маленькая конфигурация прогоняет через себя весь словарь урока.