Алгоритм Форда-Фалкерсона для поиска максимального паросочетания — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
(Идея алгоритма)
Строка 1: Строка 1:
 
==Идея алгоритма==
 
==Идея алгоритма==
Пусть дан двудольный граф <tex>G(V, E)</tex> и требуется найти [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]] в нём. Обозначим доли исходного графа как <tex>L</tex> и <tex>R</tex>. Построим граф <tex>G'(V', E')</tex> следующим образом:  
+
Пусть дан неориентированный двудольный граф <tex>G(V, E)</tex> и требуется найти [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]] в нём. Обозначим доли исходного графа как <tex>L</tex> и <tex>R</tex>. Построим граф <tex>G'(V', E')</tex> следующим образом:  
  
<tex>V' = V \cup \{s, t\}</tex> (т.е. добавим две новые вершины <tex>s</tex> и <tex>t</tex>)
+
<tex>V' = V \cup \{s, t\}</tex> (т.е. добавим новый исток <tex>s</tex> и сток <tex>t</tex>);
  
<tex>E' = \{(s,u): u \in L\} \cup \{(u, v): u \in L, v \in R\} \cup \{(v, t): v \in R\} </tex> (проведем ребра из <tex>s</tex> в каждую вершину <tex>L</tex>, и из каждой вершины <tex>R</tex> в <tex>t</tex>).
+
<tex>E' = \{(s, u): u \in L\} \cup \{(u, v): u \in L, v \in R\} \cup \{(v, t): v \in R\} </tex> (проведем ребра из <tex>s</tex> в каждую вершину <tex>L</tex>, из каждой вершины <tex>R</tex> в <tex>t</tex>, и ориентируем все ребра графа <tex>G'</tex> так, чтобы они шли от <tex>u \in L\</tex> к <tex>v \in R\</tex>).
  
 
Изначально максимальное паросочетание пусто.
 
Изначально максимальное паросочетание пусто.
# Будем искать в графе <tex>G'</tex> путь из <tex>s</tex> в <tex>t</tex> поиском в глубину.  
+
# Ищем в графе <tex>G'</tex> путь из <tex>s</tex> в <tex>t</tex> поиском в глубину.  
# Если путь найден, инвертируем все рёбра на пути.
+
# Если путь найден, инвертируем все рёбра на пути (ребро <tex>(u, v)</tex> становится ребром <tex>(v, u)</tex>). После этого перезаписываем текущее паросочетание так, чтобы в него входили ребра этого пути, ведущие из <tex>R</tex> в <tex>L</tex>.
 
# Если путь не был найден, значит текущее паросочетание является максимальным, и алгоритм завершает работу. Иначе переходим к пункту 1.
 
# Если путь не был найден, значит текущее паросочетание является максимальным, и алгоритм завершает работу. Иначе переходим к пункту 1.
  
В любой момент времени текущим паросочетанием будет множество рёбер, направленных из <tex>R</tex> в <tex>L</tex>.
+
==Корректность алгоритма==
 +
 
 +
# Путь из <tex>s</tex> в <tex>t</tex> является дополняющей цепью для исходного графа <tex>G</tex>.
 +
# Инвертация ребер не меняет пути, следовательно, он остается дополняющей цепью.
 +
# В найденном пути вершины не повторяются (это свойство поиска в глубину), тогда множество ребер, ведущих только из <tex>R</tex> в <tex>L</tex> является паросочетанием.
 +
# Путь не был найден. Это значит, что не существует дополняющей цепи для графа <tex>G'</tex>. Тогда по [[Теорема о максимальном паросочетании и дополняющих цепях|теореме]] текущее паросочетание является максимальным.
 +
 
 +
==Оценка производительности==
 +
 
 +
Поиск в глубину запускается от вершины <tex>s</tex> не более чем <tex>L</tex> раз, т.к. из <tex>s</tex> ведет ровно <tex>L</tex> ребер, и при каждом запуске одно из них инвертируется. Сам поиск работает за <tex>O(E)</tex>, каждая инвертация и перезапись паросочетания так же занимает <tex>O(E)</tex> времени. Тогда все время алгоритма ограничено <tex>O(VE)</tex>.
  
 
==Псевдокод==
 
==Псевдокод==

Версия 00:42, 24 декабря 2011

Идея алгоритма

Пусть дан неориентированный двудольный граф [math]G(V, E)[/math] и требуется найти максимальное паросочетание в нём. Обозначим доли исходного графа как [math]L[/math] и [math]R[/math]. Построим граф [math]G'(V', E')[/math] следующим образом:

[math]V' = V \cup \{s, t\}[/math] (т.е. добавим новый исток [math]s[/math] и сток [math]t[/math]);

[math]E' = \{(s, u): u \in L\} \cup \{(u, v): u \in L, v \in R\} \cup \{(v, t): v \in R\} [/math] (проведем ребра из [math]s[/math] в каждую вершину [math]L[/math], из каждой вершины [math]R[/math] в [math]t[/math], и ориентируем все ребра графа [math]G'[/math] так, чтобы они шли от [math]u \in L\[/math] к [math]v \in R\[/math]).

Изначально максимальное паросочетание пусто.

  1. Ищем в графе [math]G'[/math] путь из [math]s[/math] в [math]t[/math] поиском в глубину.
  2. Если путь найден, инвертируем все рёбра на пути (ребро [math](u, v)[/math] становится ребром [math](v, u)[/math]). После этого перезаписываем текущее паросочетание так, чтобы в него входили ребра этого пути, ведущие из [math]R[/math] в [math]L[/math].
  3. Если путь не был найден, значит текущее паросочетание является максимальным, и алгоритм завершает работу. Иначе переходим к пункту 1.

Корректность алгоритма

  1. Путь из [math]s[/math] в [math]t[/math] является дополняющей цепью для исходного графа [math]G[/math].
  2. Инвертация ребер не меняет пути, следовательно, он остается дополняющей цепью.
  3. В найденном пути вершины не повторяются (это свойство поиска в глубину), тогда множество ребер, ведущих только из [math]R[/math] в [math]L[/math] является паросочетанием.
  4. Путь не был найден. Это значит, что не существует дополняющей цепи для графа [math]G'[/math]. Тогда по теореме текущее паросочетание является максимальным.

Оценка производительности

Поиск в глубину запускается от вершины [math]s[/math] не более чем [math]L[/math] раз, т.к. из [math]s[/math] ведет ровно [math]L[/math] ребер, и при каждом запуске одно из них инвертируется. Сам поиск работает за [math]O(E)[/math], каждая инвертация и перезапись паросочетания так же занимает [math]O(E)[/math] времени. Тогда все время алгоритма ограничено [math]O(VE)[/math].

Псевдокод

 bool  dfs(x)
   if vis[x]
     return false
   vis[x] = true
   for [math]xy \in E[/math]
     if py[y] = -1
       py[y] = x
       px[x] = y
       return true
     else if dfs(py[y])
       py[y] = x
       px[x] = y
       return true
   return false
 px[] = -1
 py[] = -1
 while (changed)
   changed = false
   vis[] = false
   for [math]x \in L[/math]
     if (px[x] == -1) 
         if dfs(x)
             changed = true