соответствие в graph — это набор попарно вершинно-непересекающихся ребер, и он максимален, если покрывает максимально возможное количество вершин в графе. Существуют эффективные алгоритмы поиска таких соответствий, а также реализации (см., например, Boost для примера на C++).
Однако в произвольном графе может быть несколько максимальных паросочетаний; существуют ли реализации алгоритмов, позволяющие перечислить их все? Я бы предпочел реализации на C++, но и другие языки тоже подойдут.
«Алгоритмы перечисления всех совершенных, максимальных и максимальных соответствий в двудольных графах» — http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.8179&rep=rep1&type=pdf
"Подсчет числа соответствий в классах хордальных и двудольных хордальных графов" – http://www.jaist.ac.jp/~okamotoy/PDF/matchchordal.pdf
Я надеюсь, что это может помочь вам как-то.
Проблема нахождения всех максимальных паросочетаний в общих графах рассматривается Т. Уно (тот же автор, что и в первой ссылке, указанной Петром выше) в этой статье 2001 года:
Быстрый алгоритм перечисления недвудольных максимальных паросочетаний
Теперь максимальные совпадения (мощность) обычно являются строгим подмножеством максимальных совпадений, но как только известен размер максимального совпадения, максимальные совпадения легко фильтруются, чтобы исключить все совпадения, кроме максимальных.
Однако временная сложность этого «быстрого алгоритма», предложенного Т. Уно, зависит от количества максимальных совпадений. Действительно, для общего графа G(V,E) с |V| вершины и |E| ребер, временная сложность равна O(|E|+|V|+Δ*N), где Δ — максимальная степень вершин, а N — количество максимальных паросочетаний.
Это не было бы идеальным, когда отношение максимальных паросочетаний к максимальному паросочетанию велико. Однако алгоритм применяется к общим графам, поэтому вполне разумно ожидать такого поведения при поиске только максимальных совпадений.
