Минимальный разрез в графе

Теорема Форда-Фалкерсона 1 (о максимальном потоке и минимальном разрезе).

В любой сети существует максимальный поток. Величина максимального потока равна пропускной способности минимального разреза.

Теорема Форда-Фалкерсона 2.

Поток, вычисленный с помощью алгоритма Форда-Фалкерсона имеет максимальную величину, а разрез , где -множество вершин, помеченных при последнем помечивании, имеет минимальную пропускную способность.

Нахождение максимального потока и построение минимального разреза в сети с использованием алгоритма Форда-Фалкерсона

В данной задаче основным параметром на дугах сети является пропускная способность. Пропускная способность показывает, сколько единиц потока может быть передано по дугам сети. Таким образом, потоком в сетиD = [N, M] называется неотрицательная вещественная функция, удовлетворяющая условиям:

1. ограниченности: поток по любой дуге сети не превосходит пропускной способности этой дуги ;

2. сохранения: суммарный поток, заходящий в любую вершину сети (кроме истока и стока), равен суммарному потоку, выходящему из этой вершины.

Дуга сети называется насыщенной, если поток по этой дуге равен пропускной способности этой дуги, т. е. .

Разрезом сетиназывается множество дуг, удаление которых из сети приводит к тому, что исток и сток оказываются несвязанными.

Пропускной способностью разрезаназывается число, равное сумме пропускных способностей дуг этого разреза. Разрез называется минимальным, если имеет наименьшую пропускную способность.

Отыскание минимального разреза – одна из основных задач анализа транспортных сетей. В силу конечности графа минимальный разрез может быть найден перебором всех разрезов, но этот путь, конечно, неприемлем для достаточно больших графов.

Минимальный разрез можно отыскать при помощи теоремы Форда – Фалкерсона: в любой транспортной сети величина любого максимального потокаравна пропускной способности любого минимального разреза.

Для нахождения максимального потока в сети разработан алгоритм Форда – Фалкерсона. Перед началом выполнения алгоритма все вершины сети нумеруются произвольным образом, кроме источника и стока (источник получает минимальный номер 1, сток – максимальный , где – число узлов).

Алгоритм состоит из следующих основных шагов:

1. Определить начальный поток в сети, сложив потоки по дугам, выходящим из источника.

2. Вершинам сети присвоить целочисленные метки, а дугам – знаки «+» и «–» по следующим правилам:

а) вершине-истоку присвоить метку ;

б) находим непомеченнуювершину , смежную помеченнойвершине . Если поток по соединяющей вершины дуге меньше пропускной способности этой дуги, то происходит помечивание, иначе переходим к рассмотрению следующей вершины. Если вершина является образомпомеченной вершины , то происходит прямое помечивание (дуга в прямом направлении допустима): вершина получает метку, равную номеру вершины , соединяющая вершины дуга получает метку «+», переходим к рассмотрению следующей вершины. Если вершина не имеет ни одного помеченного прообраза, поток по дуге в прямом направлении больше 0, то происходит обратное помечивание (дуга допустима в обратном направлении): вершина получает метку, равную номеру вершины (являющейся в данном случае ее образом), соединяющая вершины дуга получает метку «–», происходит переход к рассмотрению следующей вершины. Процесс помечивания продолжается до тех пор, пока все удовлетворяющие этим условиям вершины не получат метку.

3. Если в результате процедуры помечивания вершина-сток метки не получила, то текущий поток – максимальный, переход к шагу 5. В противном случае перейти к пункту 4.

4. Рассмотреть последовательность вершин L, метка каждой из которых равна номеру следующей за ней вершины, и множество дуг МL, соединяющих соседние вершины из L.

Построение нового потока по схеме:

а) Если дуга принадлежит множеству МL (смотри выше) и имеет знак «+», то новый поток по этой дуге = старый поток по этой дуге + Δ (схему нахождения смотри далее).

б) Если дуга принадлежит множеству МL и имеет знак «–», то новый поток по этой дуге = старый поток по этой дуге Δ.

