Edge biapartization с равным числом узлов

Question

Я пытаюсь решить стандартную проблему двупартийности, т. Е. Найти подмножество ребер, чтобы выходной граф был двудольным графом. Мои дополнительные ограничения:

1. Число вершин на каждой стороне должно быть одинаковым.
2. Каждая вершина имеет ровно 1 ребро.

На самом деле, было бы достаточно знать, существует ли такое подмножество вообще - мне не нужна сама конструкция. Оптимально, алгоритм должен быть быстрым, так как мне нужно многократно запускать его для O (400) узлов.

Answer 1

Если каждая вершина должна падать только на одном ребре, кажется, что вы хотите совместить. Если это так, алгоритм цветения Эдмондс выполнит эту работу. Я не использовал реализацию алгоритма для рекомендации. Вы можете зарегистрироваться http://www.algorithmic-solutions.com/leda/ledak/index.htm