🕸️ Теория графов

Полный курс от основ до сложных теорем

🏠 Главная 🧠 Логика 🔢 Комбинаторика 📊 Информация 🎯 Экзамен

📚 Основы теории графов

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

Граф — это математическая структура, состоящая из множества вершин и множества рёбер, соединяющих эти вершины.

Формально: Граф $G = (V, E)$, где:

  • $V$ — множество вершин (vertices)
  • $E$ — множество рёбер (edges)
  • Каждое ребро $e \in E$ соединяет две вершины
Пример простого графа:

    1 ——— 2
    |     |
    |     |
    3 ——— 4

V = {1, 2, 3, 4}, E = {(1,2), (1,3), (2,4), (3,4)}

📋 Основные определения

Граф $G = (V, E)$ — пара множеств, где $V$ — множество вершин, $E$ — множество рёбер

Дополнение графа $\overline{G}$ — граф на том же множестве вершин, где ребро присутствует тогда и только тогда, когда его нет в исходном графе

Полный граф $K_n$ — граф на $n$ вершинах, где каждая пара вершин соединена ребром

Пустой граф $E_n$ — граф на $n$ вершинах без рёбер

Подграф — граф $H = (V', E')$, где $V' \subseteq V$ и $E' \subseteq E$

Изоморфные графы — графы с одинаковой структурой (существует биекция между вершинами, сохраняющая отношение смежности)

Степень вершины $\deg(v)$ — количество рёбер, инцидентных вершине $v$

Маршрут — последовательность вершин, где каждые две соседние соединены ребром (вершины и рёбра могут повторяться)

Путь — маршрут без повторяющихся рёбер

Простой путь — путь без повторяющихся вершин

Цикл — замкнутый путь (начальная и конечная вершины совпадают)

Простой цикл — цикл без повторяющихся вершин (кроме первой и последней)

Двудольный граф — граф, вершины которого можно разбить на два множества так, что рёбра соединяют только вершины из разных множеств

Ориентированный граф (орграф) — граф, где рёбра имеют направление (дуги)

🔄 Специальные пути и циклы

Эйлеров путь — путь, проходящий через каждое ребро графа ровно один раз

Эйлеров цикл — замкнутый эйлеров путь

Эйлеров граф — граф, содержащий эйлеров цикл

Гамильтонов путь — путь, проходящий через каждую вершину графа ровно один раз

Гамильтонов цикл — замкнутый гамильтонов путь

Гамильтонов граф — граф, содержащий гамильтонов цикл

🌳 Связность и деревья

Связный граф — граф, в котором между любыми двумя вершинами существует путь

Компонента связности — максимальный связный подграф

Дерево — связный граф без циклов

Лес — граф без циклов (несвязное объединение деревьев)

Остовное дерево — подграф связного графа, который является деревом и содержит все вершины исходного графа

Специальные типы графов

Полный граф $K_n$ — граф на $n$ вершинах, где каждая пара вершин соединена ребром

Количество рёбер: $\binom{n}{2} = \frac{n(n-1)}{2}$

Двудольный граф — граф, вершины которого можно разбить на два множества так, что рёбра соединяют только вершины из разных множеств

Дерево — связный граф без циклов

Турнир — ориентированный полный граф

🎯 Фундаментальные теоремы

Лемма о рукопожатиях

Теорема: В любом графе сумма степеней всех вершин равна удвоенному числу рёбер:

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

Следствие: Количество вершин нечётной степени всегда чётно.

Характеризация деревьев

Для связного графа $G$ на $n$ вершинах следующие утверждения эквивалентны:

  1. $G$ — дерево
  2. $G$ связен и имеет $n-1$ рёбер
  3. $G$ не имеет циклов и имеет $n-1$ рёбер
  4. Между любыми двумя вершинами существует единственный путь

Критерий двудольности

Теорема: Граф является двудольным тогда и только тогда, когда он не содержит циклов нечётной длины.

Теорема Эйлера

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

Следствие: Связный граф имеет эйлеров путь тогда и только тогда, когда количество вершин нечётной степени равно 0 или 2.

Задача #1
Лемма о рукопожатиях

💡 Решение

Лемма о рукопожатиях: В любом графе $G = (V, E)$ выполняется:

$$\sum_{v \in V} \deg(v) = 2|E|$$
Идея доказательства: Каждое ребро соединяет ровно две вершины
При подсчёте суммы степеней каждое ребро учитывается дважды — по одному разу для каждой из двух вершин, которые оно соединяет
Поэтому сумма степеней равна удвоенному количеству рёбер
Следствие: Количество вершин нечётной степени всегда чётно.

Доказательство: Пусть $V_{odd}$ — множество вершин нечётной степени, $V_{even}$ — чётной степени.
$\sum_{v \in V_{odd}} \deg(v) + \sum_{v \in V_{even}} \deg(v) = 2|E|$ (чётное число)
Вторая сумма чётна (сумма чётных чисел), значит первая сумма тоже чётна.
Но первая сумма — это сумма нечётных чисел, она чётна только при чётном количестве слагаемых.
Задача #2
Сколько существует различных простых циклов в графе $K_5$?

💡 Решение

В полном графе $K_5$ каждая пара вершин соединена ребром. Нужно найти количество простых циклов.

Циклы длины 3: Это треугольники. Количество способов выбрать 3 вершины из 5: $\binom{5}{3} = 10$
Циклы длины 4: Выбираем 4 вершины из 5: $\binom{5}{4} = 5$ способов. Для каждого набора из 4 вершин количество гамильтоновых циклов: $\frac{(4-1)!}{2} = 3$. Итого: $5 \times 3 = 15$
Циклы длины 5: Это гамильтоновы циклы. Количество: $\frac{(5-1)!}{2} = 12$
Общее количество: $10 + 15 + 12 = 37$ простых циклов
Формула для $K_n$: Количество простых циклов длины $k$ в $K_n$ равно $\binom{n}{k} \cdot \frac{(k-1)!}{2}$ при $k \geq 3$
Задача #3
Граф является двудольным тогда и только тогда, когда в нем нет циклов нечетной длины

