MAXimal

добавлено: 10 Jun 2009 21:03
редактировано: 18 Oct 2011 19:15

Нахождение минимального разреза. Алгоритм Штор-Вагнера

Постановка задачи

Дан неориентированный взвешенный граф $G$ с $n$ вершинами и $m$ рёбрами. Разрезом $C$ называется некоторое подмножество вершин (фактически, разрез — разбиение вершин на два множества: принадлежащие $C$ и все остальные). Весом разреза называется сумма весов рёбер, проходящих через разрез, т.е. таких рёбер, ровно один конец которых принадлежит $C$ :

$w(C) = \sum_{(v,u) \in E, \atop u \in C, v \not\i[...]$

где через $E$ обозначено множество всех рёбер графа $G$ , а через $c(v,u)$ — вес ребра $(v,u)$ .

Требуется найти разрез минимального веса.

Иногда эту задачу называют "глобальным минимальным разрезом" — по контрасту с задачей, когда заданы вершины-сток и исток, и требуется найти минимальный разрез $C$ , содержащий сток и не содержащий исток. Глобальный минимальный разрез равен минимуму среди разрезов минимальной стоимости по всевозможным парам исток-сток.

Хотя эту задачу можно решить с помощью алгоритма нахождения максимального потока (запуская его $O(n^2)$ раз для всевозможных пар истока и стока), однако ниже описан гораздо более простой и быстрый алгоритм, предложенный Матильдой Штор (Mechthild Stoer) и Франком Вагнером (Frank Wagner) в 1994 г.

В общем случае допускаются петли и кратные рёбра, хотя, понятно, петли абсолютно никак не влияют на результат, а все кратные рёбра можно заменить одним ребром с их суммарным весом. Поэтому мы для простоты будем считать, что во входном графе петли и кратные рёбра отсутствуют.

Описание алгоритма

Базовая идея алгоритма очень проста. Будем итеративно повторять следующий процесс: находить минимальный разрез между какой-нибудь парой вершин $s$ и $t$ , а затем объединять эти две вершины в одну (соединяя списки смежности). В конце концов, после $n-1$ итерации, граф сожмётся в единственную вершину и процесс остановится. После этого ответом будет являться минимальный среди всех $n-1$ найденных разрезов. Действительно, на каждой $i$ -ой стадии найденный минимальный разрез $C_i$ между вершинами $s_i$ и $t_i$ либо окажется искомым глобальным минимальным разрезом, либо же, напротив, вершины $s_i$ и $t_i$ невыгодно относить к разным множествам, поэтому мы ничего не ухудшаем, объединяя эти две вершины в одну.

Таким образом, мы свели задачу к следующей: для данного графа найти минимальный разрез между какой-нибудь, произвольной, парой вершин $s$ и $t$ . Для решения этой задачи был предложен следующий, тоже итеративный процесс. Вводим некоторое множество вершин $A$ , которое изначально содержит единственную произвольную вершину. На каждом шаге находится вершина, наиболее сильно связанная с множеством $A$ , т.е. вершина $v \not\in A$ , для которой следующая величина максимальна:

$w(v,A) = \sum_{(v,u) \in E, \atop u \in A} c(v,u)[...]$

(т.е. максимальна сумма весов рёбер, один конец которых $v$ , а другой принадлежит $A$ ).

Опять же, этот процесс завершится через $n-1$ итерацию, когда все вершины перейдут в множество $A$ (кстати говоря, этот процесс очень напоминает алгоритм Прима). Тогда, как утверждает теорема Штор-Вагнера, если мы обозначим через $s$ и $t$ последние две добавленные в $A$ вершины, то минимальный разрез между вершинами $s$ и $t$ будет состоять из единственной вершины — $t$ . Доказательство этой теоремы будет приведено в следующем разделе (как это часто бывает, само по себе оно никак не способствует пониманию алгоритма).

Таким образом, общая схема алгоритма Штор-Вагнера такова. Алгоритм состоит из $n-1$ фазы. На каждой фазе множество $A$ сначала полагается состоящим из какой-либо вершины; подсчитываются стартовые веса вершин $w(v,A)$ . Затем происходит $n-1$ итерация, на каждой из которых выбирается вершина $u$ с наибольшим значением $w(v,A)$ и добавляется в множество $A$ , после чего пересчитываются значения $w$ для оставшихся вершин (для чего, очевидно, надо пройтись по всем рёбрам списка смежности выбранной вершины $u$ ). После выполнения всех итераций мы запоминаем в $s$ и $t$ номера последних двух добавленных вершин, а в качестве стоимости найденного минимального разреза между $s$ и $t$ можно взять значение $w(t,A \setminus t)$ . Затем надо сравнить найденный минимальный разрез с текущим ответом, если меньше, то обновить ответ. Перейти к следующей фазе.

Если не использовать никаких сложных структур данных, то самой критичной частью будет нахождение вершины с наибольшей величиной $w$ . Если производить это за $O(n)$ , то, учитывая, что всего фаз $n-1$ , и по $n-1$ итерации в каждой, итоговая асимптотика алгоритма получается $O(n^3)$ .

Если для нахождения вершины с наибольшей величиной $w$ использовать Фибоначчиевы кучи (которые позволяют увеличивать значение ключа за $O(1)$ в среднем и извлекать максимум за $O(\log n)$ в среднем), то все связанные с множеством $A$ операции на одной фазе выполнятся за $O(m + n \log n)$ . Итоговая асимптотика алгоритма в таком случае составит $O(n m + n^2 \log n)$ .

Доказательство теоремы Штор-Вагнера

Напомним условие этой теоремы. Если добавить в множество $A$ по очереди все вершины, каждый раз добавляя вершину, наиболее сильно связанную с этим множеством, то обозначим предпоследнюю добавленную вершину через $s$ , а последнюю — через $t$ . Тогда минимальный $s$ - $t$ разрез состоит из единственной вершины — $t$ .

Для доказательства рассмотрим произвольный $s$ - $t$ разрез $C$ и покажем, что его вес не может быть меньше веса разреза, состоящего из единственной вершины $t$ :

$w(\{t\}) \le w(C).$

Для этого докажем следующий факт. Пусть $A_v$ — состояние множества $A$ непосредственно перед добавлением вершины $v$ . Пусть $C_v$ — разрез множества $A_v \cup v$ , индуцированный разрезом $C$ (проще говоря, $C_v$ равно пересечению этих двух множеств вершин). Далее, вершина $v$ называется активной (по отношению к разрезу $C$ ), если вершина $v$ и предыдущая добавленная в $A$ вершина принадлежат разным частям разреза $C$ . Тогда, утверждается, для любой активной вершины $v$ выполняется неравенство:

$w(v,A_v) \le w(C_v).$

В частности, $t$ является активной вершиной (т.к. перед ним добавлялась вершина $s$ ), и при $v = t$ это неравенство превращается в утверждение теоремы:

$w(t,A_t) = w(\{t\}) \le w(C_t) = w(C).$

Итак, будем доказывать неравенство, для чего воспользуемся методом математической индукции.

Для первой активной вершины $v$ это неравенство верно (более того, оно обращается в равенство) — поскольку все вершины $A_v$ принадлежат одной части разреза, а $v$ — другой.

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

$w(u,A_u) \equiv w(u,A_v) + w(u,A_u \setminus A_v)[...]$

Во-первых, заметим, что:

$w(u,A_v) \le w(v,A_v),$

— это следует из того, что когда множество $A$ было равно $A_v$ , в него была добавлена именно вершина $v$ , а не $u$ , значит, она имела наибольшее значение $w$ .

Далее, поскольку $w(v,A_v) \le w(C_v)$ по предположению индукции, то получаем:

$w(u,A_v) \le w(C_v),$

откуда имеем:

$w(u,A_u) \le w(C_v) + w(u,A_u \setminus A_v).$

Теперь заметим, что вершина $u$ и все вершины $A_u \setminus A_v$ находятся в разных частях разреза $C$ , поэтому эта величина $w(u,A_u \setminus A_v)$ обозначает сумму весов рёбер, которые учтены в $w(C_u)$ , но ещё не были учтены в $w(C_v)$ , откуда получаем:

$w(u,A_u) \le w(C_v) + w(u,A_u \setminus A_v) \le [...]$

что и требовалось доказать.

Мы доказали соотношение $w(v,A_v) \le w(C_v)$ , а из него, как уже говорилось выше, следует и вся теорема.

Реализация

Для наиболее простой и ясной реализации (с асимптотикой $O(n^3)$ ) было выбрано представление графа в виде матрицы смежности. Ответ хранится в переменных $\rm best\_cost$ и $\rm best\_cut$ (искомые стоимость минимального разреза и сами вершины, содержащиеся в нём).

Для каждой вершины в массиве $\rm exist$ хранится, существует ли она, или она была объединена с какой-то другой вершиной. В списке ${\rm v}[i]$ для каждой сжатой вершины $i$ хранятся номера исходных вершин, которые были сжаты в эту вершину $i$ .

Алгоритм состоит из $n-1$ фазы (цикл по переменной $\rm ph$ ). На каждой фазе сначала все вершины находятся вне множества $A$ , для чего массив $\rm in\_a$ заполняется нулями, и связности $w$ всех вершин нулевые. На каждой из $n-{\rm ph}$ итерации находится вершина $\rm sel$ с наибольшей величиной $w$ . Если это итерация последняя, то ответ, если надо, обновляется, а предпоследняя $\rm prev$ и последняя $\rm sel$ выбранные вершины объединяются в одну. Если итерация не последняя, то $\rm sel$ добавляется в множество $A$ , после чего пересчитываются веса всех остальных вершин.

Следует заметить, что алгоритм в ходе своей работы "портит" граф $\rm g$ , поэтому, если он ещё понадобится позже, надо сохранять его копию перед вызовом функции.

const int MAXN = 500;
int n, g[MAXN][MAXN];
int best_cost = 1000000000;
vector<int> best_cut;
 
void mincut() {
	vector<int> v[MAXN];
	for (int i=0; i<n; ++i)
		v[i].assign (1, i);
	int w[MAXN];
	bool exist[MAXN], in_a[MAXN];
	memset (exist, true, sizeof exist);
	for (int ph=0; ph<n-1; ++ph) {
		memset (in_a, false, sizeof in_a);
		memset (w, 0, sizeof w);
		for (int it=0, prev; it<n-ph; ++it) {
			int sel = -1;
			for (int i=0; i<n; ++i)
				if (exist[i] && !in_a[i] && (sel == -1 || w[i] > w[sel]))
					sel = i;
			if (it == n-ph-1) {
				if (w[sel] < best_cost)
					best_cost = w[sel],  best_cut = v[sel];
				v[prev].insert (v[prev].end(), v[sel].begin(), v[sel].end());
				for (int i=0; i<n; ++i)
					g[prev][i] = g[i][prev] += g[sel][i];
				exist[sel] = false;
			}
			else {
				in_a[sel] = true;
				for (int i=0; i<n; ++i)
					w[i] += g[sel][i];
				prev = sel;
			}
		}
	}
}

Нахождение минимального разреза. Алгоритм Штор-Вагнера

Постановка задачи

Описание алгоритма

Доказательство теоремы Штор-Вагнера

Реализация

Литература