Применение решения для LCA в DAG на циклических графах?

Question

Ответ на мой вопрос может быть очевиден, и я знаю этот очевидный ответ на бумаге. Я имею в виду, когда речь заходит о некоторых примерах, я понимаю, почему нам не разрешено создавать циклы для запуска алгоритма «Самый низкий общий предки», но у меня проблемы с пониманием документов, написанных для решения LCA в DAG. и так, какая часть раствора мешает нам использовать его на циклических графов ..

, что я желаю знать, и был бы благодарен быть в курсе:

• вы можете объяснить одно из решений LCA проблема в DAG, без лишних форм?
• Можете ли вы определить, какой шаг имеет проблемы с цилками и почему?

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

Заранее спасибо

Answer 1

Проблемы с циклы начинаются с самого определения.

Эксплуатационная Оценка по u и v определяется как множество таких узлов, что zz можно добраться из u и v и z не доступен из любого другого узла z' таким образом, что z' достижима из u и v.

Он может не существовать в циклическом графе. Например, если есть цикл 1->2->3 и два других узлов и ребер: 4->3 и 5->3, нет LCA для 4 и 5 (как все 1, 2 и 3 достижимы от них обоих, но они также достижимы друг от друга) ,

Вы можете найти все узлы, которые достижимы из u и v (с использованием ДФС или что-то еще), а затем проверить там есть такой узел z, который достижим от них обоих, но не от любого другого узла, который удовлетворяет этим условие (оно будет работать в полиномиальное время).

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