💡 Решение

Двудольный граф: Граф, вершины которого можно разбить на два множества $A$ и $B$ так, что каждое ребро соединяет вершину из $A$ с вершиной из $B$.

Доказательство (⇒):

Пусть граф $G$ двудольный с долями $A$ и $B$
Предположим, есть цикл нечётной длины $v_1, v_2, \ldots, v_k, v_1$ где $k$ нечётно
Пусть $v_1 \in A$. Тогда $v_2 \in B$, $v_3 \in A$, $v_4 \in B$, и так далее
При нечётном $k$: $v_k \in B$, но ребро $(v_k, v_1)$ соединяет $B$ и $A$ — это допустимо
Но если рассмотреть чётные позиции: $v_2, v_4, \ldots, v_k \in B$, а нечётные: $v_1, v_3, \ldots, v_{k-1} \in A$
При нечётном $k$ получается, что $v_k \in B$, но должно быть $v_k \in A$ для замыкания цикла — противоречие!

Доказательство (⇐):

Алгоритм построения двудольного разбиения:
  1. Для каждой компоненты связности выберем произвольную вершину $s$
  2. Выполним BFS от $s$, вычислив расстояния до всех вершин
  3. Поместим в множество $A$ все вершины с чётным расстоянием от $s$
  4. Поместим в множество $B$ все вершины с нечётным расстоянием от $s$
Корректность: Пусть $(u,v)$ — ребро, и $d(s,u) = d(s,v)$ (оба чётны или оба нечётны)
Тогда существует путь $s \leadsto u \to v \leadsto s$ длины $d(s,u) + 1 + d(s,v) = 2d(s,u) + 1$ (нечётной)
Это означает существование цикла нечётной длины — противоречие с условием!
Значит, смежные вершины всегда имеют расстояния разной чётности и попадают в разные доли
Задача #4
Среди любых 6 людей найдутся или трое попарно знакомых, или трое попарно незнакомых

💡 Решение (Теорема Рамсея $R(3,3) = 6$)

Переформулировка: В любой 2-раскраске рёбер полного графа $K_6$ найдётся одноцветный треугольник.

Возьмём любую вершину $v$. Из неё выходит 5 рёбер к остальным вершинам
По принципу Дирихле, среди этих 5 рёбер найдутся как минимум $\lceil 5/2 \rceil = 3$ ребра одного цвета
Пусть это красные рёбра к вершинам $a$, $b$, $c$
Случай 1: Если среди рёбер $\{a,b\}$, $\{b,c\}$, $\{a,c\}$ есть красное, то с $v$ образуется красный треугольник
Случай 2: Если все рёбра $\{a,b\}$, $\{b,c\}$, $\{a,c\}$ синие, то треугольник $\{a,b,c\}$ синий
Почему 5 людей недостаточно?
Контрпример: граф $C_5$ (цикл), где рёбра цикла красные, остальные синие. Нет одноцветных треугольников.
Задача #5
Сколько существует различных графов на данных $n$ вершинах?

💡 Решение

Граф на $n$ вершинах определяется выбором подмножества рёбер из всех возможных рёбер
Максимальное количество рёбер в графе на $n$ вершинах: $\binom{n}{2} = \frac{n(n-1)}{2}$
Каждое из этих рёбер может либо присутствовать в графе, либо отсутствовать
Количество способов выбрать подмножество из $\binom{n}{2}$ элементов: $2^{\binom{n}{2}}$
Ответ: $2^{\binom{n}{2}} = 2^{\frac{n(n-1)}{2}}$ различных графов
Примеры:
• $n = 2$: $2^1 = 2$ графа (с ребром и без ребра)
• $n = 3$: $2^3 = 8$ графов
• $n = 4$: $2^6 = 64$ графа
Задача #6
В некоторой компании детей оказалось, что у каждого ровно 5 знакомых мальчиков и ровно 5 знакомых девочек. Тогда количество детей в этой компании делится на 4

💡 Решение

Пусть в компании $m$ мальчиков и $d$ девочек. Построим двудольный граф, где одна доля — мальчики, другая — девочки.

Каждый мальчик знаком с 5 мальчиками и 5 девочками
Каждая девочка знакома с 5 мальчиками и 5 девочками
Рассмотрим рёбра между мальчиками и девочками. Их количество можно подсчитать двумя способами:
  • Со стороны мальчиков: $5m$ рёбер
  • Со стороны девочек: $5d$ рёбер
Значит, $5m = 5d$, откуда $m = d$
Рассмотрим рёбра внутри группы мальчиков. Каждый мальчик знаком с 5 другими мальчиками
По лемме о рукопожатиях: $\sum \deg(v) = 2|E|$, где сумма берётся по всем мальчикам
$5m = 2|E_{boys}|$, значит $m$ должно быть чётным
Аналогично, $d$ должно быть чётным
Поскольку $m = d$ и оба чётны, общее количество детей $m + d = 2m$ делится на 4
Вывод: Количество детей в компании обязательно делится на 4.
Задача #7
Если в графе $2n$ вершин и $n^2 + 1$ ребро, то в нем найдется треугольник

💡 Решение (Теорема Турана)

Это следствие теоремы Турана для треугольников. Докажем от противного.

