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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{В разработке}} ==Алгоритм== Пусть дан двудольный граф <tex>G(V, E)</tex> и требуется найти максима…»)
 
(Псевдокод)
Строка 26: Строка 26:
 
     '''for''' <tex>xy \in E</tex>
 
     '''for''' <tex>xy \in E</tex>
 
       '''if''' py[y] = -1
 
       '''if''' py[y] = -1
         py[y] = x
+
         py[y] = x
 +
        px[x] = y
 
         return true
 
         return true
       '''else''' if dfs(p[y])
+
       '''else''' if dfs(py4w[y])
         p[y] = x
+
         py[y] = x
 +
        px[x] = y
 
         return true
 
         return true
 
     return false
 
     return false
  
 +
  px[] = -1
 +
  py[] = -1
 
   '''while''' (changed)
 
   '''while''' (changed)
 
     changed = false
 
     changed = false

Версия 23:54, 13 декабря 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] является дополняющей цепью. Тогда корректность алгоритма следует из теоремы Бержа.

Псевдокод

 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(py4w[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