в) Если дуга не принадлежит множеству МL, то поток по дуге оставляем без изменения.

Схема нахождения Δ:

I. , где для нахождения рассматриваются все дуги, принадлежащие множеству МL и имеющие знак «+», и для каждой такой дуги вычисляется разность между пропускной способностью дуги и потоком по этой дуге ( ). Затем из этих значений разностей выбирается минимальное значение и присваивается .

II. Для нахождения рассматриваются все дуги, принадлежащие множеству МL и имеющие знак «–». Затем из этих дуг выбирается дуга с минимальным потоком ( ), и значение потока по этой дуге присваивается .

Перейти к шагу 2.

5. Определяем максимальный поток, складывая начальный поток и все полученные изменения потока.

В оптимальном решении, т. е. когда найден максимальный поток, минимальный разрез образуется насыщенными дугами.

Дата добавления: 2019-02-22 ; просмотров: 509 ; ЗАКАЗАТЬ РАБОТУ

Алгоритм Каргера (англ. Karger’s algorithm) — рандомизированный алгоритм для нахождения минимального разреза в связном графе. Он был разработан Дэвидом Каргером (англ. David Karger) в 1993 году.

Содержание

Основные определения [ править ]

Пусть [math]G[/math] — неориентированный мультиграф с множеством вершин [math]V[/math] и множеством ребер [math]E[/math] , и [math]|V| = n[/math] , [math]|E| = m[/math] .

Определение:
Стягиванием (англ. contraction) ребра [math]uv[/math] назовем следующую последовательность действий:

  1. Добавляем новую вершину [math]w[/math] .
  2. Для всех ребер [math]xu[/math] и [math]xv[/math] (где [math]x in V, x
    eq v, x
    eq u[/math] ) добавляем новые ребра [math]xw[/math] . При этом, если получаются кратные ребра — оставляем их.
  3. Удаляем вершины [math]u[/math] и [math]v[/math] и все инцидентные им ребра.
Определение:
Мультивершиной (англ. supervertex) называется вершина, полученная из двух вершин стягиванием ребра между ними, каждая из которых, в свою очередь, может быть также мультивершиной.
Определение:
Стянутым графом (англ. contracted graph) называется граф, состоящий из двух мультивершин или одной мультивершины и одной обычной вершины (которую, чтобы избежать оговорок в дальнейшем, также будем называть мультивершиной), полученный из исходного графа последовательным стягиванием произвольных ребер.
Определение:
Разрезом (англ. cut) [math]langle A, B
angle[/math] называется разбиение множества [math]V[/math] на два множества [math]A[/math] и [math]B[/math] , удовлетворяющее следующим условиям:

  • [math]A, B subset V[/math] ,
  • [math]A, B
    eq emptyset[/math] ,
  • [math]A cap B = emptyset[/math] ,
  • [math]A cup B = V[/math] .

Такой разрез часто называют также глобальным разрезом, чтобы отличать его от [math](s,t)[/math] -разреза.

Определение:
Вес разреза [math]langle A, B
angle[/math] обозначается [math]w(A, B)[/math] и вычисляется по формуле:

  • для взвешенного графа — [math]w(A, B) =[/math] [math]sumlimits_ w(uv)[/math] ;
  • для невзвешенного графа — [math]w(A, B) = ||[/math] .

Задача поиска разреза минимальной веса (англ. min-cut problem) заключается в поиске разреза минимального веса среди всех возможных разрезов исходного графа. Эту задачу можно решить с помощью любого из алгоритмов поиска максимального потока, зафиксировав произвольную вершину [math]s[/math] в качестве истока и запуская его [math]O(n)[/math] раз для всех возможных стоков. Если использовать быстрый алгоритм поиска максимального потока, работающий за [math]O(mn)[/math] , то время работы такого алгоритма поиска минимального разреза будет [math]O(n^2m)[/math] . Ниже описан более простой в реализации и сравнимый по скорости алгоритм Каргера. При некоторых оптимизациях, этот алгоритм работает значительно быстрее, чем использование алгоритмов поиска максимального потока.