Предположим, что граф $G$ на $2n$ вершинах с $n^2 + 1$ рёбрами не содержит треугольников
Тогда $G$ — граф без треугольников (triangle-free graph)
По теореме Турана, максимальное количество рёбер в графе без треугольников на $2n$ вершинах равно $\lfloor \frac{(2n)^2}{4} \rfloor = n^2$
Это достигается на полном двудольном графе $K_{n,n}$
Но в нашем графе $n^2 + 1$ рёбер, что больше максимально возможного
Получили противоречие, значит в графе есть треугольник
Теорема Турана: Максимальное количество рёбер в графе на $n$ вершинах без $(r+1)$-клики равно $\left(1 - \frac{1}{r}\right) \frac{n^2}{2}$.
Интуиция: Если рёбер "слишком много", то граф становится "слишком плотным" и обязательно содержит треугольники.
Задача #8
В любом дереве на $n > 1$ вершинах есть хотя бы две висячие вершины

💡 Решение

Висячая вершина — вершина степени 1.
Пусть $T$ — дерево на $n \geq 2$ вершинах. В дереве ровно $n-1$ рёбер
По лемме о рукопожатиях: $\sum_{v \in V} \deg(v) = 2(n-1) = 2n - 2$
Пусть в дереве $k$ висячих вершин и $(n-k)$ невисячих вершин
Каждая невисячая вершина имеет степень $\geq 2$ (поскольку дерево связно и $n \geq 2$)
Поэтому: $\sum_{v \in V} \deg(v) = k \cdot 1 + \sum_{\text{невисячие } v} \deg(v) \geq k + 2(n-k) = 2n - k$
Из равенства $\sum_{v \in V} \deg(v) = 2n - 2$ получаем: $2n - k \leq 2n - 2$
Откуда $k \geq 2$
Примеры:
• Путь из 4 вершин: ровно 2 висячие вершины (концы)
• Звезда $K_{1,n-1}$: $n-1$ висячих вершин
Задача #9
В любом дереве на $n$ вершинах ровно $n-1$ ребро

💡 Решение

Доказательство индукцией по числу вершин:

База: При $n = 1$ дерево состоит из одной вершины без рёбер. $1-1 = 0$ ✓
Предположение: Утверждение верно для всех деревьев с $k < n$ вершинами
Переход: Рассмотрим дерево $T$ на $n$ вершинах
Из предыдущей задачи знаем, что в $T$ есть висячая вершина $v$
Удалим $v$ и инцидентное ей ребро $e$. Получим граф $T'$ на $(n-1)$ вершинах
$T'$ — связный граф без циклов, то есть тоже дерево
По предположению индукции, $T'$ имеет $(n-1)-1 = n-2$ рёбер
Значит, исходное дерево $T$ имеет $(n-2) + 1 = n-1$ рёбер
Альтернативное доказательство: Любое дерево можно построить, начиная с одной вершины и добавляя по одной вершине с одним ребром. После добавления $n$ вершин получим $n-1$ рёбер.
Задача #10
В любом связном графе можно выделить остовное дерево

💡 Решение

Остовное дерево — подграф, который является деревом и включает все вершины исходного графа.
Алгоритм построения остовного дерева:
  1. Начинаем с исходного связного графа $G = (V, E)$
  2. Пока граф содержит циклы:
  3.    • Находим любой цикл в графе
  4.    • Удаляем одно ребро из этого цикла
  5.    • Граф остаётся связным
  6. Когда циклов не остаётся, получаем дерево
Корректность: При удалении ребра из цикла связность не нарушается
Если ребро $e = (u,v)$ принадлежит циклу, то существует альтернативный путь от $u$ к $v$
Поэтому после удаления $e$ граф остаётся связным
Процесс завершится, когда получим связный граф без циклов — дерево
Альтернативные алгоритмы:
• DFS: Строим дерево поиска в глубину
• BFS: Строим дерево поиска в ширину
• Краскал: Добавляем рёбра по возрастанию весов, избегая циклов
• Прим: Растим дерево от выбранной вершины
Задача #11
Любой связный граф, в котором число ребер на единицу меньше числа вершин, является деревом

💡 Решение

Пусть граф $G$ связен и имеет $n$ вершин и $n-1$ рёбер. Докажем, что $G$ — дерево.

Дерево — это связный граф без циклов
Связность дана по условию
Докажем отсутствие циклов от противного
Предположим, в $G$ есть цикл
Удалим одно ребро из цикла — граф останется связным
Получим связный граф на $n$ вершинах с $n-2$ рёбрами
Но связный граф на $n$ вершинах должен иметь не менее $n-1$ рёбер
Противоречие! Значит, циклов нет
Эквивалентные определения дерева:
Для связного графа $G$ на $n$ вершинах эквивалентны:
  1. $G$ — дерево
  2. $G$ имеет $n-1$ рёбер
  3. Между любыми двумя вершинами единственный путь
  4. $G$ связен, но удаление любого ребра нарушает связность
Задача #12
В любом дереве существует единственный простой путь между любыми двумя вершинами

💡 Решение

Существование: Поскольку дерево связно, между любыми двумя вершинами $u$ и $v$ существует путь
Единственность: Предположим, что между $u$ и $v$ существуют два различных простых пути $P_1$ и $P_2$
Пусть $w$ — первая вершина после $u$, в которой пути расходятся
Пусть $x$ — первая вершина после $w$, в которой пути снова встречаются
Тогда от $w$ до $x$ существуют два различных пути:
  • Часть пути $P_1$ от $w$ до $x$
  • Часть пути $P_2$ от $w$ до $x$
Объединение этих путей образует цикл
Но дерево не содержит циклов — противоречие!
Значит, путь между любыми двумя вершинами единственен
Применение: Это свойство используется в алгоритмах поиска LCA (наименьшего общего предка) и в структурах данных для представления иерархий.
Задача #13
Если в графе $2n + 1$ вершин и степень каждой вершины хотя бы $n$, то этот граф связен

