Продвинутые задачи по теории графов

Задача 1

1.0 балл

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

💡 Решение

Теоретическая база:

Лемма о рукопожатиях: $\sum_{v \in V} \deg(v) = 2|E|$

Неравенство для планарных графов: Если $G$ планарен и $|V| \geq 3$, то $|E| \leq 3|V| - 6$

Подсчёт рёбер:
Поскольку граф регулярный степени 5, каждая из 12 вершин имеет степень 5.
По лемме о рукопожатиях: $12 \times 5 = 2|E|$
Следовательно, $|E| = 30$ рёбер.

Проверка планарности:
Для планарного графа с $n = 12$ вершинами: $|E| \leq 3 \times 12 - 6 = 30$
Неравенство выполняется на границе, но это ещё не гарантирует планарность.

Дополнительный анализ:
Регулярный граф степени 5 на 12 вершинах очень плотный.
Каждая вершина соединена почти с половиной всех вершин.
Такая высокая плотность делает граф непланарным.

Ответ: 30 рёбер, граф не может быть планарным.

Задача 2

1.5 балла

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

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

Определения:

Турнир — ориентированный полный граф (между любыми двумя вершинами есть ровно одно ориентированное ребро)

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

База индукции:
Для $n = 3$ турнир имеет один из видов:
• $A \to B \to C$ (транзитивный)
• $A \to B \to C \to A$ (цикл)
В обоих случаях гамильтонов путь существует.

Индукционный переход:
Пусть утверждение верно для турниров на $k$ вершинах.
Рассмотрим турнир $T$ на $k+1$ вершинах.
Удалим произвольную вершину $v$.

Построение пути:
По предположению индукции, в $T \setminus \{v\}$ есть гамильтонов путь:
$P: v_1 \to v_2 \to \ldots \to v_k$

Вставка вершины $v$:
Рассмотрим три случая:
• Если $v \to v_1$, то путь: $v \to v_1 \to \ldots \to v_k$
• Если $v_k \to v$, то путь: $v_1 \to \ldots \to v_k \to v$
• Иначе найдётся $i$: $v_i \to v \to v_{i+1}$, получаем: $v_1 \to \ldots \to v_i \to v \to v_{i+1} \to \ldots \to v_k$

Алгоритм построения гамильтонова пути:

Начать с произвольной вершины
На каждом шаге добавлять вершину с максимальной исходящей степенью среди оставшихся
Если нет исходящих рёбер, найти подходящее место для вставки в уже построенный путь
Повторять до включения всех вершин

Задача 3

1.5 балла

Найдите хроматический многочлен графа-колеса W₅ (цикл C₅ с дополнительной центральной вершиной, соединённой со всеми вершинами цикла).

💡 Решение через принцип включений-исключений

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

$P(G,k)$ — количество способов правильно раскрасить граф $G$ в $k$ цветов

Структура W₅:
Граф-колесо W₅ состоит из:
• Цикла C₅ на вершинах {1, 2, 3, 4, 5}
• Центральной вершины 0, соединённой со всеми вершинами цикла

Раскраска центра:
Центральную вершину 0 можно покрасить $k$ способами.
Остальные 5 вершин должны иметь цвета, отличные от центра.

Раскраска цикла:
Цикл C₅ нужно раскрасить $(k-1)$ цветами.
Хроматический многочлен нечётного цикла C₅:
$P(C_5, k) = (k-1)^5 - (k-1) = (k-1)[(k-1)^4 - 1]$

Итоговая формула:
$P(W_5, k) = k \cdot P(C_5, k-1) = k \cdot [(k-1)^4 - (k-1) + 1]$
После упрощения: $P(W_5, k) = k[(k-1)^4 - (k-1) + 1]$

Проверка: При $k = 2$: $P(W_5, 2) = 2[1 - 1 + 1] = 2$ ✓

Задача 4

1.5 балла

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

💡 Анализ через теорему Форда-Фалкерсона

Теорема о максимальном потоке:

Величина максимального потока равна пропускной способности минимального разреза

Исходная ситуация:
Максимальный поток $f^* = 15$
По теореме Форда-Фалкерсона, минимальный разрез имеет пропускную способность 15

