Доказательство (классическое, коротко).
Теорема. Всякое конечное связное неориентированное дерево с $n$ вершинами имеет ровно $n-1$ ребро.
Доказательство по индукции. Для $n=1$ утверждение верно (ребер $0$). Пусть утверждение верно для всех деревьев с $n-1$ вершинами. Возьмём дерево $T$ с $n>1$ вершинами. В любом конечном дереве есть лист (вершина степени 1): возьмём самый длинный простой путь в $T$, его конец — лист. Удалим этот лист и инцидентное ему ребро; получим связное ациклическое графо—то есть дерево с $n-1$ вершинами, которое по индуктивному предположению имеет $n-2$ ребра. Вернём удалённое ребро — получится $(n-2)+1=n-1$ ребро в исходном дереве. QED.
(Альтернативно: суммируя степени вершин, $\sum \mathrm{deg}(v)=2|E|$; в дереве есть не менее двух листьев, и индуктивный аргумент даёт $|E|=n-1$.)
Алгоритмы и структуры данных для динамической поддержи соединённости
1) Только добавления рёбер (инкрементальная задача)
- Структура: Disjoint Set Union (DSU, Union–Find).
- Поддерживает: MakeSet, Find(v), Union(u,v).
- Идея: родительский массив + объединение по рангу (или по размеру) + сжатие путей при Find.
- Сложность: амортизированная для каждой операции $\mathrm{O}(\alpha (n))$, где $\alpha$ — обратная функция Аккермана (на практике «почти константа»). Память: $\mathrm{O}(n)$.
Когда использовать: если рёбра только добавляются и нужно отвечать на запросы «соединены ли u и v?», DSU — лучший выбор.
2) Динамические леса (операции link и cut: добавление/удаление ребра так, чтобы граф всегда оставался лесом)
- Структуры: Euler Tour Trees (ET-trees) на сбалансированных BST (treap, RB-tree) или Link–Cut Trees (Splay-based).
- Идея ET-trees: представляем обход по дереву (Euler tour) как последовательность посещений вершин и храним её в сбалансированном дереве; соединение деревьев — конкатенация, разрез — сплит. Link–Cut: разбиение дерева на preferred paths, храним их в сбопльных splay-деревьях; поддерживает и дополнительные операции над путями.
- Поддерживаемые операции: link(u,v), cut(u,v), connected(u,v) (и при необходимости запросы по пути/поддереву).
- Сложность: каждое обновление и запрос — $\mathrm{O}(\log n)$ (в худшем или амортизированно, в зависимости от реализации); память $\mathrm{O}(n)$.
- Когда использовать: если граф всегда является лесом (или вы поддерживаете остовные леса внутри общего графа), и нужны как добавления, так и удаления рёбер.
3) Полностью динамическая связность в общем графе (рёбра могут добавляться и удаляться произвольно)
- Более сложные алгоритмы: Holm–de Lichtenberg–Thorup (HDT) — детерминистический алгоритм, а также рандомизированные варианты (Henzinger–King и др.).
- Идея HDT: поддерживать уровни остовных лесов (специальные динамические леса), при удалении не-бриджевого ребра быстро, при удалении мостового — искать замену на более низких уровнях; используют ET-trees/Link–Cut внутри уровней.
- Сложность (классический результат): обновление — амортизированное $\mathrm{O}({\log }^{2}n)$ на операцию, запрос connected — $\mathrm{O}(\log n)$. Существуют рандомизированные алгоритмы с ожидаемой полилогарифмической сложностью, некоторые достигают примерно $\mathrm{O}(\log n)$ ожидаемой на обновление.
- Когда использовать: нужна поддержка произвольных удалений/добавлений в общем графе; структура сложнее в реализации, но даёт полилогарифмическую стоимость.
Краткая сводка по выбору
- Только добавления: DSU, амортизированно $\mathrm{O}(\alpha (n))$.
- Динамические леса (link/cut): ET-trees или Link–Cut, $\mathrm{O}(\log n)$ на операцию.
- Полностью динамичный общий граф: HDT (детерм.) $\mathrm{O}({\log }^{2}n)$ амортизированно на обновление (запросы $\mathrm{O}(\log n)$); есть рандомизированные варианты с лучшими ожидаемыми гарантиями.
Короткие практические замечания
- Для большинства задач на потоковых добавлениях DSU — простой и быстрый выбор.
- Если нужны удаления, но граф поддерживается как лес/остов — используйте ET-trees или Link–Cut.
- Для произвольной динамики в большом проекте берут готовые реализации HDT или рандомизированные структуры; реализация непростая, и часто предпочитают эвристики/амортизированные подходы в зависимости от входных данных.