💡 Решение

Доказательство от противного:

Предположим, что граф $G$ несвязен
Тогда $G$ можно разбить на компоненты связности
Пусть одна из компонент содержит $k$ вершин, где $k \leq n$
(Если все компоненты содержат $> n$ вершин, то общее число вершин $> 2n$, что противоречит условию)
Рассмотрим любую вершину $v$ в этой компоненте
По условию $\deg(v) \geq n$
Но $v$ может быть соединена только с вершинами своей компоненты
Максимальная степень $v$ в компоненте из $k$ вершин равна $k-1$
Получаем противоречие: $\deg(v) \geq n > k-1 \geq \deg(v)$ при $k \leq n$
Значит, граф связен
Интуиция: Если у каждой вершины "слишком много" соседей относительно размера графа, то граф не может распасться на изолированные части.
Задача #14
Если граф несвязен, то его дополнение связно

💡 Решение

Дополнение графа $\overline{G}$ — граф на том же множестве вершин, где рёбра $(u,v)$ есть тогда и только тогда, когда их нет в исходном графе $G$.
Пусть граф $G$ несвязен
Тогда множество вершин можно разбить на компоненты связности $C_1, C_2, \ldots, C_k$ где $k \geq 2$
В исходном графе $G$ нет рёбер между вершинами из разных компонент
Значит, в дополнении $\overline{G}$ есть рёбра между любыми двумя вершинами из разных компонент
Возьмём любые две вершины $u, v$ в $\overline{G}$
Случай 1: $u$ и $v$ из разных компонент в $G$. Тогда $(u,v) \in E(\overline{G})$ — прямое соединение
Случай 2: $u$ и $v$ из одной компоненты $C_i$ в $G$. Возьмём любую вершину $w$ из другой компоненты $C_j$
Тогда $(u,w) \in E(\overline{G})$ и $(w,v) \in E(\overline{G})$, получаем путь $u \to w \to v$
В любом случае между $u$ и $v$ есть путь в $\overline{G}$
Пример: Граф из двух изолированных рёбер $\{(1,2), (3,4)\}$ несвязен. Его дополнение содержит рёбра $\{(1,3), (1,4), (2,3), (2,4)\}$ и связно.
Задача #15
Связный граф является эйлеровым тогда и только тогда, когда степени всех вершин чётны

💡 Решение (Теорема Эйлера)

Эйлеров цикл — замкнутый путь, проходящий через каждое ребро графа ровно один раз.

Доказательство (⇒):

Пусть в графе есть эйлеров цикл
Рассмотрим любую вершину $v$
Каждый раз, когда цикл проходит через $v$, он "входит" по одному ребру и "выходит" по другому
Поскольку каждое ребро используется ровно один раз, рёбра при $v$ разбиваются на пары "вход-выход"
Значит, степень $v$ чётна

Доказательство (⇐):

Алгоритм построения эйлерова цикла:
  1. Начинаем с любой вершины $v$ и строим путь, каждый раз переходя по неиспользованному ребру
  2. Поскольку степени чётны, в любую вершину (кроме стартовой) можно войти и выйти
  3. Путь закончится в стартовой вершине $v$ (получим цикл)
  4. Если не все рёбра использованы, найдём вершину $u$ на построенном цикле с неиспользованными рёбрами
  5. Построим новый цикл, начиная с $u$, и объединим с исходным
  6. Повторяем до использования всех рёбер
Задача #16
Связный граф содержит эйлеров путь тогда и только тогда, когда количество вершин нечётной степени равно 0 или 2

💡 Решение

Эйлеров путь — путь, проходящий через каждое ребро графа ровно один раз (не обязательно замкнутый).
Случай 1: 0 вершин нечётной степени
Все степени чётны ⟹ существует эйлеров цикл ⟹ существует эйлеров путь
Случай 2: Ровно 2 вершины нечётной степени
Пусть это вершины $u$ и $v$. Добавим ребро $(u,v)$
В новом графе все степени чётны ⟹ есть эйлеров цикл
Удалим добавленное ребро $(u,v)$ из цикла ⟹ получим эйлеров путь от $u$ к $v$
Случай 3: Более 2 вершин нечётной степени
Эйлеров путь имеет начало и конец — максимум 2 "особые" вершины
Все промежуточные вершины должны иметь чётную степень (вход = выход)
Если нечётных вершин > 2, то эйлеров путь невозможен
Задача #17
В любом турнире есть гамильтонов путь

💡 Решение

Турнир — ориентированный граф, где для любой пары вершин $u, v$ есть ровно одна дуга: либо $(u,v)$, либо $(v,u)$.

Доказательство индукцией:

База: $n = 1, 2$ — тривиально
Предположение: Утверждение верно для турниров с $n-1$ вершинами
Переход: Рассмотрим турнир $T$ на $n$ вершинах
Выберем произвольную вершину $v$ и удалим её
Получим турнир $T'$ на $n-1$ вершинах
По предположению, в $T'$ есть гамильтонов путь $P = v_1 \to v_2 \to \ldots \to v_{n-1}$
Нужно вставить $v$ в подходящее место этого пути
Рассмотрим дуги от $v$ к вершинам пути:
  • Если $(v, v_1) \in E$, вставляем в начало: $v \to v_1 \to \ldots \to v_{n-1}$
  • Если $(v_{n-1}, v) \in E$, вставляем в конец: $v_1 \to \ldots \to v_{n-1} \to v$
  • Иначе найдём $i$: $(v_i, v) \in E$ и $(v, v_{i+1}) \in E$
  • Вставляем между ними: $v_1 \to \ldots \to v_i \to v \to v_{i+1} \to \ldots \to v_{n-1}$
