Удаление ложных циклов при обнаружении циклов DFS-XOR для результатов алгоритма неориентированных графов

Question

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

Цитата из статьи: The method will find non-existing cycles in case there are no overlapping edges at all between the two cycles in base. This can be fixed by first applying AND on each two cycles in base.

В какой момент я должен применить AND?

Есть ли более подробное объяснение удаления ложных циклов в этом алгоритме?

Answer 1

Я думаю, что намерение состоит в том, что непосредственно перед вычислением XOR двух циклов для получения нового цикла вы проверяете, чтобы они не были непересекающимися. Это потому, что XOR двух непересекающихся циклов - это два непересекающихся цикла, а это не то, что вы хотели.

На самом деле, я думаю, что более эффективно объединить этап AND и XOR - для вычисления XOR вам необходимо идентифицировать ребра, которые принадлежат обоим циклам, чтобы исключить их. Так что просто следите за тем, выбросили ли вы какие-либо края, а если нет, то вы не нашли новый цикл.