Алгоритм построения графиков для сопоставления узлов

Question

Для ориентированного графа, какой алгоритм я могу использовать, чтобы найти случайное подмножество его ребер, чтобы у каждого узла было ровно одно входящее и ровно одно исходящее ребро?

Например, это может быть график, который мне дают:

И это будет правильный выходной граф:

Это действительно, потому что:

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

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

Есть ли эффективный алгоритм для решения этой проблемы?

Спасибо!

Answer 1

Это проблема покрытия циклов узлов. Это может быть решено как Максимальные соответствия в двудольных графах .

Короче говоря:

1. Разделите каждый узел на два, каждый в одном разделе графа, чтобы все ребра перешли из раздела P1 в раздел P2. В вашем примере узлы A и D превратятся в узлы A1, D1 в разделе P1 и A2, D2 в P2. Край A-D превратится в A1-D2, а D-A - в D1-A2.
2. Затем найдите максимальное соответствие, некоторые алгоритмы существуют.
3. Затем объедините узлы обратно, и вы получите покрытие цикла.

Answer 2

Вы пытаетесь разложить граф на набор циклов.

Эта ссылка указывает на алгоритм Тарьяна для поиска циклов в графе.

Послечто вам понадобится некоторая стратегия поиска (некоторые варианты циклов могут не привести к решению с учетом ваших ограничений).