Такое место всегда найдётся, поскольку турнир полный

🎨 Раскраска графов

Основные понятия

Раскраска вершин графа — это присвоение каждой вершине графа цвета таким образом, что любые две смежные вершины имеют разные цвета.
Хроматическое число χ(G) — минимальное количество цветов, необходимое для правильной раскраски вершин графа G.
Раскраска рёбер — присвоение каждому ребру цвета так, что любые два смежных ребра имеют разные цвета.
Хроматический индекс χ'(G) — минимальное количество цветов для правильной раскраски рёбер графа G.

Теорема о четырёх красках

Любой планарный граф можно правильно раскрасить не более чем четырьмя цветами.

Историческая справка: Эта знаменитая теорема была сформулирована в 1852 году и доказана только в 1976 году Аппелем и Хакеном с помощью компьютера.

Теорема Визинга

Для любого простого графа G: Δ(G) ≤ χ'(G) ≤ Δ(G) + 1, где Δ(G) — максимальная степень вершины.

Пример: Раскраска полного графа

Задача: Найти хроматическое число полного графа K₅.

Решение:

В полном графе K₅ каждая вершина смежна со всеми остальными. Поэтому все вершины должны иметь разные цвета.

Ответ: χ(K₅) = 5

Общий случай: χ(Kₙ) = n

Пример: Раскраска двудольного графа

Задача: Доказать, что χ(G) ≤ 2 для любого двудольного графа G.

Доказательство:

Пусть G — двудольный граф с долями A и B. Покрасим все вершины из A в красный цвет, а все вершины из B — в синий цвет.

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

Следовательно, χ(G) ≤ 2. ∎

🗺️ Планарные графы

Определения

Планарный граф — граф, который можно нарисовать на плоскости так, что его рёбра пересекаются только в вершинах.
Грань — область плоскости, ограниченная рёбрами планарного графа. Внешняя область также считается гранью.

Формула Эйлера для планарных графов

Для связного планарного графа: v - e + f = 2

где v — число вершин, e — число рёбер, f — число граней.

Теорема Куратовского

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных K₅ или K₃,₃.

Пример: Проверка планарности

Задача: Является ли граф K₅ планарным?

Решение:

Для K₅: v = 5, e = 10

Если граф планарен, то по формуле Эйлера: f = 2 - v + e = 2 - 5 + 10 = 7

Каждая грань ограничена минимум 3 рёбрами, каждое ребро принадлежит максимум 2 граням.

Поэтому: 3f ≤ 2e, то есть 3 × 7 ≤ 2 × 10, получаем 21 ≤ 20 — противоречие!

Ответ: K₅ не является планарным.

🔄 Гамильтоновы графы и циклы

Определения

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

Теорема Дирака

Если в простом графе G с n ≥ 3 вершинами степень каждой вершины не менее n/2, то G содержит гамильтонов цикл.

Теорема Оре

Если в простом графе G с n ≥ 3 вершинами для любых двух несмежных вершин u и v выполняется deg(u) + deg(v) ≥ n, то G содержит гамильтонов цикл.

Пример: Применение теоремы Дирака

Задача: Граф имеет 8 вершин, и степень каждой вершины равна 4. Содержит ли он гамильтонов цикл?

Решение:

n = 8, deg(v) = 4 для всех вершин v

n/2 = 8/2 = 4

Поскольку deg(v) = 4 ≥ 4 = n/2 для всех вершин, по теореме Дирака граф содержит гамильтонов цикл.

🌊 Потоки в сетях

Основные понятия

Сеть — ориентированный граф с выделенными вершинами: источником s и стоком t, где каждому ребру приписана пропускная способность c(e) ≥ 0.
Поток — функция f, определённая на рёбрах, удовлетворяющая:
  • Ограничению пропускной способности: 0 ≤ f(e) ≤ c(e)
  • Закону сохранения потока: для каждой вершины v ≠ s,t сумма входящих потоков равна сумме исходящих

Теорема Форда-Фалкерсона (о максимальном потоке и минимальном разрезе)

Величина максимального потока из s в t равна пропускной способности минимального разреза, разделяющего s и t.

Алгоритм Форда-Фалкерсона

Алгоритм:
  1. Начать с нулевого потока
  2. Найти увеличивающий путь от s к t в остаточной сети
  3. Увеличить поток вдоль этого пути на максимально возможную величину
  4. Повторять шаги 2-3, пока увеличивающие пути существуют

🎓 Продвинутые демонстрационные задачи

Демка 1: Регулярные и планарные графы

Задача: Граф G имеет 12 вершин и является регулярным степени 5. Сколько рёбер в графе G? Может ли такой граф быть планарным?

Решение:
Подсчёт рёбер: По лемме о рукопожатиях: $\sum_{v \in V} \deg(v) = 2|E|$
Поскольку граф регулярный степени 5: $12 \times 5 = 2|E|$
Следовательно, $|E| = 30$ рёбер.
Проверка планарности: Для планарного графа с $n \geq 3$ вершинами: $|E| \leq 3n - 6$
$3 \times 12 - 6 = 30$, значит неравенство выполняется на границе.
Дополнительная проверка: Но для графов без треугольников: $|E| \leq 2n - 4$
Если граф содержит треугольники, то каждая грань ограничена минимум 3 рёбрами.
Регулярный граф степени 5 на 12 вершинах содержит много треугольников.

Ответ: 30 рёбер, граф не может быть планарным из-за высокой плотности рёбер.

Демка 2: Гамильтоновы пути в турнирах

Задача: Докажите, что в любом турнире на n ≥ 3 вершинах существует гамильтонов путь.

