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

Question

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

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

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

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

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

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

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

Спасибо!

Answer 1

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

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

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

Answer 2

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

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

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