Алгоритм [ править ]

Пусть нам дан граф [math]G = [/math] .

Так как алгоритм вероятностный и функция [math]mathrm[/math] возвращает вес случайного потока, а не минимального, то для того, чтобы наверняка найти вес минимального, необходим вызвать эту функцию [math]count[/math] раз. Какое конкретное значение [math]count[/math] выбрать будет описано ниже. Реализация функции [math]mathrm[/math] — это и есть основа алгоритма. Будем действовать следующим образом: пока вершин больше двух, будем выбирать случайное ребро и стягивать его. Когда в графе останется две вершины, то количество ребер между этими вершинами будет равно весу некоторого разреза исходного графа.

Корректность алгоритма [ править ]

Докажем корректность алгоритма. Для удобства доказательства и оценок вероятностей, будем считать, что мы ищем не просто вес минимального разреза, а величину конкретного минимального разреза. То есть зафиксируем какой-то один из минимальных разрезов, и если функция [math]mathrm[/math] вернет правильный вес, но посчитает его на другом минимальном разрезе, то будем считать, что ответ получен неверный. Это условие не ухудшает оценки вероятностей и время работы алгоритма.

Лемма (1):
Пусть [math]w[/math] — некоторая мультивершина, [math]u[/math] и [math]v[/math] — какие-то две из вершин, которые были стянуты в вершину [math]w[/math] . Тогда существует такой путь [math]p[/math] в исходном графе [math]G[/math] между вершинами [math]u[/math] и [math]v[/math] , что ко всем ребрам этого пути была применена операция стягивания.
Доказательство:
[math] riangleright[/math]
Рассмотрим подграф [math]G'[/math] исходного графа [math]G[/math] в который входят все ребра, которые были стянуты в вершину [math]w[/math] . Очевидно, что [math]G'[/math] связен, а значит в нем существует путь между его любыми двумя вершинами. Следовательно, существует путь между [math]u[/math] и [math]v[/math] , состоящий из стянутых ребер. Лемма доказана.
[math] riangleleft[/math]
Лемма (2):
Если стянуть некоторое ребро [math]e = uv[/math] в графе G, то вес минимального разреза в графе [math]G’ = Gsetminus e[/math] будет не меньше чем вес минимального разреза в исходном графе [math]G[/math] .
Доказательство:
[math] riangleright[/math]
Составим биекцию между ребрами графов [math]G[/math] и [math]G'[/math] , не рассматривая ребра между вершинами [math]u[/math] и [math]v[/math] в графе [math]G[/math] . Очевидно, что это возможно, исходя из следующих соображений. Все ребра в [math]G[/math] , не инцидентные вершинам [math]u[/math] и [math]v[/math] , остались без изменений, а всем ребрам, инцидентным этим вершинам, по определению стягивания можно сопоставить новое ребро в [math]G'[/math] . Пусть [math]langle A’, B’
angle[/math] — минимальный разрез в графе [math]G'[/math] , и, не уменьшая общности, [math]w in A'[/math] . Рассмотрим разрез [math]langle A, B’
angle[/math] в графе [math]G[/math] . Исходя из биекции между ребрами и тем, что все ребра вида [math]uv[/math] не пересекают разрез (так как [math]u in A, v in A[/math] ), то [math]w(A’, B’) = w(A, B’)[/math] . Тогда если разрез [math]langle A, B’
angle[/math] в графе [math]G[/math] — минимален, вес минимального разреза в [math]G'[/math] совпадает с весом минимального размера в [math]G[/math] . Если в [math]G[/math] существует разрез меньшего веса, то вес минимального разреза в [math]G'[/math] больше чем в [math]G[/math] . Лемма доказана.
[math] riangleleft[/math]
Лемма (3):
Пусть [math]c[/math] — вес минимального потока в графе [math]G[/math] . Тогда [math]m geqslant nc/2[/math] .
Доказательство:
[math] riangleright[/math]
Заметим, что, чтобы выполнялось условие, степень каждой вершины должна быть не менее, чем [math]c[/math] . Действительно, пусть [math]deg(v) lt c[/math] для некоторой вершины [math]v in V[/math] . Тогда [math]w(v, G setminus v) = deg(v) lt c[/math] , что противоречит условию. Далее, по лемме о рукопожатиях имеем, что [math]m geqslant nc/2[/math] . Лемма доказана.
[math] riangleleft[/math]
Лемма (4):
Функция [math]mathrm[/math] после своего выполнения получит стянутый граф [math]G'[/math] соответствующий конкретному разрезу [math]langle A, B
angle[/math] исходного графа [math]G[/math] тогда и только тогда, когда ни одно ребро, принадлежащее разрезу [math]langle A, B
angle[/math] , не будет стянуто.
Доказательство:
[math] riangleright[/math]

