Изменения
Нет описания правки
Идея алгоритма довольно проста. Будем <tex>n-1</tex> раз повторять следующий процесс: находить минимальный разрез между какой-нибудь парой вершин <tex>s</tex> и <tex>t</tex>, а затем объединять эти две вершины в одну (создавать новую вершину, список смежности которой равен объединению списков смежности <tex>s</tex> и <tex>t</tex>). В конце концов, после <tex>n-1</tex> итерации, останется одна вершина. После этого ответом будет являться минимальный среди всех <tex>n-1</tex> найденных разрезов. Действительно, на каждой <tex>i</tex>-ой стадии найденный минимальный разрез <tex>\langle A,B \rangle</tex> между вершинами <tex>s_i</tex> и <tex>t_i</tex> либо окажется искомым глобальным минимальным разрезом, либо же, напротив, вершины <tex>s_i</tex> и <tex>t_i</tex> невыгодно относить к разным множествам, поэтому мы ничего не ухудшаем, объединяя эти две вершины в одну.
Следовательно нам необходимо для данного графа найти минимальный разрез между какой-нибудь парой вершин <tex>s</tex> и <tex>t</tex>. Для этого вводим некоторое множество вершин <tex>A</tex>, которое изначально содержит единственную произвольную вершину <tex>s</tex>. На каждом шаге находится вершина, наиболее сильно связанная с множеством <tex>A</tex>, т.е. вершина <tex>v \not\in A</tex>, для которой следующая величина <tex dpi = "140">w(v,A) = \sum\limits_{(v,u) \in E, \atop u \in A} w(v,u)</tex> максимальна (максимальна сумма весов рёбер, один конец которых <tex>v</tex>, а другой принадлежит <tex>A</tex>).Этот процесс завершится, когда все вершины перейдут в множество <tex>A</tex>. minCut(): v[i] - список вершин, которые были сжаты в i-тую(сначала заполняется i); for i = 1..n-1 обнуляем мн-во A; обнуляем w(связности всех вершин); for j = 1..n-1 s = вершина не из A, для которой w[s] - максимальна; if (j != n-1) добавляем s в A; пересчитываем связность w[i] для остальных вершин; prev = s; else if (w[s] < minCost) minCost = w[s]; minCut = v[s]; s и prev объединяются в одну вершину; == Корректность алгоритма =={{Теорема|statement=Если добавить в множество <tex>A</tex> по очереди все вершины, каждый раз добавляя вершину, наиболее сильно связанную с <tex>A</tex>, то пусть предпоследняя добавленная вершина {{---}} <tex>s</tex>, а последняя {{---}} <tex>t</tex>. Тогда минимальный <tex>s</tex>-<tex>t</tex> разрез состоит из единственной вершины {{---}} <tex>t</tex>|proof=Рассмотрим произвольный <tex>s</tex>-<tex>t</tex> разрез <tex>C</tex> и покажем, что его вес не может быть меньше веса разреза, состоящего из единственной вершины <tex>t</tex>: <tex dpi = '130'>w(\{t\}) \le w(C)</tex>. }}
