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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Идея алгоритма)
м (rollbackEdits.php mass rollback)
 
(не показано 10 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
==Идея алгоритма==
 
==Идея алгоритма==
Пусть дан неориентированный двудольный граф <tex>G(V, E)</tex> и требуется найти [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]] в нём. Обозначим доли исходного графа как  
+
Пусть дан [[Основные определения теории графов|неориентированный двудольный граф]] <tex>G(V, E)</tex> и требуется найти [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]] в нём. Обозначим доли исходного графа как  
[[Файл:GrafG.png|thumb|200px|right|Пример графа G.]]
 
[[Файл:GrafG2.png|thumb|200px|right|Соответствующий граф G'.]]
 
 
<tex>L</tex> и <tex>R</tex>. Построим граф <tex>G'(V', E')</tex> следующим образом:  
 
<tex>L</tex> и <tex>R</tex>. Построим граф <tex>G'(V', E')</tex> следующим образом:  
  
Строка 8: Строка 6:
  
 
<tex>E' = \{(s, u): u \in L\} \cup \{(u, v): u \in L, v \in R\ , (u, v) \in E\} \cup \{(v, t): v \in R\} </tex>.
 
<tex>E' = \{(s, u): u \in L\} \cup \{(u, v): u \in L, v \in R\ , (u, v) \in E\} \cup \{(v, t): v \in R\} </tex>.
 
+
{|align="center"
 +
|-valign="center"
 +
|[[Файл:GrafG.png|thumb|200px|Пример графа <tex>G</tex>.]]
 +
|[[Файл:GrafG2.png|thumb|200px|Соответствующий граф <tex>G'</tex>.]]
 +
|}
 
Изначально текущее паросочетание пусто. На каждом шаге алгоритма будем поддерживать следующий инвариант: в текущее найденное паросочетание входят те и только те ребра, которые направлены из <tex>R</tex> в <tex>L</tex>.
 
Изначально текущее паросочетание пусто. На каждом шаге алгоритма будем поддерживать следующий инвариант: в текущее найденное паросочетание входят те и только те ребра, которые направлены из <tex>R</tex> в <tex>L</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>(s, L)</tex> и <tex>(R, t)</tex> ребра, покрывающие вершины, принадлежащие текущему паросочетанию.
+
# Если путь найден, перезаписываем текущее паросочетание. Далее инвертируем все рёбра на пути (ребро <tex>(u, v)</tex> становится ребром <tex>(v, u)</tex> ) и удаляем <tex>(s, L)</tex> и <tex>(R, t)</tex> ребра, покрывающие вершины, принадлежащие текущему паросочетанию.
 
# Если путь не был найден, значит текущее паросочетание является максимальным, и алгоритм завершает работу. Иначе переходим к пункту 1.
 
# Если путь не был найден, значит текущее паросочетание является максимальным, и алгоритм завершает работу. Иначе переходим к пункту 1.
  
 
==Корректность алгоритма==
 
==Корректность алгоритма==
  
Обозначим как <tex>p'</tex> путь из <tex>s</tex> в <tex>t</tex> без первого и последнего ребра. Пусть он
+
Обозначим как <tex>p'</tex> путь <tex>p</tex> из <tex>s</tex> в <tex>t</tex> без первого и последнего ребра. Пусть он
является дополняющей цепью для исходного графа <tex>G</tex> и обратно — т.е. любая дополняющая цепь графа <tex>G</tex> является путем <tex>p'</tex>. Тогда из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы]] если мы на каждом шаге можем найти новый путь, т.е. находим новую дополняющую цепь, то мы увеличиваем текущее паросочетание. Если путь найти мы уже не можем, значит дополняющих цепей в графе нет и текущее паросочетание — искомое. Осталось доказать, что путь <tex>p'</tex> действительно является дополняющей цепью.
+
является дополняющей цепью для исходного графа <tex>G</tex>, и пусть также существование дополняющей цепи в графе <tex>G</tex> приводит к существованию пути <tex>p'</tex>. Тогда из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы]]: если мы на каком-то шаге можем найти новый путь, т.е дополняющую цепь, то мы увеличиваем текущее паросочетание. Если путь найти мы уже не можем, значит дополняющих цепей в графе нет и текущее паросочетание — искомое. Осталось доказать что сделанное предположение действительно верно.
  
Т.к. <tex>p'</tex> — путь в двудольном графе, он нечетной длины, в котором вершины не повторяются (т.к. этот путь строится с помощью поиска в глубину). Рассмотрим текущее паросочетание. Мы записывали в него ребра из <tex>L</tex> в <tex>R</tex>, но после этого инвертировали их. Значит, ребра текущего паросочетания сейчас ведут из <tex>R</tex> в <tex>L</tex>. В таком случае ребра пути <tex>p'</tex> можно пронумеровать так, чтобы нечетные ребра были свободными, а четные — покрытыми (что соответствует текущему паросочетанию). Тогда этот путь — дополняющая цепь для графа <tex>G</tex>, и паросочетание можно перезаписать.
+
Т. к. <tex>p'</tex> — путь в двудольном графе, начинающийся в <tex>L</tex> и заканчивающийся в <tex>R</tex>, то он нечетной длины. Вершины в нем не повторяются (т.к. это путь в дереве поиска в глубину). Рассмотрим текущее паросочетание. Согласно поддерживаемому инварианту <tex>(R,L)</tex>-ребра в паросочетании, а  <tex>(L,R)</tex>-ребра {{---}} нет. В таком случае ребра пути <tex>p'</tex> можно пронумеровать так, чтобы нечетные ребра были свободными, а четные — покрытыми ребрами текущего паросочетания. Заметим, что путь может начинаться и заканчиваться только в свободной вершине, т. к. из <tex>s</tex> ведут ребра только в свободные вершины и только из свободных вершин ведут ребра в <tex>t</tex>. Итак, теперь ясно, что <tex>p'</tex> — дополняющая цепь для графа <tex>G</tex>.
Обратно дополняющая цепь в графе <tex>G</tex> это путь нечетной длины из <tex>L</tex> в <tex>R</tex>. Он начинается в какой-то вершине <tex>u \in L\</tex> и заканчивается в вершине <tex>v \in R\</tex> (поскольку концевые вершины этого пути должны быть свободны). Нo каждая вершина из <tex>L</tex> связана ребром с <tex>s</tex> в графе <tex>G'</tex>, аналогично каждая вершина из <tex>R</tex> связана ребром с <tex>t</tex>. Тогда любая дополняющая цепь в графе <tex>G</tex> является частью пути из <tex>s</tex> в <tex>t</tex> в графе <tex>G'</tex>, или, что то же самое, является путем <tex>p'</tex>. Отсюда следует, что алгоритм корректен.
+
 
 +
Обратно, пусть существует дополняющая цепь в графе <tex>G</tex>. В одной из ориентаций она начинается в какой-то свободной вершине <tex>u \in L\</tex> и заканчивается в свободной вершине <tex>v \in R\</tex>, далее будем рассматривать именно эту ориентацию. Ребра поочередно то не лежат, то лежат в паросочетании, значит в нашей ориентации эти ребра поочередно ориентированы то <tex>(L, R)</tex>, то <tex>(R,L)</tex>. Заметим что эта ориентация совпадает с ориентацией ребер на пути, а значит в нашем ориентированом графе существует путь из свободной вершины <tex>u \in L</tex> в свободную вершину <tex>v \in R</tex>. Нo каждая свободная вершина из <tex>L</tex> связана ребром с <tex>s</tex> в графе <tex>G'</tex>, аналогично каждая свободная вершина из <tex>R</tex> связана ребром с <tex>t</tex>. Не сложно заметить, что, в таком случае, <tex>t</tex> достижим из <tex>s</tex>, а значит в процессе поиска в глубину будет найден некий <tex>s \rightarrow t</tex> путь <tex>p</tex> и соответствующий ему <tex>p'</tex>.
 +
 
 +
Утверждение доказано.
  
 
==Оценка производительности==
 
==Оценка производительности==
Строка 27: Строка 32:
  
 
==Псевдокод==
 
==Псевдокод==
 +
* <tex>px[]</tex> {{---}} массив вершин <tex>y \in R</tex>, инцидентные <tex>x_i \in L</tex> в текущем паросочетании,
 +
* <tex>py[]</tex> {{---}} массив вершин <tex>x \in L</tex>, инцидентные <tex>y_i \in R</tex> в текущем паросочетании,
 +
* <tex>vis[]</tex> {{---}} массив, где помечаются посещенные вершины.
 +
Максимальное паросочетание {{---}} такие ребра <tex>(x, y)</tex>, что <tex>x \in L, y \in R, px[x] = y</tex>.
  
В массиве <tex>px</tex> хранятся вершины <tex>y \in R</tex>, инцидентные <tex>x_i \in L</tex> в текущем паросочетании, для <tex>py</tex> аналогично.
+
Поиск в глубину, одновременно инвертирующий ребра:
Максимальное паросочетание {{---}} такие ребра <tex>(x, y)</tex>, что <tex>x \in L, y \in R, px[x] == y</tex>.
+
  '''bool''' dfs(x)''':'''
  bool '''dfs'''(x)
+
    '''if''' vis[x]
    '''if''' vis[x]
+
        '''return''' ''false''
      return false
+
    vis[x] = ''true''
    vis[x] = true
+
    '''for''' <tex>(x, y) \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
        px[x] = y
+
            '''return''' ''true''
        return true
+
        '''else'''
      '''else'''  
+
            '''if''' dfs(py[y])
        if dfs(py[y])
+
                py[y] = x
          py[y] = x
+
                px[x] = y
          px[x] = y
+
                '''return''' ''true''
          return true
+
    '''return''' ''false''
    return false
 
  
  px[] = -1
+
Инициализация и внешний цикл:
  py[] = -1
+
'''func''' fordFulkerson()''':'''
  is_path = true;
+
    fill(px, -1)
  '''while''' (is_path)
+
    fill(py, -1)
    is_path = false
+
    isPath = ''true''
    vis[] = false
+
    '''while''' isPath
    '''for''' <tex>x \in L</tex>
+
        isPath = ''false''
      '''if''' (px[x] == -1)
+
        fill(vis, ''false'')
        '''if''' dfs(x)
+
        '''for''' <tex>x \in L</tex>
          is_path = true
+
            '''if''' px[x] == -1
 
+
                '''if''' dfs(x)
==Ссылки==
+
                    isPath = ''true''
  
 +
==См. также==
 
* [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|Теорема о максимальном паросочетании и дополняющих цепях]]
 
* [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|Теорема о максимальном паросочетании и дополняющих цепях]]
 
* [[Алгоритм_Форда-Фалкерсона,_реализация_с_помощью_поиска_в_глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
 
* [[Алгоритм_Форда-Фалкерсона,_реализация_с_помощью_поиска_в_глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
  
==Литература==
+
==Источники информации==
 
+
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн {{---}} "Алгоритмы: построение и анализ", 2-е издание, стр. 758 - 761.
Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд {{---}} "Алгоритмы: построение и анализ", 2-е издание, стр. 758 - 761.
 
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Задача о паросочетании]]
 
[[Категория:Задача о паросочетании]]

Текущая версия на 19:12, 4 сентября 2022

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

Пусть дан неориентированный двудольный граф [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\ , (u, v) \in E\} \cup \{(v, t): v \in R\} [/math].

Пример графа [math]G[/math].
Соответствующий граф [math]G'[/math].

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

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

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

Обозначим как [math]p'[/math] путь [math]p[/math] из [math]s[/math] в [math]t[/math] без первого и последнего ребра. Пусть он является дополняющей цепью для исходного графа [math]G[/math], и пусть также существование дополняющей цепи в графе [math]G[/math] приводит к существованию пути [math]p'[/math]. Тогда из теоремы: если мы на каком-то шаге можем найти новый путь, т.е дополняющую цепь, то мы увеличиваем текущее паросочетание. Если путь найти мы уже не можем, значит дополняющих цепей в графе нет и текущее паросочетание — искомое. Осталось доказать что сделанное предположение действительно верно.

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

Обратно, пусть существует дополняющая цепь в графе [math]G[/math]. В одной из ориентаций она начинается в какой-то свободной вершине [math]u \in L\[/math] и заканчивается в свободной вершине [math]v \in R\[/math], далее будем рассматривать именно эту ориентацию. Ребра поочередно то не лежат, то лежат в паросочетании, значит в нашей ориентации эти ребра поочередно ориентированы то [math](L, R)[/math], то [math](R,L)[/math]. Заметим что эта ориентация совпадает с ориентацией ребер на пути, а значит в нашем ориентированом графе существует путь из свободной вершины [math]u \in L[/math] в свободную вершину [math]v \in R[/math]. Нo каждая свободная вершина из [math]L[/math] связана ребром с [math]s[/math] в графе [math]G'[/math], аналогично каждая свободная вершина из [math]R[/math] связана ребром с [math]t[/math]. Не сложно заметить, что, в таком случае, [math]t[/math] достижим из [math]s[/math], а значит в процессе поиска в глубину будет найден некий [math]s \rightarrow t[/math] путь [math]p[/math] и соответствующий ему [math]p'[/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].

Псевдокод

  • [math]px[][/math] — массив вершин [math]y \in R[/math], инцидентные [math]x_i \in L[/math] в текущем паросочетании,
  • [math]py[][/math] — массив вершин [math]x \in L[/math], инцидентные [math]y_i \in R[/math] в текущем паросочетании,
  • [math]vis[][/math] — массив, где помечаются посещенные вершины.

Максимальное паросочетание — такие ребра [math](x, y)[/math], что [math]x \in L, y \in R, px[x] = y[/math].

Поиск в глубину, одновременно инвертирующий ребра:

bool dfs(x):
    if vis[x]
        return false
    vis[x] = true
    for [math](x, y) \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

Инициализация и внешний цикл:

func fordFulkerson():
    fill(px, -1)
    fill(py, -1)
    isPath = true
    while isPath
        isPath = false
        fill(vis, false)
        for [math]x \in L[/math]
            if px[x] == -1
                if dfs(x)
                    isPath = true

См. также

Источники информации

  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн — "Алгоритмы: построение и анализ", 2-е издание, стр. 758 - 761.