Поиск всех максимальных паросочетаний в двудольном графе

[myf]

Существует ли эффективный алгоритм поиска всех максимальных паросочетаний в двудольном графе? Алгоритм поиска одоного паросочетания есть везде, а вот всех. Или просто придется делать банальный перебор без всяких отсечений (а как тогда избежать повторений???). заранее спасибо!

[Егор]

myf писал(а):

Или просто придется делать банальный перебор без всяких отсечений (а как тогда избежать повторений???). заранее спасибо!

Первое, что приходит в голову - метод ветвей и границ, который можно оформить в виде рекурсии. Условие отсечения тривиально: не обрабатывать двудольный граф с долями X и Y, если Г(X) не совпадает с Y. Здесь Г(X) - множество всех соседей ("невест") для множества X.

Вот набросок алгоритма (почти готовая программа на Питоне). Через u обозначена матрица смежностей.

функция Gamma1(x, Y, u):
# множество соседей элемента x, принадлежащих Y
  вернуть множество таких y из Y, для которых u[x, y] == 1.

функция Gamma(X, Y, u):
# множество соседей множества X, принадлежащих Y
  вернуть объединение Gamma(x, Y, u) по всем x из X.

функция f(X, Y, u):
# возвращает список паросочетаний; паросочетание задаётся как список пар
  если X пусто или Gamma(X, Y, u) != Y,
    то вернуть пустой список
  результат = пустой список
  пусть x - какой-нибудь (например, минимальный) элемент из X
  для каждого y из Gamma1(x, Y, u):
    результат1 = f(X\x, Y\y, u)
    для каждого паросочетания1 из результата1:
      паросочетание = паросочетание1, к которому добавили пару (x,y)
      добавить к результату паросочетание
  вернуть результат

Естественно, подобный алгоритм будет нормально работать только для небольших графов.

Добавление. Виноват, перепутал условие задачи. Я набросал алгоритм для поиска всех паросочетаний размера n, если |X|=|Y|=n. Для поиска всех максимальных паросочетаний придётся существенно переделать рекурсивную функцию f.

[Macavity]

myf писал(а):

Существует ли эффективный алгоритм поиска всех максимальных паросочетаний в двудольном графе? Алгоритм поиска одоного паросочетания есть везде, а вот всех. Или просто придется делать банальный перебор без всяких отсечений (а как тогда избежать повторений???). заранее спасибо!

В книге Н.Кристофидиса "Теория графов" приводится вариант требуемого алгоритма. И вообще, мне кажется, книга полезная для практического использования.
Скачать можно здесь: http://nehudlit.ru/1/45/.

[myf]

Скачал книгу Н.Кристофидиса "Теория графов". Нет там такого алгоритма. Там как и везде алгоритмы поиска максимального паросочетания (только одного, случайного).

[Macavity]

myf писал(а):

Скачал книгу Н.Кристофидиса "Теория графов". Нет там такого алгоритма. Там как и везде алгоритмы поиска максимального паросочетания (только одного, случайного).

Вы правы, я невнимательно посмотрел вопрос. Однако мне кажется, что поиск максимальных паросочетаний можно сделать направленным.

Предположим, что использованием хорошего алгоритма удалось найти первое максимальное паросочетание. Как найти еще одно максимальное паросочетание? Два максимальных паросочетания должны отличаться хотя бы одним ребром. Скажем в первом паросочетании k ребер. Удалим временно из исходного графа одно из ребер, принадлежащих найденному максимальному паросочетанию, и снова найдем максимальное паросочетание. Сравним полученное паросочетание с ранее найденным максимальным паросочетанием.

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

б) Если же данное паросочетание не является максимальным, то это означает, что удаленное ребро должно входить во все максимальные паросочетания и его надо вернуть в граф и никогда больше не удалять, разыскивая другие максимальные паросочетания.

Вот, примерно, в этом и алгоритм, он явно конечен (временно удаляемые ребра) и по сути это алгоритм поиска по дереву в глубь с отсечениями. Однако, вполне возможно он не оптимален, но надеюсь приемлем.
Возможно, он такой же как предложил Егор, но я не понял его алгоритма.

[Jilian]

myf писал(а):

Существует ли эффективный алгоритм поиска всех максимальных паросочетаний в двудольном графе? Алгоритм поиска одоного паросочетания есть везде, а вот всех. Или просто придется делать банальный перебор без всяких отсечений (а как тогда избежать повторений???). заранее спасибо!

А где Вы нашли эффективный алгоритм поиска одного паросочетания?

Добавлено спустя 1 час 29 минут 38 секунд:

2myf
Буду благодарна за ссылочку.