Алгоритмы C++
.pdfкоторая возвращает величину найденного максимального потока.
Алгоритм Куна нахождения наибольшего паросочетания в двудольном графе
Дан двудольный граф, содержащий N вершин и M рёбер. Требуется найти наибольшее паросочетание, т.е. выбрать
как можно больше рёбер, чтобы ни одно выбранное ребро не имело общей вершины ни с каким другим выбранным ребром.
Описание
Цепью длины k назовём некоторый простой путь (т.е. не содержащий повторяющихся вершин или рёбер), содержащий k рёбер. Чередующейся цепью (в двудольном графе, относительно некоторого паросочетания) назовём цепь,
в которой рёбра поочередно принадлежат/не принадлежат паросочетанию. Увеличивающей цепью (в двудольном графе, относительно некоторого паросочетания) назовём цепь, у которой начальная и конечная вершины не принадлежат паросочетанию.
Теорема Бержа. Паросочетание является максимальным тогда и только тогда, когда не существует увеличивающих относительно него цепей.
Далее, заметим, что если найдена некоторая увеличивающая цепь, то с её помощью легко увеличить мощность паросочетания на 1. Пройдём вдоль этой цепи, и каждое ребро поочерёдно будем добавлять/ удалять из паросочетания (т.е. первое ребро (которое по определению не принадлежит паросочетанию) добавим в паросочетание, второе удалим, третье добавим, и т.д.). Действительно, в результате этой операции мы
увеличим мощность паросочетания на 1 (для этого достаточно заметить, что длина увеличивающей цепи всегда нечётно, а корректность вышеописанного преобразования очевидна).
Таким образом, мы получили каркас алгоритма построения максимального паросочетания: искать в графе увеличивающие цепи, пока они существуют, и увеличивать паросочетание вдоль них.
Осталось детализировать способ нахождения увеличивающих цепей. Алгоритм Куна основан на поиске в глубину или в ширину, и выбирает каждый раз любую из найденных увеличивающих цепей. Стоит заметить, что есть и другие способы, например, в более эффективном алгоритме Хопкрофта-Карпа.
Поскольку каждая увеличивающая цепь будет найдена за O (N+M), а всего цепей понадобится найти не более N/2, то итоговая асимптотика алгоритма равна O (N2 + N M), т.е. O (N M).
Рассмотрим подробнее алгоритм поиска увеличивающей цепи (пусть, для определённости, это поиск в глубину). Поиск начинает идти из вершины первой доли. Из первой доли во вторую он ходит только по рёбрам, не
принадлежащим паросочетанию, а из второй доли в первую - наоборот, только по принадлежащим. С точки зрения реализации, поиск в глубину всегда находится в вершине первой доли, и он возвращает булево значение - найдена цепь или не найдена. Из текущей вершины V поиск в глубину пытается пойти по всем смежным рёбрам (кроме принадлежащего паросочетанию), и если он может пойти в вершину To второй доли, не
принадлежащей паросочетанию, то возвращает True и добавляет ребро (V,To) в паросочетание. Если же он
пытается пойти в вершину To, уже принадлежащую паросочетанию, то он вызывает себя из вершины Mt[To] (соседа To в паросочетании), и если цепь была найдена, то добавляет ребро (V, To) в паросочетание.
Реализация
Здесь N - число вершин в первой доле, K - во второй доле.
int n, k;
vector < vector<int> > g; vector<int> mt; vector<char> used;
bool kuhn (int v) {
if (used[v]) return false; used[v] = true;
for (size_t i=0; i<g[v].size(); ++i) { int to = g[v][i];
if (mt[to] == -1 || kuhn (mt[to])) { mt[to] = v;
return true;
}
}
return false;
}
int main() {
... чтение графа ...
mt.assign (k, -1);
for (int i=0; i<n; ++i) { used.assign (n, false); kuhn (i);
}
for (int i=0; i<k; ++i) if (mt[i] != -1)
printf ("%d %d\n", mt[i]+1, i+1);
}
Улучшенная реализация
Модифицируем алгоритм следующим образом. До основного цикла алгоритма найдём каким-нибудь простым алгоритмом произвольное паросочетание (каким-либо жадным алгоритмом), и лишь затем будем выполнять цикл с вызовами функции kuhn(), который будет улучшать это паросочетание. В результате алгоритм будет работать заметно быстрее на случайных графах - потому что в большинстве графов можно легко набрать паросочетание достаточно большого веса.
Например, можно просто перебрать все вершины первой доли, и для каждой из них найти произвольное ребро, которое можно добавить в паросочетание, и добавить его. Даже такая простая эвристика способна ускорить алгоритм Куна в несколько раз.
Следует обратить внимание на то, что основной цикл придётся немного модифицировать. Поскольку при вызове функции kuhn в основном цикле предполагается, что текущая вершина ещё не входит в паросочетание, то нужно добавить соответствующую проверку.
В реализации изменится только код в функции main():
int main() {
... чтение графа ...
mt.assign (k, -1); vector<char> used1 (n); for (int i=0; i<n; ++i)
for (size_t j=0; j<g[i].size(); ++j) if (mt[g[i][j]] == -1) {
mt[g[i][j]] = i; used1[i] = true; break;
}
for (int i=0; i<n; ++i) {
if (used1[i]) continue;
used.assign (n, false); kuhn (i);
}
for (int i=0; i<k; ++i) if (mt[i] != -1)
printf ("%d %d\n", mt[i]+1, i+1);
}
Другой хорошей эвристикой является следующая. На каждом шаге будет искать вершину наименьшей степени (но не изолированную), из неё выбирать любое (?) ребро и добавлять его в паросочетание, затем удаляя обе эти вершины со всеми инцидентными им рёбрами из графа. Такая жадность работает очень хорошо на случайных графах, даже в большинстве случаев строит максимальное паросочетание, однако на специально подобранном тесте она может найти паросочетание значительно меньшей величины, чем максимальное.
Проверка графа на двудольность и разбиение на две доли
Пусть дан неориентированный граф. Требуется проверить, является ли он двудольным, т.е. можно ли разделить его вершины на две доли так, чтобы не было рёбер, соединяющих две вершины одной доли. Если граф является двудольным, то вывести сами доли.
Решим эту задачу с помощью поиска в ширину за O (M).
Признак двудольности
Теорема. Граф является двудольным тогда и только тогда, когда все его простые циклы имеют чётную длину.
Впрочем, с практической точки зрения искать все простые циклы неудобно. Намного проще проверять граф на двудольность следующим алгоритмом:
Алгоритм
Произведём серию поисков в ширину. Т.е. будем запускать поиск в ширину из каждой непосещённой вершины. Ту вершину, из которой мы начинаем идти, мы помещаем в первую долю. В процессе поиска в ширину, если мы идём в какую-то новую вершину, то мы помещаем её в долю, отличную от доли текущей вершину. Если же мы пытаемся пройти по ребру в вершину, которая уже посещена, то мы проверяем, чтобы эта вершина и текущая вершина находились в разных долях. В противном случае граф двудольным не является.
По окончании работы алгоритма мы либо обнаружим, что граф не двудолен, либо найдём разбиение вершин графа на две доли.
Реализация
int n;
vector < vector<int> > g;
... чтение графа ...
vector<char> part (n, -1); bool ok = true;
vector<int> q (n);
for (int st=0; st<n; ++st)
if (part[st] == -1) { int h=0, t=0; q[t++] = st; part[st] = 0; while (h<t) {
int v = q[h++];
for (size_t i=0; i<g[v].size(); ++i) { int to = g[v][i];
if (part[to] == -1)
part[to] = !part[v], q[t++] = to;
else
ok &= part[to] != part[v];
}
}
}
puts (ok ? "YES" : "NO");
Напомним основные положения теории матроидов.
Матроид M - это упорядоченная пара (S,I), где S - некоторое множество, I - непустое семейство подмножеств множества S, которые удовлетворяют следующим условиям:
1.Множество S конечное.
2.Семейство I является наследственным, т.е. если какое-то множество принадлежит I, то все его подмножества также принадлежат I.
3.Структура M обладает свойством замены, т.е. если A I, и B I, и |A|<|B|, то найдётся такой элемент x A-B, что A x I.
Элементы семейства I называются независимыми подмножествами.
Матроид называется взвешенным, если для каждого элемента x S определён некоторый вес. Весом подмножества называется сумма весов его элементов.
Наконец, важнейшая теорема в теории взвешенных матроидов: чтобы получить оптимальный ответ, т.е. независимое подмножество с наибольшим весом, нужно действовать жадно: начиная с пустого подмножества, будем добавлять (если, конечно, текущий элемент можно добавить без нарушения независимости) все элементы по одному в порядке уменьшения (точнее, невозрастания) их весов:
отсортировать множество S по невозрастанию веса; ans = [];
foreach (x in S)
if (ans x I)
ans = ans x;
Утверждается, что по окончании этого процесса мы получим подмножество с наибольшим весом. Теперь докажем, что наша задача - не что иное, как взвешенный матроид.
Пусть S - множество всех вершин первой доли. Чтобы свести нашу задачу в двудольном графе к матроиду относительно вершин первой доли, поставим в соответствие каждому паросочетанию такое подмножество S, которое равно множеству насыщенных вершин первой доли. Можно также определить и обратное соответствие (из множества насыщенных вершин - в паросочетание), которое, хотя и не будет однозначным, однако вполне нас будет устраивать.
Тогда определим семейство I как семейство таких подмножеств множества S, для которых найдётся хотя бы одно соответствующее паросочетание.
Далее, для каждого элемента S, т.е. для каждой вершины первой доли, по условию определён некоторый вес. Причём вес подмножества, как нам и требуется в рамках теории матроидов, определяется как сумма весов элементов в нём.
Тогда задача о нахождении паросочетания наибольшего веса теперь переформулируется как задача нахождения независимого подмножества наибольшего веса.
Осталось проверить, что выполнены 3 вышеописанных условия, наложенных на матроид. Во-первых, очевидно, что S является конечным. Во-вторых, очевидно, что удаление ребра из паросочетания эквивалентно удалению вершины из множества насыщенных вершин, а потому свойство наследственности выполняется. В-третьих, как следует из корректности алгоритма Куна, если текущее паросочетание не максимально, то всегда найдётся такая вершина, которую можно будет насытить, не удаляя из множества насыщенных вершин другие вершины.
Итак, мы показали, что наша задача является взвешенным матроидом относительно множества насыщенных вершин первой доли, а потому к ней применим жадный алгоритм.
Осталось показать, что алгоритм Куна является этим жадным алгоритмом.
Однако это довольно очевидный факт. Алгоритм Куна на каждом шаге пытается насытить текущую вершину - либо просто проводя ребро в ненасыщенную вершину второй доли, либо находя удлиняющую цепь и чередуя паросочетание вдоль неё. И в том, и в другом случае никакие уже насыщенные вершины не перестают быть ненасыщенными, а ненасыщенные на предыдущих шагах вершины первой доли не насыщаются и на этом шаге. Таким образом, алгоритм Куна является жадным алгоритмом, строящим оптимальное независимое подмножества матроида, что и завершает наше доказательство.