E13 Графы: связность, деревья

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

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

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

Главные инструменты: формула $|E| = |V| - 1$ для деревьев, лист (вершина степени 1), индукция по числу вершин с удалением листа, эйлеровы и гамильтоновы пути/циклы. На олимпиадах ВсОШ/Курчатов задачи на деревья требуют умения «видеть структуру» и доказывать существование или невозможность определённых конфигураций.

• Характеристика дерева. Граф с $n$ вершинами является деревом тогда и только тогда, когда он связен и имеет ровно $n-1$ ребро. Условие: конечный граф. Применять: как только задача требует доказать, что граф — дерево, или использовать число рёбер.

• Лемма о листе. В каждом дереве с $\geq 2$ вершинами есть хотя бы два листа (вершины степени $1). *$Условие: конечное дерево, $n \geq 2$. Применять:* при индукции по числу вершин — удаляй лист.

• Формула рукопожатий. $\sum_{v} \deg(v) = 2|E|$. Условие: любой граф. Применять: оценка числа рёбер через сумму степеней.

• Критерий связности. Граф несвязен $\Leftrightarrow$ существует $S \subsetneq V$, $S \neq \emptyset$, такое что нет рёбер между $S$ и $V \setminus S$. Применять: при доказательстве/опровержении связности.

• Теорема Эйлера о пути. В связном графе существует эйлеров цикл $\Leftrightarrow$ все вершины имеют чётную степень; существует эйлеров путь $\Leftrightarrow$ ровно 2 вершины нечётной степени. Применять: задачи о прохождении по всем рёбрам.

• Перевести задачу на язык графов: назвать вершины, рёбра, определить, что значит «связность» в данном контексте.
• Подсчитать рёбра через формулу рукопожатий: $2|E| = \sum \deg(v)$, оценить $|E|$ снизу/сверху.
• Индукция с удалением листа: в дереве есть лист, удали его, применяй индукционное предположение к меньшему дереву, добавь лист обратно.
• Доказать несвязность через разрез: явно указать множество $S$ и показать, что рёбер между $S$ и $\overline{S}$ нет.
• Использовать количество компонент: если добавляем ребро к лесу — число компонент уменьшается на 1; если добавляем ребро внутри компоненты — возникает цикл.
• Рассмотреть «крайний» объект: в дереве самый «длинный» путь (диаметр) — его концы суть листья; это часто стартует красивые аргументы.
• Покраска в два цвета (двудольность): граф двудоен $\Leftrightarrow$ нет нечётных циклов. Деревья всегда двудольны.

Поверхностные признаки (что буквально написано):
- «$n$ городов, $m$ дорог», «$n$ точек, некоторые соединены отрезками»
- «связный граф», «дерево», «лес», «ациклический граф»
- «докажите, что граф можно/нельзя обойти», «найдите минимальное число рёбер»

Структурные признаки (форма выражения, объекты):
- Множество объектов + бинарное отношение (симметричное) между ними
- Условие «нет циклов» или «ровно $n-1$ ребро» в описании
- Задача про «соединённость» компонент, или «минимальное покрытие рёбрами»

Цель задачи (что от тебя хотят):
- Доказать, что граф связен или несвязен при данных условиях
- Найти минимальное/максимальное число рёбер, обеспечивающих нужное свойство
- Доказать существование/несуществование специального обхода (эйлерова, гамильтонова)

Задача 1. Дерево и степени вершин

Условие: В дереве с $n$ вершинами есть $k$ листьев (вершин степени 1). Докажите, что сумма степеней всех нелистовых вершин равна $2(n-1) - k$.

Источник: тренировочная (базовое свойство деревьев)

Как думать (рассуждение ученика$):
1. $Триггер: «дерево», «листья», «сумма степеней» → граф + формула рукопожатий.$2. *$Что знаю: дерево с $n$ вершинами имеет $n-1$ рёбер.$3. *$Формула рукопожатий: $\sum_{v} \deg(v) = 2(n-1)$.$4. *$Листья вносят:* $k \cdot 1 = k$. Нелистья вносят: $2(n-1) - k$.

Решение:
По формуле рукопожатий: $\sum_{v \in V} \deg(v) = 2|E| = 2(n-1)$.

Разобьём сумму: $\sum_{\text{листья}} \deg(v) + \sum_{\text{не-листья}} \deg(v) = 2(n-1)$.

Каждый лист имеет степень 1, листьев $k$, значит $k + \sum_{\text{не-листья}} \deg(v) = 2(n-1)$.

Отсюда $\sum_{\text{не-листья}} \deg(v) = 2(n-1) - k$.

Ответ: $2(n-1) - k$.

Что главное: Формула рукопожатий + характеристика дерева ($|E| = n-1$) — немедленно.

Задача 2. Связность после удаления рёбер

Условие: Дан связный граф $G$ с $n$ вершинами и $m$ рёбрами, $m \geq n$. Докажите, что из $G$ можно удалить некоторое ребро так, чтобы граф остался связным.

Источник: тренировочная

Как думать (рассуждение ученика$):
1. $Что знаю:* связный граф с $m \geq n$ рёбрами — значит, рёбер больше, чем в остовном дереве ($n-1$ рёбер$).
2. $Ключевая идея: остовное дерево — минимальный связный подграф. Любое ребро вне остовного дерева — лишнее: его можно удалить, связность сохранится.$3. *$Строго: ребро $e$ «мост» (его удаление нарушает связность) $\Leftrightarrow$ $e$ входит в каждое остовное дерево $\Leftrightarrow$ $e$ не лежит ни в каком цикле.

Решение:
Построим остовное дерево $T$ графа $G$ (оно существует, так как $G$ связен). $T$ имеет $n-1$ ребро. Поскольку $m \geq n > n-1$, существует ребро $e \in E(G) \setminus E(T)$.

Удалим $e$ из $G$. Граф $G \setminus \{e\}$ содержит остовное дерево $T$ (которое не содержит $e$), следовательно $G \setminus \{e\}$ связен.

Ответ: Можно удалить любое ребро, не входящее в остовное дерево.

Что главное: Понятие «моста» и остовного дерева. Если рёбер больше $n-1$, есть «нелишнее» ребро вне любого дерева — его удаление безопасно.

• Ошибка: думать, что «дерево» = «ациклический граф». Дерево — ациклический И связный граф. Несвязный ациклический граф — это «лес». → Как избежать: всегда проверяй оба условия: нет циклов + связность.
• Ошибка: $|E| = n-1$ → дерево. Граф с $n$ вершинами и $n-1$ рёбрами не обязан быть деревом (может быть лесом из нескольких компонент). Нужна и связность. → Как избежать: теорема «$n-1$ ребро + связность ↔ дерево» — оба условия вместе.
• Ошибка: неправильно считать компоненты. После удаления $k$ рёбер из дерева получается лес из $k+1$ компонент — не $k$. → Как избежать: явно проверяй: дерево с $n$ вершинами, удаляем $k$ рёбер → $k+1$ дерево с суммой $n$ вершин.
• Ошибка: путать «степень» и «число соседей». В простом графе (без кратных рёбер) они совпадают, но в мультиграфе — нет. → Как избежать: уточни, является ли граф простым.
• Ошибка: доказывать связность без покрытия всех пар вершин. Иногда показывают, что от одной вершины достижимы все — это достаточно для связности. Но нужно явно сослаться на это. → Как избежать: укажи: «от вершины $v$ достижимы все $n-1$ остальных, значит граф связен».