Формулировка задачи
- Дано ориентированный взвешенный граф $(V,E)$, функция весов $w:E\to \mathbb{R}$ и фиксированный источник (корень) $r\in V$.
- Требуется найти подмножество рёбер $A\subseteq E$ такое, что в ориентированном графе $(V,A)$ из корня $r$ достижимы все вершины, и суммарный вес ${\sum }_{e\in A}w(e)$ минимален.
- Эквивалентное формальное требование: найти минимальную по сумме весов ориентированную остовную арборесценцию (directed spanning arborescence) корня $r$ — то есть такое подмножество $A$, что
$$\forall v\in V\setminus \{r\}:inde{g}_A(v)=1,inde{g}_A(r)=0,$$ и $(V,A)$ ацикличен (тогда из $r$ есть путь в любую вершину). Цель: минимизировать $w(A)={\sum }_{e\in A}w(e)$.
Связь с задачей о минимальной арборесценции (Edmonds / Chu–Liu)
- Это именно задача минимальной (корневой) арборесценции. Алгоритм Chu–Liu/Edmonds даёт полиномиальное решение: выбирает для каждой вершины минимальное входящее ребро, обнаруживает и сворачивает циклы, корректирует веса и рекурсивно решает задачу на сжатом графе, затем разворачивает циклы, восстанавливая решение.
Алгоритм (Chu–Liu/Edmonds), суть и формулы
1. Для каждой вершины $v\ne r$ выбираем входящее ребро с минимальным весом:
$$e_v=\arg \underset{(u\to v)\in E}{\min }w(u\to v).$$ Если такие выбранные ребра образуют ацикличный граф, то набор $\{e_v{\}}_{v\ne r}$ — искомая минимальная арборесценция.
2. Если выбранные ребра содержат цикл(ы), то возьмём любой цикл $C$. Свернём вершины цикла в одну супер-вершину $c$. Построим сжатый граф $G^{\prime }$ так:
- Для ребра $(x\to y)$ с $x\notin C,y\notin C$ сохраняем без изменений.
- Для ребра $(x\to y)$ с $x\notin C,y\in C$ вводим ребро $(x\to c)$ с весом
$$w^{\prime }(x\to c)=w(x\to y)-w(e_y),$$ где $e_y$ — выбранное минимальное входящее ребро в $y$ на шаге 1.
- Для ребра $(x\to y)$ с $x\in C,y\notin C$ вводим ребро $(c\to y)$ с весом
$$w^{\prime }(c\to y)=\underset{x\in C}{\min }w(x\to y),$$ сохраняя информацию, от какой конкретной вершины исходило это минимальное ребро (нужно при восстановлении).
- Рёбра внутри $C$ удаляются (их роль учтена через $w(e_y)$ в корректировке входящих весов).
3. Рекурсивно находим минимальную арборесценцию в $G^{\prime }$. Это даёт множество рёбер в сжатом графе, в том числе, возможно, входящее в $c$ ребро $(x\to c)$ (или нет, если $c=r$).
4. Разворачиваем $C$: если в найденном решении в $G^{\prime }$ входящее ребро в $c$ соответствует исходному ребру $(x\to y)$ в $G$ (с $y\in C$), то в цикле $C$ мы удаляем выбранное ранее входящее ребро $e_y$ и оставляем остальные выбранные входящие рёбра цикла. Таким образом разрывается цикл и получаем дерево, корректно соединённое с внешней частью решения.
Корректность: уменьшение весов при свёртке гарантирует, что выбор входящего ребра в сжатом графе соответствует оптимальному варианту выбора того, в какую вершину цикла "пришло" внешнее соединение, и последующее развёртывание даёт глобально оптимальное решение.
Сложность: классическая реализация работает за $O(|V|\cdot |E|)$. Существуют более сложные реализации и оптимизации, улучшающие асимптотику (например, с использованием структур данных для быстрого поиска и сжатия).
Наглядный пример
Пусть $V=\{1,2,3,4\}$, корень $r=1$. Рёбра и веса:
$$1\to 2:3,1\to 3:2,2\to 3:1,3\to 2:1,2\to 4:4,3\to 4:2.$$
Шаг 1 — выбрать минимальные входящие для каждой вершины, кроме корня:
$$e_2=3\to 2(\text{вес}1),e_3=2\to 3(\text{вес}1),e_4=3\to 4(\text{вес}2).$$ Эти выбранные рёбра содержат цикл $C=\{2,3\}$ (рёбра $2\to 3$ и $3\to 2$).
Шаг 2 — свернём $C$ в вершину $c$. Рассчитаем веса входящих рёбер в $c$ из вершин вне $C$:
- Для $1\to 2$: $w^{\prime }(1\to c)=w(1\to 2)-w(e_2)=3-1=2.$ - Для $1\to 3$: $w^{\prime }(1\to c)=w(1\to 3)-w(e_3)=2-1=1.$ Выберем минимальный (со значением $1$), соответствующий исходному ребру $1\to 3$.
Ребра из $c$ наружу:
$$c\to 4:\min (w(2\to 4),w(3\to 4))=\min (4,2)=2$$ (исходило от $3\to 4$).
Сжатый граф: вершины $\{1,c,4\}$ с рёбрами $1\to c$ вес $1$, $c\to 4$ вес $2$.
Шаг 3 — в сжатом графе выбираем входящие: для $c$ — $1\to c$ (1), для $4$ — $c\to 4$ (2). Ациклично, решение найдено.
Шаг 4 — разворачивание цикла $C$. В сжатом решении входящее в $c$ ребро соответствовало $1\to 3$. Значит при разворачивании мы включаем $1\to 3$ и в цикле удаляем $e_3$ (это было $2\to 3$), оставляя $3\to 2$. В итоге берём рёбра:
$$1\to 3(2),3\to 2(1),3\to 4(2).$$ Суммарный вес $2+1+2=5$ — это минимальная арборесценция корня $1$.
Краткое резюме
- Задача — найти минимальную направленную остовную арборесценцию корня $r$.
- Алгоритм Edmonds (Chu–Liu) решает её полиномиально: выбирает минимальные входящие, сворачивает циклы с корректировкой весов, рекурсивно решает задачу на сжатом графе и затем разворачивает циклы.
- Основная формула при сжатии входящих рёбер: $w^{\prime }(x\to c)=w(x\to y)-w(e_y)$ для $y\in C$.