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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
Строка 4: Строка 4:
 
<tex>V' = V \cup \{s, t\}</tex>
 
<tex>V' = V \cup \{s, t\}</tex>
  
Обазначим доли исходного графа как <tex>L</tex> и <tex>R</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>L</tex> и <tex>R</tex>. Тогда <tex>E' = {(s,u): u \in L} \cup {(u, v): u \in L, v \in R} \cup {(v, t): v \in R} </tex>
  
 
1) Будем искать путь из <tex>s</tex> в <tex>t</tex> поиском в глубину.  
 
1) Будем искать путь из <tex>s</tex> в <tex>t</tex> поиском в глубину.  

Версия 16:28, 22 декабря 2010

Алгоритм

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

[math]V' = V \cup \{s, t\}[/math]

Обозначим доли исходного графа как [math]L[/math] и [math]R[/math]. Тогда [math]E' = {(s,u): u \in L} \cup {(u, v): u \in L, v \in R} \cup {(v, t): v \in R} [/math]

1) Будем искать путь из [math]s[/math] в [math]t[/math] поиском в глубину.

2) Если путь найден, инвертируем все ребра на пути.

3) Если путь не был найден, значит текущее паросочетание является максимальным и алгоритм завершает работу. Иначе переходим к пункту 1)

В любой момент времени текущим паросочетанием будет множество ребер, направленных из [math]R[/math] в [math]L[/math].


Очевидно, что путь из [math]s[/math] в [math]t[/math] является дополняющей цепью для исходного графа [math]G[/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