Доказательство по индукции:
База: Для n = 3 турнир имеет вид: A → B → C или A → C → B.
В любом случае существует гамильтонов путь.
Переход: Пусть утверждение верно для турниров на k вершинах.
Рассмотрим турнир T на k+1 вершинах. Удалим произвольную вершину v.
Построение пути: По предположению индукции, в T\{v} есть гамильтонов путь P: $v_1 \to v_2 \to ... \to v_k$.
Найдём место для вставки v в этот путь.
Вставка вершины: Если $v \to v_1$, то путь: $v \to v_1 \to ... \to v_k$.
Если $v_k \to v$, то путь: $v_1 \to ... \to v_k \to v$.
Иначе найдётся i: $v_i \to v \to v_{i+1}$, получаем: $v_1 \to ... \to v_i \to v \to v_{i+1} \to ... \to v_k$.
Алгоритм построения:
  1. Начать с произвольной вершины
  2. На каждом шаге добавлять вершину с максимальной исходящей степенью среди оставшихся
  3. Если нет исходящих рёбер, вставить в подходящее место уже построенного пути

Демка 3: Хроматический многочлен колеса

Задача: Найдите хроматический многочлен графа-колеса W₅.

Решение через принцип включений-исключений:
Структура W₅: Граф-колесо W₅ состоит из цикла C₅ и центральной вершины, соединённой со всеми вершинами цикла.
Раскраска центра: Центральную вершину можно покрасить k способами.
Остальные 5 вершин должны иметь цвета, отличные от центра.
Раскраска цикла: Цикл C₅ нужно раскрасить (k-1) цветами.
Хроматический многочлен цикла C₅: $(k-1)^5 - (k-1) = (k-1)[(k-1)^4 - 1]$
Коррекция: Но в колесе вершины цикла не образуют простой цикл из-за центра.
Правильная формула: $P(W_5,k) = k[(k-1)^4 - (k-1) + 1]$

Проверка: При k=2: P(W₅,2) = 2[1-1+1] = 2 ✓ (только центр отличается от остальных)

Демка 4: Анализ потоков в сетях

Задача: Максимальный поток равен 15. После удаления ребра поток стал 10. Что можно сказать о пропускной способности удалённого ребра?

Анализ:
Исходная ситуация: Пусть максимальный поток f* = 15.
По теореме Форда-Фалкерсона, минимальный разрез имеет пропускную способность 15.
После удаления ребра e: Новый максимальный поток f' = 10.
Значит, новый минимальный разрез имеет пропускную способность 10.
Анализ изменения: Удаление ребра e могло повлиять на поток двумя способами:
1) Ребро e входило в минимальный разрез
2) Ребро e было критическим для некоторых путей
Нижняя граница: Поскольку поток уменьшился на 5, пропускная способность удалённого ребра c(e) ≥ 5.
Если c(e) < 5, то удаление e не могло уменьшить поток более чем на c(e).

Ответ: Пропускная способность удалённого ребра не менее 5.

🏆 Экспертные демонстрационные задачи

Экспертная демка 1: Теорема Брукса

Задача: Докажите теорему Брукса: если граф G связен и не является полным графом или нечётным циклом, то χ(G) ≤ Δ(G).

Доказательство:
Случай 1: Если Δ(G) ≤ 2, то G — путь или цикл.
Путь: χ(G) = 2 ≤ Δ(G). Чётный цикл: χ(G) = 2 ≤ Δ(G).
Нечётный цикл исключён по условию.
Случай 2: Δ(G) ≥ 3. Если G не является полным графом, то найдутся две вершины u, v степени Δ(G), не смежные друг с другом.
Построение порядка: Выполним поиск в глубину, начиная с вершины, смежной и с u, и с v.
Получим порядок вершин, где u и v — последние две вершины.
Жадная раскраска: Раскрашиваем вершины в обратном порядке.
Каждая вершина (кроме u и v) имеет не более Δ(G)-1 раскрашенных соседей.
u и v не смежны, поэтому каждая из них имеет не более Δ(G)-1 раскрашенных соседей.

Следствие: Все вершины можно раскрасить Δ(G) цветами.

Экспертная демка 2: Теорема Турана

Задача: Докажите теорему Турана: граф без треугольников на n вершинах имеет не более ⌊n²/4⌋ рёбер.

Доказательство:
Идея: Максимальный граф без треугольников — это полный двудольный граф.
Конструкция: Разобьём n вершин на два множества A и B размеров ⌊n/2⌋ и ⌈n/2⌉.
Соединим каждую вершину из A с каждой вершиной из B.
Подсчёт рёбер: Количество рёбер = ⌊n/2⌋ × ⌈n/2⌉.
При чётном n: (n/2)² = n²/4
При нечётном n: ((n-1)/2) × ((n+1)/2) = (n²-1)/4 = ⌊n²/4⌋
Оптимальность: Любой граф без треугольников с большим числом рёбер можно улучшить перестановкой вершин между долями.

Обобщение: Это частный случай теоремы Турана для графов без клик размера r.

Экспертная демка 3: Теорема Холла

Задача: Докажите теорему Холла о системах различных представителей.

Доказательство через теорию графов:
Построение графа: Создадим двудольный граф G = (X ∪ Y, E), где:
X = {1, 2, ..., n} (индексы множеств)
Y = ⋃ᵢ Aᵢ (объединение всех элементов)
Ребро (i, y) ∈ E ⟺ y ∈ Aᵢ
Связь с паросочетанием: Система различных представителей существует ⟺ в G есть паросочетание, покрывающее все вершины из X.
Применение теоремы Кёнига: Максимальное паросочетание в двудольном графе имеет размер n ⟺ для любого S ⊆ X выполняется |N(S)| ≥ |S|.
Перевод условий: N(S) = ⋃ᵢ∈S Aᵢ, поэтому условие Холла эквивалентно условию существования совершенного паросочетания.