Необходимость. От противного. Если некоторое ребро [math]uv[/math] , принадлежащее разрезу [math]langle A, B
angle[/math] в [math]G[/math] будет стянуто, то обе вершины [math]u[/math] и [math]v[/math] будут принадлежать одной мультивершине, а значит [math]G'[/math] не соответствует разрезу [math]langle A, B
angle[/math] . Противоречие.

Достаточность. Пусть ни одно ребро, принадлежащее разрезу [math]langle A, B
angle[/math] не было стянуто. Рассмотрим произвольную пару вершин [math]u in A[/math] и [math]v in B[/math] в графе [math]G[/math] . Если алгоритм стянул [math]u[/math] и [math]v[/math] в одну мультивершину в [math]G'[/math] , тогда по лемме 1 существует путь [math]p[/math] между вершинами [math]u[/math] и [math]v[/math] , и все ребра этого пути были стянуты. Но [math]p[/math] пересекает разрез [math]langle A, B
angle[/math] , что противоречит предположению, что ни одно ребро не было стянуто. Значит, вершины из любой пары [math]u in A[/math] , и [math]v in B[/math] были стянуты в разные мультивершины. А так, как стянутый граф состоит только из двух мультивершин, значит одна из них была получена стягиванием всех вершин из [math]A[/math] , а другая — из [math]B[/math] . Лемма доказана.

[math] riangleleft[/math]
Теорема:
Доказательство: [math] riangleright[/math]

По лемме 4 искомый стянутый граф будет получен тогда и только тогда, когда ни одно из ребер разреза не будет стянуто. Так как на каждой итерации алгоритма мы случайно выбираем ребро для стягивания, то можно оценить вероятность того, что ни одно из ребер разреза не будет стянуто. Каждое стягивание уменьшает количество ребер на [math]1[/math] . Таким образом после [math]i[/math] -ой итерации алгоритма количество вершин в текущем графе будет равно [math]n — i + 1[/math] . Рассчитаем вероятность того, что на [math]i[/math] -ой итерации будет стянуто ребро из разреза [math]langle A, B
angle[/math] . Пусть [math]w = w(A, B)[/math] . По лемме 2 величина минимального потока в текущем графе будет не меньше, чем [math]w[/math] , и в нем будет не менее [math]frac<2>[/math] вершин по лемме 3. Тогда вероятность того, что будет стянуто ребро из разреза [math]langle A, B
angle[/math] , при условии, что до этого не было стянуто ни одно из ребер разреза, будет не более

Обозначим за [math]xi_i[/math] событие, что на [math]i[/math] -ой итерации случайным образом будет выбрано ребро из разреза [math]langle A, B
angle[/math] . Тогда мы только что установили, что

[math]p(xi_i | overline <xi_1>wedge ldots wedge overline<xi_>) leqslant frac<2>.[/math]

[math]p(overline <xi_i>| overline <xi_1>wedge ldots wedge overline<xi_>) = 1 — p(xi_i | overline <xi_1>wedge ldots wedge overline<xi_>) geqslant 1 — frac<2> = frac.[/math]

