Алгоритмы C++
.pdf
— произведение элементов матрицы, индексы которых не повторяются и покрывают все номера от до 
. Таким образом, снова, как и в доказательстве теоремы Эдмондса, каждое ненулевое слагаемое этой суммы соответствует совершенному паросочетанию в графе, и наоборот.
Рёберная связность. Свойства и нахождение
Определение
Пусть дан граф G.
Рёберной связностью λ графа G называется наименьшее число рёбер, которое нужно удалить, чтобы граф перестал быть связным. Для несвязного графа рёберная связность равна нулю. Для графа с мостом рёберная связность равна единице.
Множество S рёбер разделяет вершины A и B, если при удалении этих рёбер из графа вершины A и B оказываются в разных компонентах связности.
Ясно, что рёберная связность графа равна минимуму наименьшего числа рёбер, разделяющих две вершины A и B, взятому среди всех пар (A,B).
Свойства
Соотношение Уитни (Whitney) (1932 г.) между рёберной связностью λ, вершинной связностью κ и наименьшей из степеней вершин δ:
κ <= λ <= δ
Теорема Форда-Фалкерсона (1956 г.). Для любых двух вершин наибольшее число рёбернонепересекающихся цепей, соединяющих их, равно наименьшему числу рёбер, разделяющих эти вершины.
На этой теореме и основано нахождение величины рёберной связности.
Нахождение рёберной связности
Итак, мы должны перебрать все пары вершин (A,B), и между каждой парой найти наибольшее число непересекающихся по рёбрам путей. А найти эту величину уже можно с помощью алгоритма максимального потока: мы делаем A истоком, B стоком, а пропускную способность каждого ребра положив равной 1.
Таким образом, псевдокод алгоритма таков:
int ans = INF;
for (int s=0; s<n; ++s)
for (int t=0; t<n; ++t) { int flow;
... находим величину flow максимального потока из s в t ...
ans = min (ans, flow);
}
Асимптотика алгоритма при использовании алгоритма Эдмондса-Карпа нахождения максимального потока получается
O (N2 N M2) = O (N3 M2), однако следует заметить, что скрытая в асимптотике константа весьма мала, поскольку практически невозможно создать такой граф, чтобы алгоритм нахождения максимального потока работал медленно сразу при всех стоках и истоках.
вершины раздваиваем (вершина I заменяется I1 и I2), причём все рёбра, ранее входившие в I, направляем в I1, а
все рёбра, выходившие из I, направляем из I2, кроме того, проводим ребро из I1 в I2; пропускную способность каждого ребра положив равной 1.
Таким образом, псевдокод алгоритма таков:
int ans = n-1;
строим модифицированный граф с раздвоенными вершинами for (int s=0; s<n; ++s)
for (int t=0; t<n; ++t) {
if (g[s][t]) continue; int flow;
... находим величину flow максимального потока из s2 в t1 ...
ans = min (ans, flow);
}
Асимптотика алгоритма при использовании алгоритма Эдмондса-Карпа нахождения максимального потока получается
O (N2 N M2) = O (N3 M2), однако следует заметить, что скрытая в асимптотике константа весьма мала, поскольку практически невозможно создать такой граф, чтобы алгоритм нахождения максимального потока работал медленно сразу при всех стоках и истоках.
Построение графа с указанными величинами вершинной и рёберной связностей и наименьшей из степеней вершин
Даны величины κ, λ, δ - вершинная связность ("каппа"), рёберная связность ("лямбда") и наименьшая из степеней вершин графа ("дельта"). Требуется построить граф, который бы обладал указанными значениями, или сказать, что такого графа не существует.
(см. "вершинная связность", "рёберная связность")
Решение
Заметим, что всегда выполняется условие:
κ <= λ <= δ
Это соотношение было найдено Уитни (Whitney) в 1932 году (впрочем, эти соотношения можно легко доказать эвристически)
Менее очевидный факт - что если κ, λ и δ удовлетворяют этому соотношению, то граф, обладающий этими значениями, обязательно существует. Таким образом, мы решили первую часть задачи - ответили на вопрос о существовании ответа.
Теперь построим сам граф. Граф будет состоять из 2(δ+1) вершин, причём первые (δ+1) вершины образуют полносвязный подграф, и вторые (δ+1) вершины также образуют полносвязный подграф. Кроме того, соединим эти две части λ рёбрами так, чтобы в первой части эти рёбра были смежны λ вершинам, а в другой части - κ вершинам. Очевидно, полученный граф будет обладать необходимыми свойствами.
Нахождение K-го кратчайшего пути без циклов с помощью бинарного поиска
Дан взвешенный граф (ориентированный или неориентированный) с N вершинами, M рёбрами, любой путь в котором имеет длину не более W, а каждое ребро имеет неотрицательный вес. Кратные рёбра допускаются. Также дано число K, и указаны две вершины S и T. Требуется найти K-ый в порядке сортировки простой путь (т.е.
без повторяющихся вершин), соединяющий вершины S и T.
Наиболее популярный алгоритм решения этой задачи - это алгоритм Йена, однако его асимптотика - O (N M K). Здесь же мы рассмотрим алгоритм, который и идейно значительно проще, и асимптотически быстрее (в большинстве случаев)
- за O (N2 K log W).
Алгоритм
Научимся для заданной верхней границы MaxLen проверять за O (N2 K), есть ли K простых путей из S в T длины не более MaxLen. Однако это можно сделать достаточно просто - фактически с помощью перебора с отсечениями. Запустим перебор из вершины S, который будет искать всевозможные простые пути в вершину T длины не более MaxLen. Ясно, что чтобы перебор был эффективным, если текущая длина пути уже больше MaxLen, то из этой ветви перебора надо сразу выходить (здесь используется то, что рёбер с отрицательными весами нет). Если в какой-то момент мы найдём K путей, то мы уже можем останавливать перебор - ответ найден, как минимум K различных простых путей существуют. Последнее отсечение, которое надо добавить в перебор - чтобы он не заходил в тупики, т.е. в такие вершины, из которых он уже никогда не достигнет T. Математически это отсечение имеет вид: CurLen + Dist(V,T) <= MaxLen, где CurLen - текущая длина пути, Dist(A,B) - это расстояние между вершинами A и B,
которое можно предвычислить алгоритмом Дейкстры (можно простейшим вариантом за O (N2 + M), всё равно это асимптотику не ухудшит).
Поймём, почему асимптотика этого перебора получится O (N2 K). Действительно, поскольку все пути простые, то длина каждого найденного пути есть O (N). Далее, поскольку алгоритм не заходит в тупики, то любая его
ветвь завершается нахождением ещё одного пути из S в T, но путей будет найдено не более K. Наконец, каждый раз, находясь в какой-либо вершине, перебор выполняет O (N) действий. Итого мы получаем асимптотику O (N2 K).
Теперь применим этот алгоритм перебора к нашей задаче с помощью бинарного поиска. Подбирать бинарным поиском мы, очевидно, будет величину MaxLen - ограничение на длину пути. Мы хотим найти минимальную величину MaxLen, при которой в графе ещё есть как минимум K путей из S в T длины не более
MaxLen. После окончания бинарного поиска мы можем восстановить и сам путь с помощью всё того же перебора (теперь мы уже знаем длину пути - MaxLen, - и хотим найти любой путь этой длины).
Поскольку MaxLen может изменяться только от 0 до W, то бинарный поиск в целом отработает за O (N2 K log W), восстановление пути (если он, конечно, существует) - за O (N2 K), итого асимптотика O (N2 K log W).
Реализация
const int INF = 1000*1000*1000;
const int W = ...; // максимальная длина пути
int n, s, t;
vector < vector < pair<int,int> > > g; vector<int> dist;
vector<char> used; vector<int> curpath, kth_path;
int kth_path_exists (int k, int maxlen, int v, int curlen = 0) { curpath.push_back (v);
if (v == t) {
if (curlen == maxlen) kth_path = curpath;
curpath.pop_back(); return 1;
}
used[v] = true; int found = 0;
for (size_t i=0; i<g[v].size(); ++i) {
int to = g[v][i].first, len = g[v][i].second;
if (!used[to] && curlen + len + dist[to] <= maxlen) { found += kth_path_exists (k - found, maxlen, to,
curlen + len);
if (found == k) break;
}
}
used[v] = false; curpath.pop_back(); return found;
}
int main() {
... чтение входных данных (n, k, g, s, t) ...
dist.assign |
(n, |
INF); |
|
dist[t] = 0; |
(n, |
false); |
|
used.assign |
|||
for (;;) { |
sel |
= -1; |
|
int |
|||
for |
(int i=0; i<n; ++i) |
||
[i] < dist[sel])) |
|
if (!used[i] && dist[i] < INF && (sel == -1 || dist |
|
|
sel = i; |
||
if (sel |
|||
== -1) break; |
|||
used[sel] = true; |
|||
for |
(size_t i=0; i<g[sel].size(); ++i) { |
||
|
|
int to = g[sel][i].first, len = g[sel][i].second; |
|
|
|
dist[to] = min (dist[to], dist[sel] + len); |
|
}
}
int minw = 0, maxw = W; while (minw < maxw) {
int wlimit = (minw + maxw) >> 1; used.assign (n, false);
if (kth_path_exists (k, wlimit, s) == k) maxw = wlimit;
else
minw = wlimit + 1;
}
used.assign (n, false);
if (kth_path_exists (k, minw, s) < k) puts ("NO SOLUTION");
else {
cout << minw << ' ' << kth_path.size() << endl; for (size_t i=0; i<kth_path.size(); ++i)
cout << kth_path[i]+1 << ' ';
}
}