После удаления ребра $e$:
Новый максимальный поток $f' = 10$
Новый минимальный разрез имеет пропускную способность 10

Анализ изменения:
Поток уменьшился на $15 - 10 = 5$ единиц
Это означает, что удалённое ребро было критическим для потока

Нижняя граница:
Пропускная способность $c(e) \geq 5$
Если $c(e) < 5$, то удаление $e$ не могло уменьшить поток более чем на $c(e)$

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

Задача 5

1.5 балла

Граф G является k-связным (k ≥ 2). Докажите, что любые две вершины графа G лежат на общем цикле.

💡 Доказательство через теорему Менгера

Определения:

k-связный граф — граф остаётся связным после удаления любых k-1 вершин

Теорема Менгера: Граф k-связен ⟺ между любыми двумя вершинами есть k вершинно-непересекающихся путей

Применение теоремы Менгера:
Пусть $u, v$ — любые две вершины в k-связном графе $G$
По теореме Менгера, между $u$ и $v$ есть $k \geq 2$ вершинно-непересекающихся путей

Построение цикла:
Возьмём любые два из этих путей: $P_1$ и $P_2$
$P_1: u = u_0, u_1, u_2, \ldots, u_m = v$
$P_2: u = w_0, w_1, w_2, \ldots, w_n = v$

Объединение путей:
Поскольку пути вершинно-непересекающиеся, $u_i \neq w_j$ для всех $i, j$ (кроме концов)
Объединим $P_1$ и обращённый $P_2$: $u \to \ldots \to v \to \ldots \to u$

Получение цикла:
Получаем цикл, проходящий через вершины $u$ и $v$
Следовательно, любые две вершины лежат на общем цикле

Задача 6

2.0 балла

Постройте алгоритм для проверки изоморфизма двух деревьев за линейное время. Обоснуйте корректность и сложность алгоритма.

💡 Алгоритм через канонизацию деревьев

Идея:

Построить каноническую форму для каждого дерева и сравнить их

Алгоритм канонизации:

Найти центр дерева: Последовательно удалять листья до получения 1-2 вершин
Построить каноническую строку: Обход из центра с лексикографической сортировкой поддеревьев
Сравнить канонические формы: Деревья изоморфны ⟺ их канонические формы совпадают

Поиск центра:
Центр дерева — вершина(ы), минимизирующая максимальное расстояние до других вершин
Алгоритм: удаляем листья уровень за уровнем
Сложность: $O(n)$

Канонизация:
Для каждой вершины строим строку, описывающую её поддерево
Рекурсивно: $canonical(v) = "(" + sort(canonical(children)) + ")"$
Сложность: $O(n \log n)$ из-за сортировки

Оптимизация до $O(n)$:
Используем хеширование вместо строк
Полиномиальное хеширование: $hash(v) = \sum_{u \in children(v)} hash(u) \cdot p^{|subtree(u)|}$
Сложность: $O(n)$

Корректность:
Изоморфные деревья имеют одинаковые центры и структуру
Каноническая форма однозначно определяет структуру дерева
Вероятность коллизии хешей пренебрежимо мала

Итоговая сложность: $O(n)$ времени, $O(n)$ памяти

Задача 7

1.0 балл

Сколько различных помеченных деревьев можно построить на множестве вершин {1, 2, 3, 4, 5}?

💡 Применение формулы Кэли

Формула Кэли:

Количество помеченных деревьев на $n$ вершинах равно $n^{n-2}$

Применение формулы:
Для $n = 5$ вершин: $5^{5-2} = 5^3 = 125$

Интуитивное объяснение:
Каждое дерево можно закодировать последовательностью из $n-2$ чисел
Каждое число от 1 до $n$ может появиться в любой позиции
Отсюда $n^{n-2}$ различных кодов

Ответ: 125 различных помеченных деревьев

🎓 Продвинутые задачи по теории графов

💡 Решение

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

💡 Решение через принцип включений-исключений

💡 Анализ через теорему Форда-Фалкерсона

💡 Доказательство через теорему Менгера

💡 Алгоритм через канонизацию деревьев

💡 Применение формулы Кэли