Конструктивность: Доказательство даёт алгоритм построения системы представителей через алгоритмы поиска максимального паросочетания.

Экспертная демка 4: Остовные деревья колеса

Задача: Найдите количество остовных деревьев в графе-колесе W₄ используя теорему Кирхгофа.

Решение через матрицу Лапласа:
Структура W₄: 5 вершин: центр (0) и цикл (1,2,3,4).
Рёбра: (0,1), (0,2), (0,3), (0,4), (1,2), (2,3), (3,4), (4,1)
Матрица Лапласа L: $$L = \begin{pmatrix} 4 & -1 & -1 & -1 & -1 \\ -1 & 3 & -1 & 0 & -1 \\ -1 & 0 & 3 & -1 & -1 \\ -1 & 0 & -1 & 3 & -1 \\ -1 & -1 & 0 & -1 & 3 \end{pmatrix}$$
Удаление строки и столбца: Удалим последнюю строку и столбец: $$L' = \begin{pmatrix} 4 & -1 & -1 & -1 \\ -1 & 3 & -1 & 0 \\ -1 & 0 & 3 & -1 \\ -1 & 0 & -1 & 3 \end{pmatrix}$$
Вычисление определителя: $\det(L') = 4 \det\begin{pmatrix} 3 & -1 & 0 \\ 0 & 3 & -1 \\ 0 & -1 & 3 \end{pmatrix} - (-1) \det\begin{pmatrix} -1 & -1 & 0 \\ -1 & 3 & -1 \\ -1 & -1 & 3 \end{pmatrix} + ...$
После вычислений: $\det(L') = 16$

Ответ: Граф-колесо W₄ имеет 16 остовных деревьев.

🧩 Сложные задачи и алгоритмы

Задача: Хроматический многочлен

Задача: Найти хроматический многочлен дерева с n вершинами.

Решение:

Хроматический многочлен P(G,k) показывает, сколькими способами можно раскрасить граф G в k цветов.

Для дерева T с n вершинами:

P(T,k) = k(k-1)^(n-1)

Обоснование: Корень можно покрасить k способами, каждую следующую вершину — (k-1) способами (любым цветом, кроме цвета родителя).

Задача: Число остовных деревьев

Задача: Найти количество остовных деревьев полного графа K₄.

Решение (теорема Кирхгофа):

Составим матрицу Лапласа L для K₄:

L = \begin{pmatrix} 3 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ -1 & -1 & -1 & 3 \end{pmatrix}

Удалим последнюю строку и столбец, найдём определитель:

det = \begin{vmatrix} 3 & -1 & -1 \\ -1 & 3 & -1 \\ -1 & -1 & 3 \end{vmatrix} = 16

Ответ: K₄ имеет 16 остовных деревьев.

Общая формула: Kₙ имеет n^(n-2) остовных деревьев (формула Кэли).

Задача: Изоморфизм графов

Задача: Разработать алгоритм проверки изоморфизма двух графов.

Подход через инварианты:
  1. Простые инварианты: число вершин, рёбер, последовательность степеней
  2. Спектральные инварианты: собственные значения матрицы смежности
  3. Структурные инварианты: обхват, хроматическое число, число треугольников
  4. Канонические формы: алгоритм Вейсфейлера-Лемана

Сложность: Проблема изоморфизма графов находится в классе NP, но не известно, является ли она NP-полной.

➕ Дополнительные задачи

Дополнительная задача #1
В связном графе хотя бы две вершины имеют одинаковую степень

💡 Решение

Доказательство (принцип Дирихле):

Пусть граф $G$ связен и имеет $n$ вершин
Степень каждой вершины — целое число от 1 до $n-1$
(0 исключено, так как граф связен; $n$ исключено, так как нет петель)
Получается $n$ вершин и только $(n-1)$ возможных значений степени
По принципу Дирихле хотя бы две вершины имеют одинаковую степень
Замечание: Для несвязного графа утверждение неверно. Например, граф из изолированной вершины и полного графа $K_{n-1}$: степени 0, 1, 2, ..., n-2 — все разные.
Дополнительная задача #2
Докажите, что в любом графе количество вершин нечетной степени четно

💡 Решение

Лемма о рукопожатиях: В любом графе $G = (V, E)$ выполняется: $$\sum_{v \in V} \deg(v) = 2|E|$$

Доказательство основного утверждения:

Разбим множество вершин на два подмножества:
  • $V_{even}$ — вершины четной степени
  • $V_{odd}$ — вершины нечетной степени
По лемме о рукопожатиях: $$\sum_{v \in V_{even}} \deg(v) + \sum_{v \in V_{odd}} \deg(v) = 2|E|$$
Левая часть — сумма четного числа (левое слагаемое) и суммы нечетных чисел (правое слагаемое)
Правая часть — четное число
Сумма четного числа и суммы нечетных чисел четна только если количество нечетных слагаемых четно
Значит, $|V_{odd}|$ четно
Пример: В треугольнике все три вершины имеют степень 2 (четную), поэтому количество вершин нечетной степени равно 0 (четно).
Пример 2: В графе-звезде с 4 лучами: центр имеет степень 4 (четную), 4 листа имеют степень 1 (нечетную). Итого: 4 вершины нечетной степени.
Дополнительная задача #3
Граф называется регулярным, если все его вершины имеют одинаковую степень. Докажите, что регулярный граф нечетной степени имеет четное число вершин

💡 Решение

Условие: Граф $G$ регулярен степени $d$, где $d$ нечетно

Пусть граф имеет $n$ вершин
Поскольку граф $d$-регулярен, каждая вершина имеет степень $d$
По лемме о рукопожатиях: $$\sum_{v \in V} \deg(v) = n \cdot d = 2|E|$$
Правая часть $2|E|$ четна
Левая часть $n \cdot d$ должна быть четной
Поскольку $d$ нечетно, для четности произведения $n \cdot d$ необходимо, чтобы $n$ было четным
Примеры:
  • Треугольник $K_3$: 3-регулярен четной степени (степень 2), имеет 3 вершины
  • Полный граф $K_4$: 3-регулярен нечетной степени (степень 3), имеет 4 вершины (четно) ✓
  • Цикл $C_5$: 2-регулярен четной степени, имеет 5 вершин
  • Полный граф $K_6$: 5-регулярен нечетной степени, имеет 6 вершин (четно) ✓
Дополнительная задача #4
Среди любых 6 людей найдутся или трое попарно знакомых, или трое попарно незнакомых

💡 Решение (Теорема Рамсея R(3,3) = 6)

Формулировка в терминах теории графов:

В любом графе на 6 вершинах либо есть треугольник (клика размера 3), либо есть независимое множество размера 3.

Рассмотрим произвольную вершину $v$. У неё есть 5 соседей среди остальных вершин
По принципу Дирихле среди этих 5 вершин либо:
  • Не менее 3 соединены с $v$ рёбрами (назовём их $A$)
  • Не менее 3 не соединены с $v$ рёбрами (назовём их $B$)
Случай 1: $|A| \geq 3$. Если среди вершин множества $A$ есть ребро, то получаем треугольник с вершиной $v$
Если среди вершин множества $A$ нет рёбер, то $A$ образует независимое множество размера 3
Случай 2: $|B| \geq 3$. Аналогично, либо есть ребро в $B$ (тогда рассматриваем подграф), либо $B$ — независимое множество
Интерпретация "знакомства":
• Треугольник = трое попарно знакомых
• Независимое множество = трое попарно незнакомых
Замечание: Число 6 минимально. В графе на 5 вершинах можно построить контрпример (цикл длины 5).
Дополнительная задача #5
Сколько существует различных графов на данных n вершинах?

💡 Решение

Анализ задачи:

Граф на $n$ вершинах определяется выбором подмножества рёбер из всех возможных рёбер.

В полном графе $K_n$ на $n$ вершинах количество рёбер равно $\binom{n}{2} = \frac{n(n-1)}{2}$
Каждое возможное ребро либо присутствует в графе, либо отсутствует
Количество различных графов равно количеству подмножеств множества всех возможных рёбер
Ответ: $2^{\binom{n}{2}} = 2^{\frac{n(n-1)}{2}}$
Примеры:
• $n = 1$: $2^{\binom{1}{2}} = 2^0 = 1$ граф (только изолированная вершина)
• $n = 2$: $2^{\binom{2}{2}} = 2^1 = 2$ графа (с ребром и без ребра)
• $n = 3$: $2^{\binom{3}{2}} = 2^3 = 8$ графов
• $n = 4$: $2^{\binom{4}{2}} = 2^6 = 64$ графа
Дополнительная задача #6
В любом дереве на n > 1 вершинах есть хотя бы две висячие вершины

💡 Решение

Определение: Висячая вершина (лист) - это вершина степени 1.

Доказательство 1 (от противного):

Предположим, что в дереве не более одного листа
Случай 1: Нет листьев вообще. Тогда степень каждой вершины $\geq 2$
По лемме о рукопожатиях: $\sum_{v} \deg(v) = 2|E| \geq 2n$
Но в дереве $|E| = n-1$, поэтому $2|E| = 2(n-1) = 2n-2 < 2n$. Противоречие
Случай 2: Ровно один лист $v$, $\deg(v) = 1$. Остальные вершины имеют степень $\geq 2$
$\sum_{u} \deg(u) = 1 + \sum_{u \neq v} \deg(u) \geq 1 + 2(n-1) = 2n-1$
Но $\sum_{u} \deg(u) = 2|E| = 2(n-1) = 2n-2 < 2n-1$. Противоречие

Доказательство 2 (конструктивное):

Рассмотрим самый длинный простой путь в дереве: $v_1 - v_2 - \ldots - v_k$
Утверждение: $v_1$ и $v_k$ - листья
Доказательство: Если $\deg(v_1) \geq 2$, то у $v_1$ есть сосед $u \neq v_2$
Поскольку дерево не содержит циклов, $u$ не лежит на пути $v_1 - v_2 - \ldots - v_k$
Тогда путь $u - v_1 - v_2 - \ldots - v_k$ длиннее исходного, что противоречит максимальности
Аналогично для $v_k$
Дополнительная задача #7
В любом дереве на n вершинах ровно n − 1 ребро

💡 Решение

Доказательство (математическая индукция):

База индукции: $n = 1$. Дерево из одной вершины имеет 0 рёбер. $1-1 = 0$ ✓
Индукционный переход: Пусть утверждение верно для всех деревьев с $k < n$ вершинами
Рассмотрим дерево $T$ на $n$ вершинах
Выберем любой лист $v$ (он существует при $n \geq 2$)
Удалим вершину $v$ и инцидентное ей ребро $e$
Получим дерево $T'$ на $(n-1)$ вершинах
По предположению индукции $|E(T')| = (n-1) - 1 = n-2$
Следовательно, $|E(T)| = |E(T')| + 1 = (n-2) + 1 = n-1$ ✓
Альтернативное доказательство (через связность и ацикличность):
• Связный граф на $n$ вершинах имеет не менее $n-1$ рёбер
• Ацикличный граф на $n$ вершинах имеет не более $n-1$ рёбер
• Дерево одновременно связно и ацикличо, поэтому имеет ровно $n-1$ рёбер