211
правок
Изменения
Новая страница: «{{В разработке}} ==Алгоритм== Пусть дан двудольный граф <tex>G(V, E)</tex> и требуется найти максима…»
{{В разработке}}
==Алгоритм==
Пусть дан двудольный граф <tex>G(V, E)</tex> и требуется найти максимальное паросочетание в нём. Преобразуем его в граф <tex>G'(V', E')</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>
1) Будем искать путь из <tex>s</tex> в <tex>t</tex> поиском в глубину.
2) Если путь найден, инвертируем все ребра на пути.
3) Если путь не был найден, значит текущее паросочетание является максимальным и алгоритм завершает работу. Иначе переходим к пункту 1)
В любой момент времени текущим паросочетанием будет множество ребер, направленных из <tex>R</tex> в <tex>L</tex>.
Очевидно, что путь из <tex>s</tex> в <tex>t</tex> является дополняющей цепью. Тогда корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы Бержа]].
==Псевдокод==
bool '''dfs'''(x)
'''if''' vis[x]
return false
vis[x] = true
'''for''' <tex>xy \in E</tex>
'''if''' py[y] = -1
py[y] = x
return true
'''else''' if dfs(p[y])
p[y] = x
return true
return false
'''while''' (changed)
changed = false
vis[] = false
'''for''' для каждой <tex>x \in L</tex>
'''if''' (px[x] == -1)
'''if''' dfs(x)
changed = true
==Алгоритм==
Пусть дан двудольный граф <tex>G(V, E)</tex> и требуется найти максимальное паросочетание в нём. Преобразуем его в граф <tex>G'(V', E')</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>
1) Будем искать путь из <tex>s</tex> в <tex>t</tex> поиском в глубину.
2) Если путь найден, инвертируем все ребра на пути.
3) Если путь не был найден, значит текущее паросочетание является максимальным и алгоритм завершает работу. Иначе переходим к пункту 1)
В любой момент времени текущим паросочетанием будет множество ребер, направленных из <tex>R</tex> в <tex>L</tex>.
Очевидно, что путь из <tex>s</tex> в <tex>t</tex> является дополняющей цепью. Тогда корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы Бержа]].
==Псевдокод==
bool '''dfs'''(x)
'''if''' vis[x]
return false
vis[x] = true
'''for''' <tex>xy \in E</tex>
'''if''' py[y] = -1
py[y] = x
return true
'''else''' if dfs(p[y])
p[y] = x
return true
return false
'''while''' (changed)
changed = false
vis[] = false
'''for''' для каждой <tex>x \in L</tex>
'''if''' (px[x] == -1)
'''if''' dfs(x)
changed = true
