Алгоритм Куна для поиска максимального паросочетания — различия между версиями
| Строка 1: | Строка 1: | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
| − | Если из вершины х не существует дополняющей цепи относительно | + | Если из вершины х не существует дополняющей цепи относительно паросочетания М, то если паросочетание М' получается из М изменением вдоль дополняющей цепи, то из х не существует дополняющей цепи в М'. |
|proof=Доказательство от противного! Допустим, что из х появилась дополняющая цепь относительно M'. Рассмотрим изменения, которые мы внесли в М вдоль дополняющей цепи, чтобы получить паросочетание М'. В этой цепи все промежуточные вершины были насыщенными, а концы свободные. После изменения вдоль этой цепи все вершины, лежащие на этой цепи станут насыщенными. Тогда появившаяся дополняющая цепь должна проходить хотя бы через одну из концевых вершин в той дополняющей цепи, относительно которой вносили изменения, поскольку иначе такая же дополняющая цепь была и в паросочетании М. Однако поскольку в паросочетании М концевые вершины не насыщены, то из вершины х в паросочетании М есть все равно есть дополняющая цепь. Надо рассмотреть часть дополняющей цепи В М', ограниченную концом текущей дополняющей цепи и концом той дополняющей цепи, вдоль которой вносили изменения, такую что вершина х будет промежуточной. Легко заметить что в такой цепи все промежуточные вершины насыщенные, а концы свободны, поэтому она является дополняющей. Значит, мы пришли к противоречию, поскольку в паросочетании М нет дополняющих цепей из вершины х. | |proof=Доказательство от противного! Допустим, что из х появилась дополняющая цепь относительно M'. Рассмотрим изменения, которые мы внесли в М вдоль дополняющей цепи, чтобы получить паросочетание М'. В этой цепи все промежуточные вершины были насыщенными, а концы свободные. После изменения вдоль этой цепи все вершины, лежащие на этой цепи станут насыщенными. Тогда появившаяся дополняющая цепь должна проходить хотя бы через одну из концевых вершин в той дополняющей цепи, относительно которой вносили изменения, поскольку иначе такая же дополняющая цепь была и в паросочетании М. Однако поскольку в паросочетании М концевые вершины не насыщены, то из вершины х в паросочетании М есть все равно есть дополняющая цепь. Надо рассмотреть часть дополняющей цепи В М', ограниченную концом текущей дополняющей цепи и концом той дополняющей цепи, вдоль которой вносили изменения, такую что вершина х будет промежуточной. Легко заметить что в такой цепи все промежуточные вершины насыщенные, а концы свободны, поэтому она является дополняющей. Значит, мы пришли к противоречию, поскольку в паросочетании М нет дополняющих цепей из вершины х. | ||
}} | }} | ||
==Алгоритм== | ==Алгоритм== | ||
| − | Пусть дан двудольный граф <tex>G(V, E)</tex> и требуется найти максимальное паросочетание в нём. | + | Пусть дан двудольный граф <tex>G(V, E)</tex> и требуется найти максимальное паросочетание в нём. Обозначим доли исходного графа как <tex>L</tex> и <tex>R</tex>. |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
1) Будем искать путь из <tex>s</tex> в <tex>t</tex> поиском в глубину. | 1) Будем искать путь из <tex>s</tex> в <tex>t</tex> поиском в глубину. | ||
Версия 12:10, 14 декабря 2010
| Теорема: |
Если из вершины х не существует дополняющей цепи относительно паросочетания М, то если паросочетание М' получается из М изменением вдоль дополняющей цепи, то из х не существует дополняющей цепи в М'. |
| Доказательство: |
| Доказательство от противного! Допустим, что из х появилась дополняющая цепь относительно M'. Рассмотрим изменения, которые мы внесли в М вдоль дополняющей цепи, чтобы получить паросочетание М'. В этой цепи все промежуточные вершины были насыщенными, а концы свободные. После изменения вдоль этой цепи все вершины, лежащие на этой цепи станут насыщенными. Тогда появившаяся дополняющая цепь должна проходить хотя бы через одну из концевых вершин в той дополняющей цепи, относительно которой вносили изменения, поскольку иначе такая же дополняющая цепь была и в паросочетании М. Однако поскольку в паросочетании М концевые вершины не насыщены, то из вершины х в паросочетании М есть все равно есть дополняющая цепь. Надо рассмотреть часть дополняющей цепи В М', ограниченную концом текущей дополняющей цепи и концом той дополняющей цепи, вдоль которой вносили изменения, такую что вершина х будет промежуточной. Легко заметить что в такой цепи все промежуточные вершины насыщенные, а концы свободны, поэтому она является дополняющей. Значит, мы пришли к противоречию, поскольку в паросочетании М нет дополняющих цепей из вершины х. |
Алгоритм
Пусть дан двудольный граф и требуется найти максимальное паросочетание в нём. Обозначим доли исходного графа как и . 1) Будем искать путь из в поиском в глубину.
2) Если путь найден, инвертируем все ребра на пути.
3) Если путь не был найден, значит текущее паросочетание является максимальным и алгоритм завершает работу. Иначе переходим к пункту 1)
В любой момент времени текущим паросочетанием будет множество ребер, направленных из в . Корректность работы алгоритма следует из теоремы Бержа и доказанной выше теоремы.
