Изменения
Новая страница: «'''Алгоритм Каргера''' {{---}} рандомизированный алгоритм для нахождения минимального разре...»
'''Алгоритм Каргера''' {{---}} рандомизированный алгоритм для нахождения минимального разреза в связном графе. Он был разработан Дэвидом Каргером (англ. ''David Karger'') в 1993 году.
== Основные определения ==
Пусть <tex>G</tex> {{---}} неориентированный мультиграф с множеством вершин <tex>V</tex> и множеством ребер <tex>E</tex>, и <tex>|V| = n</tex>, <tex>|E| = m</tex>.
{{Определение
|definition=
'''Стягиванием''' (англ. ''contraction'') ребра <tex>uv</tex> называется следующая последовательность действий:
# Добавляем новую вершину <tex>w</tex>.
# Для всех ребер <tex>xu</tex> и <tex>xv</tex> (где <tex>x \in V, x \neq v, x \neq u</tex>) добавляем новые ребра <tex>xw</tex>. При этом, если получаются кратные ребра - оставляем их.
# Удаляем вершины <tex>u</tex> и <tex>v</tex> и все инцидентные им ребра.
}}
{{Определение
|definition=
'''Мультивершиной''' (англ. ''supervertex'') называется вершина, полученная из двух вершин стягиванием ребра между ними, каждая из которых, в свою очередь, может быть также мультивершиной.
}}
{{Определение
|definition=
'''Стянутым графом''' (англ. ''contracted graph'') называется граф, состоящий из двух мультивершин, полученный из исходного графа последовательным стягиванием произвольных ребер.
}}
{{Определение
|definition=
'''Разрезом''' (англ. ''cut'') <tex>\langle A, B \rangle</tex> называется разбиение множества <tex>V</tex> на два множества <tex>A</tex> и <tex>B</tex>, удовлетворяющее следующим условиям:
* <tex>A, B \subset V</tex>;
* <tex>A, B \neq \emptyset</tex>;
* <tex>A \cap B = \emptyset</tex>;
* <tex>A \cup B = V</tex>.
}}
Такой разрез часто называют также глобальным разрезом, чтобы отличать его от [[Разрез, лемма о потоке через разрез#Определение разреза|<tex>(s,t)</tex>-разреза]].
{{Определение
|definition=
'''Вес разреза''' <tex>\langle A, B \rangle</tex> обозначается <tex>w(A, B)</tex> и вычисляется по формуле:
* для взвешенного графа - <tex>w(A, B) =</tex> <tex dpi = "140">\sum\limits_{uv \in E, u \in A, v \in B} w(uv)</tex>;
* для невзвешенного графа - <tex>w(A, B) = |\{uv: u \in A, v \in B\}|</tex>.
}}
Задача поиска разреза минимальной веса (англ. ''min-cut problem'') заключается в поиске разреза минимального веса среди всех возможных разрезов исходного графа. Эту задачу можно решить с помощью любого из алгоритмов поиска максимального потока, зафиксировав произвольную вершину <tex>s</tex> в качестве истока и запуская его <tex>O(n)</tex> раз для всех возможных стоков. Если использовать быстрый алгоритм поиска максимального потока, работающий за <tex>O(mn)</tex>, то время работы такого алгоритма поиска минимального разреза будет <tex>O(n^2m)</tex>. Однако ниже описан существенно более простой в реализации и более быстрый алгоритм Каргера.
== Алгоритм ==
Пусть нам дан граф <tex>G = \{V, E\}</tex>.
minCut():
answer = INF;
for i = 1..c
curCut = getCut();
if curCut < answer
answer = curCut;
return answer;
Так как алгоритм вероятностный и функция <tex>getCut</tex> возвращает вес случайного потока, а не минимального, то для того, чтобы наверняка найти вес минимального, необходим вызвать эту функцию <tex>c</tex> раз. Какое конкретное значение <tex>c</tex> выбрать будет описано ниже.
Реализация функции <tex>getCut</tex> {{---}} это и есть основа алгоритма. Будем действовать следующим образом: пока вершин больше двух, будем выбирать случайное ребро и стягивать его. Когда в графе останется две вершины, то количество ребер между этими вершинами будет равно весу некоторого разреза исходного графа.
getCut():
n = количество вершин в G;
while n > 2
e = случайное ребро из G;
contract(e);
n--;
m = количество ребер в G;
return m;
== Корректность алгоритма ==
Докажем корректность алгоритма. Для удобства доказательства и оценок вероятностей, будем считать, что мы ищем не просто вес минимального разреза, а величину конкретного минимального разреза. То есть зафиксируем какой-то один из минимальных разрезов, и если функция <tex>getCut</tex> вернет правильный вес, но посчитает его на другом минимальном разрезе, то будем считать, что ответ получен неверный. Это условие не ухудшает оценки вероятностей и время работы алгоритма.
{{Лемма
|about = 1
|id = Лемма1
|statement = Пусть <tex>w</tex> {{---}} некоторая мультивершина, <tex>u</tex> и <tex>v</tex> - какие-то две из вершин, которые были стянуты в вершину <tex>w</tex>. Тогда существует такой путь <tex>p</tex> в исходном графе <tex>G</tex> между вершинами <tex>u</tex> и <tex>v</tex>, что ко всем ребрам этого пути была применена операция стягивания.
|proof =
Рассмотрим подграф <tex>G'</tex> исходного графа <tex>G</tex> в который входят все ребра, которые были стянуты в вершину <tex>w</tex>. Очевидно, что <tex>G'</tex> связен, а значит в нем существует путь между его любыми двумя вершина. Следовательно, существует путь между <tex>u</tex> и <tex>v</tex>, состоящий из стянутых ребер. Лемма доказана.
}}
{{Лемма
|about = 2
|id = Лемма2
|statement = Если стянуть некоторое ребро <tex>e = uv</tex> в графе G, то вес минимального разреза в графе <tex>G' = G\setminus e</tex> будет не меньше чем вес минимального разреза в исходном графе <tex>G</tex>.
|proof =
Составим биекцию между ребрами графов <tex>G</tex> и <tex>G'</tex>, не рассматривая ребра между вершинами <tex>u</tex> и <tex>v</tex> в графе <tex>G</tex>. Очевидно, что это возможно, исходя из следующих соображений. Все ребра в <tex>G</tex>, не инцидентные вершинам <tex>u</tex> и <tex>v</tex>, остались без изменений, а всем ребрам, инцидентным этим вершинам, по определению стягивания можно сопоставить новое ребро в <tex>G'</tex>. Пусть <tex>\langle A', B' \rangle</tex> {{---}} минимальный разрез в графе <tex>G'</tex>, и, не уменьшая общности, <tex>w \in A'</tex>. Рассмотрим разрез <tex>\langle A, B' \rangle</tex> в графе <tex>G</tex>. Исходя из биекции между ребрами и тем, что все ребра вида <tex>uv</tex> не пересекают разрез (так как <tex>u \in A, v \in A</tex>), то <tex>w(A', B') = w(A, B')</tex>. Тогда если разрез <tex>\langle A, B' \rangle</tex> в графе <tex>G</tex> {{---}} минимален, вес минимального разреза в <tex>G'</tex> совпадает с весом минимального размера в <tex>G</tex>. Если в <tex>G</tex> существует разрез меньшего веса, то вес минимального разреза в <tex>G'</tex> больше чем в <tex>G</tex>. Лемма доказана.
}}
{{Лемма
|about = 3
|id = Лемма3
|statement = Пусть <tex>c</tex> {{---}} вес минимального потока в графе <tex>G</tex>. Тогда <tex>m \geq nc/2</tex>.
|proof =
Заметим, что, чтобы выполнялось условие, степень каждой вершины должна быть не менее, чем <tex>c</tex>. Действительно, пусть <tex>deg(v) < c</tex> для некоторой вершины <tex>v \in V</tex>. Тогда <tex>w(v, G \setminus v) = deg(v) < c</tex>, что противоречит условию. Далее, по [[Лемма_о_рукопожатиях|лемме о рукопожатиях]] имеем, что <tex>m \geq nc/2</tex>. Лемма доказана.
}}
{{Лемма
|about = 4
|id = Лемма4
|statement = Функция <tex>getCut</tex> после своего выполнения получит стянутый граф <tex>G'</tex> соответствующий конкретному разрезу <tex>\langle A, B \rangle</tex> исходного графа <tex>G</tex> тогда и только тогда, когда ни одно ребро, принадлежащее разрезу <tex>\langle A, B \rangle</tex>, не будет стянуто.
|proof =
Необходимость:
От противного. Если некоторое ребро <tex>uv</tex>, принадлежащее разрезу <tex>\langle A, B \rangle</tex> в <tex>G</tex> будет стянуто, то обе вершины <tex>u</tex> и <tex>v</tex> будут принадлежать одной мультивершине, а значит <tex>G'</tex> не соответствует разрезу <tex>\langle A, B \rangle</tex>. Противоречие.
Достаточность:
Пусть ни одно ребро, принадлежащее разрезу <tex>\langle A, B \rangle</tex> не было стянуто. Рассмотри произвольную пару вершин <tex>u \in A</tex> и <tex>v \in B</tex> в графе <tex>G</tex>. Если алгоритм стянул <tex>u</tex> и <tex>v</tex> в одну мультивершину в <tex>G'</tex>, тогда по [[Алгоритм Каргера для нахождения минимального разреза#Лемма1|лемме 1]].
}}
== Основные определения ==
Пусть <tex>G</tex> {{---}} неориентированный мультиграф с множеством вершин <tex>V</tex> и множеством ребер <tex>E</tex>, и <tex>|V| = n</tex>, <tex>|E| = m</tex>.
{{Определение
|definition=
'''Стягиванием''' (англ. ''contraction'') ребра <tex>uv</tex> называется следующая последовательность действий:
# Добавляем новую вершину <tex>w</tex>.
# Для всех ребер <tex>xu</tex> и <tex>xv</tex> (где <tex>x \in V, x \neq v, x \neq u</tex>) добавляем новые ребра <tex>xw</tex>. При этом, если получаются кратные ребра - оставляем их.
# Удаляем вершины <tex>u</tex> и <tex>v</tex> и все инцидентные им ребра.
}}
{{Определение
|definition=
'''Мультивершиной''' (англ. ''supervertex'') называется вершина, полученная из двух вершин стягиванием ребра между ними, каждая из которых, в свою очередь, может быть также мультивершиной.
}}
{{Определение
|definition=
'''Стянутым графом''' (англ. ''contracted graph'') называется граф, состоящий из двух мультивершин, полученный из исходного графа последовательным стягиванием произвольных ребер.
}}
{{Определение
|definition=
'''Разрезом''' (англ. ''cut'') <tex>\langle A, B \rangle</tex> называется разбиение множества <tex>V</tex> на два множества <tex>A</tex> и <tex>B</tex>, удовлетворяющее следующим условиям:
* <tex>A, B \subset V</tex>;
* <tex>A, B \neq \emptyset</tex>;
* <tex>A \cap B = \emptyset</tex>;
* <tex>A \cup B = V</tex>.
}}
Такой разрез часто называют также глобальным разрезом, чтобы отличать его от [[Разрез, лемма о потоке через разрез#Определение разреза|<tex>(s,t)</tex>-разреза]].
{{Определение
|definition=
'''Вес разреза''' <tex>\langle A, B \rangle</tex> обозначается <tex>w(A, B)</tex> и вычисляется по формуле:
* для взвешенного графа - <tex>w(A, B) =</tex> <tex dpi = "140">\sum\limits_{uv \in E, u \in A, v \in B} w(uv)</tex>;
* для невзвешенного графа - <tex>w(A, B) = |\{uv: u \in A, v \in B\}|</tex>.
}}
Задача поиска разреза минимальной веса (англ. ''min-cut problem'') заключается в поиске разреза минимального веса среди всех возможных разрезов исходного графа. Эту задачу можно решить с помощью любого из алгоритмов поиска максимального потока, зафиксировав произвольную вершину <tex>s</tex> в качестве истока и запуская его <tex>O(n)</tex> раз для всех возможных стоков. Если использовать быстрый алгоритм поиска максимального потока, работающий за <tex>O(mn)</tex>, то время работы такого алгоритма поиска минимального разреза будет <tex>O(n^2m)</tex>. Однако ниже описан существенно более простой в реализации и более быстрый алгоритм Каргера.
== Алгоритм ==
Пусть нам дан граф <tex>G = \{V, E\}</tex>.
minCut():
answer = INF;
for i = 1..c
curCut = getCut();
if curCut < answer
answer = curCut;
return answer;
Так как алгоритм вероятностный и функция <tex>getCut</tex> возвращает вес случайного потока, а не минимального, то для того, чтобы наверняка найти вес минимального, необходим вызвать эту функцию <tex>c</tex> раз. Какое конкретное значение <tex>c</tex> выбрать будет описано ниже.
Реализация функции <tex>getCut</tex> {{---}} это и есть основа алгоритма. Будем действовать следующим образом: пока вершин больше двух, будем выбирать случайное ребро и стягивать его. Когда в графе останется две вершины, то количество ребер между этими вершинами будет равно весу некоторого разреза исходного графа.
getCut():
n = количество вершин в G;
while n > 2
e = случайное ребро из G;
contract(e);
n--;
m = количество ребер в G;
return m;
== Корректность алгоритма ==
Докажем корректность алгоритма. Для удобства доказательства и оценок вероятностей, будем считать, что мы ищем не просто вес минимального разреза, а величину конкретного минимального разреза. То есть зафиксируем какой-то один из минимальных разрезов, и если функция <tex>getCut</tex> вернет правильный вес, но посчитает его на другом минимальном разрезе, то будем считать, что ответ получен неверный. Это условие не ухудшает оценки вероятностей и время работы алгоритма.
{{Лемма
|about = 1
|id = Лемма1
|statement = Пусть <tex>w</tex> {{---}} некоторая мультивершина, <tex>u</tex> и <tex>v</tex> - какие-то две из вершин, которые были стянуты в вершину <tex>w</tex>. Тогда существует такой путь <tex>p</tex> в исходном графе <tex>G</tex> между вершинами <tex>u</tex> и <tex>v</tex>, что ко всем ребрам этого пути была применена операция стягивания.
|proof =
Рассмотрим подграф <tex>G'</tex> исходного графа <tex>G</tex> в который входят все ребра, которые были стянуты в вершину <tex>w</tex>. Очевидно, что <tex>G'</tex> связен, а значит в нем существует путь между его любыми двумя вершина. Следовательно, существует путь между <tex>u</tex> и <tex>v</tex>, состоящий из стянутых ребер. Лемма доказана.
}}
{{Лемма
|about = 2
|id = Лемма2
|statement = Если стянуть некоторое ребро <tex>e = uv</tex> в графе G, то вес минимального разреза в графе <tex>G' = G\setminus e</tex> будет не меньше чем вес минимального разреза в исходном графе <tex>G</tex>.
|proof =
Составим биекцию между ребрами графов <tex>G</tex> и <tex>G'</tex>, не рассматривая ребра между вершинами <tex>u</tex> и <tex>v</tex> в графе <tex>G</tex>. Очевидно, что это возможно, исходя из следующих соображений. Все ребра в <tex>G</tex>, не инцидентные вершинам <tex>u</tex> и <tex>v</tex>, остались без изменений, а всем ребрам, инцидентным этим вершинам, по определению стягивания можно сопоставить новое ребро в <tex>G'</tex>. Пусть <tex>\langle A', B' \rangle</tex> {{---}} минимальный разрез в графе <tex>G'</tex>, и, не уменьшая общности, <tex>w \in A'</tex>. Рассмотрим разрез <tex>\langle A, B' \rangle</tex> в графе <tex>G</tex>. Исходя из биекции между ребрами и тем, что все ребра вида <tex>uv</tex> не пересекают разрез (так как <tex>u \in A, v \in A</tex>), то <tex>w(A', B') = w(A, B')</tex>. Тогда если разрез <tex>\langle A, B' \rangle</tex> в графе <tex>G</tex> {{---}} минимален, вес минимального разреза в <tex>G'</tex> совпадает с весом минимального размера в <tex>G</tex>. Если в <tex>G</tex> существует разрез меньшего веса, то вес минимального разреза в <tex>G'</tex> больше чем в <tex>G</tex>. Лемма доказана.
}}
{{Лемма
|about = 3
|id = Лемма3
|statement = Пусть <tex>c</tex> {{---}} вес минимального потока в графе <tex>G</tex>. Тогда <tex>m \geq nc/2</tex>.
|proof =
Заметим, что, чтобы выполнялось условие, степень каждой вершины должна быть не менее, чем <tex>c</tex>. Действительно, пусть <tex>deg(v) < c</tex> для некоторой вершины <tex>v \in V</tex>. Тогда <tex>w(v, G \setminus v) = deg(v) < c</tex>, что противоречит условию. Далее, по [[Лемма_о_рукопожатиях|лемме о рукопожатиях]] имеем, что <tex>m \geq nc/2</tex>. Лемма доказана.
}}
{{Лемма
|about = 4
|id = Лемма4
|statement = Функция <tex>getCut</tex> после своего выполнения получит стянутый граф <tex>G'</tex> соответствующий конкретному разрезу <tex>\langle A, B \rangle</tex> исходного графа <tex>G</tex> тогда и только тогда, когда ни одно ребро, принадлежащее разрезу <tex>\langle A, B \rangle</tex>, не будет стянуто.
|proof =
Необходимость:
От противного. Если некоторое ребро <tex>uv</tex>, принадлежащее разрезу <tex>\langle A, B \rangle</tex> в <tex>G</tex> будет стянуто, то обе вершины <tex>u</tex> и <tex>v</tex> будут принадлежать одной мультивершине, а значит <tex>G'</tex> не соответствует разрезу <tex>\langle A, B \rangle</tex>. Противоречие.
Достаточность:
Пусть ни одно ребро, принадлежащее разрезу <tex>\langle A, B \rangle</tex> не было стянуто. Рассмотри произвольную пару вершин <tex>u \in A</tex> и <tex>v \in B</tex> в графе <tex>G</tex>. Если алгоритм стянул <tex>u</tex> и <tex>v</tex> в одну мультивершину в <tex>G'</tex>, тогда по [[Алгоритм Каргера для нахождения минимального разреза#Лемма1|лемме 1]].
}}
