Найти все циклы на основе метки ребра в несвязном помеченном неориентированном графе?

Question

1. Условие того, что цикл должен быть действительным на этом графике, заключается в том, что ребра, образующие цикл, должны иметь хотя бы одну общую метку между ними.
2. Петли не рассматриваются как циклы.
3. В графике может быть много отключенных компонентов.

Рассмотрим следующий график

Допустимые циклы:
1. C, D, E (поскольку среди них распространено T3).
2. F, G, H (среди них распространено T4).

Недопустимые циклы:
1. A (циклы не рассматриваются как циклы)
2. A, B, C (поскольку общие метки не найдены).

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

Какой будет наилучший алгоритм обнаружения цикла, который может быть применен к такой проблеме.

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

Answer 1

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

Однако необходимо внести небольшую модификацию, чтобы запустить алгоритм, описанный k итераций, где k - количество различных меток.Кроме того, каждый раз, когда вы запускаете алгоритм, учитывайте только ребра с меткой T_i.

Время выполнения с модификацией составляет O(k(M + N)).Обратите внимание, что на этом шаге отпадает необходимость «создавать» k отдельные графы, как описано Малиоборо.

Answer 2

Самое простое решение, которое я могу себе представить, это разделить этот график на основе метки ребра.

Например, у вас есть этот график:

A --T1-- B
B --T2,T1-- C
C --T3,T1-- A

Поскольку существует три метки, создайте триграфики, основанные на ребре.

T1:
A --T1-- B
B --T1-- C
C --T1-- A

T2:
B --T2-- C

T3:
C --T3-- A

После этого вы можете выполнить алгоритм поиска в глубину (DFS) , чтобы найти цикл.