Тогда вероятность того, что во время работы функции не будет стянуто ни одно ребро оценивается следующим образом:

[math]p(overline <xi_1>wedge ldots wedge overline<xi_>) = prodlimits_^ p(overline <xi_i>| overline <xi_1>wedge ldots wedge overline<xi_>) geqslant [/math]

[math]geqslant prodlimits_^ frac = frac cdot frac cdot frac cdot ldots cdot frac<2> <4>cdot frac<1> <3>= frac<2> geqslant frac<2>.[/math]

Теорема доказана.

[math] riangleleft[/math]

Таким образом, мы видим, что вероятность получить правильный ответ после единичного запуска функции [math]mathrm[/math] очень мала. Однако, вызвав эту функцию [math]count[/math] раз мы увеличим эту вероятность. Рассчитаем значение [math]count[/math] такое, чтобы вероятность успеха была близка к [math]1[/math] .

Для этого воспользуемся следующим неравенством:

[math] e^x geqslant 1 + x[/math] для любого вещественного [math]x[/math] .

Вероятность того, что мы не получим правильный ответ после [math]count[/math] независимых запусков равна

Пусть [math]count = n^2ln(n)[/math] . Тогда в силу указанного выше неравенства:

То есть, если вызвать функцию [math]mathrm[/math] [math]n^2ln(n)[/math] раз, и после каждой итерации запоминать минимум, то вероятность того, что найденный ответ будет неверен [math] leqslant frac<1>[/math] . Даже при небольших значениях [math]n[/math] алгоритм практически гарантированно выдает правильный ответ.

Оценка времени работы алгоритма [ править ]

Время работы функции [math]mathrm[/math] — [math]O(n^2)[/math] . Функция работает [math]O(n^2log(n))[/math] раз. Итоговое время работы — [math]O(n^4 log(n))[/math] .

Оптимизация алгоритма [ править ]

Каргер совместно со Штейном (англ. Stein) придумали оптимизацию алгоритма Каргера, значительно ускоряющую время его работы. Новый алгоритм называется в честь обоих создателей — алгоритм Каргера-Штейна (англ. Karger-Stein algorithm). Его суть заключается в следуюшем. Заметим, что вероятность стягивания вершины, принадлежащей минимальному разрезу, в начале выполнения функции [math]mathrm[/math] довольна мала, в то время, как вероятность стянуть ребро, которое не следует стягивать, ближе к концу работы функции существенно возрастает. Тогда будем использовать следующую рекурсивную версию алгоритма:

  1. Запускаем функцию [math]mathrm[/math] и стягиваем ребра до тех пор, пока не останется [math]frac<sqrt<2>>[/math] вершин.
  2. Запускаем независимо эту же функцию для получившегося графа дважды и возвращаем минимальный из ответов.

Такая модификация алгоритма выдает правильный ответ с точностью, не менее [math]frac<1><log(n)>[/math] . Время работы функции [math]mathrm[/math] вычисляется рекурсивной функцией:

[math]T(n) = O(n^2) + 2 * T(n/sqrt<2>) = O(n^2log(n))[/math] .

Это медленнее, чем оригинальный алгоритм, однако вероятность нахождения разреза минимального веса экспоненциально выше. Достаточно запустить алгоритм [math]clog^2(n)[/math] раз, где [math]c[/math] — некоторая константа. Действительно, рассчитаем вероятность неправильного ответа также, как раньше:

Итоговое время работы — [math] O(n^2log(n)) cdot clog^2(n) = O(n^2log^3(n))[/math] .

В литературе данные задачи известны как Задача о кратчайшем пути и Задача о максимальном потоке.

В данном калькуляторе для определения наикратчайшего пути в сети применяется табличный метод. Также можно использовать этот калькулятор, где реализован алгоритм Дейкстры.

  • Решение онлайн
  • Видеоинструкция

[an error occurred while processing the directive]
Карта сайта