Ссылка на алгоритм тестирования ацикличности смешанного графа?

Смешанный граф - это граф, который может иметь как направленные, так и ненаправленные ребра. Его лежащий в основе ненаправленный граф получается путем забывания ориентации направленных ребер, а в другом направлении ориентация смешанного графа получается путем назначения направления каждому неориентированному ребру. Набор ребер образует цикл в смешанном графе, если он может быть ориентирован для формирования направленного цикла. Смешанный граф ацикличен тогда и только тогда, когда у него нет циклов.

Это все стандартно, и есть много опубликованных работ, упоминающих ациклические смешанные графы. Поэтому должен быть известен следующий алгоритм проверки ацикличности смешанных графов:

Повторите следующие шаги:

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

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

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

ds.algorithms reference-request graph-theory graph-algorithms directed-acyclic-graph Дэвид Эппштейн
источник

что происходит, когда у вершины есть два падающих неориентированных ребра, и нет другого ребра? Например, в неориентированном треугольнике. Я имею в виду, правила выше покрывают этот случай?

Матеус де Оливейра Оливейра

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

Дэвид Эппштайн,

Возможно, было бы яснее рассмотреть, что происходит в случае, если ваш график не является ненаправленным. Один из способов проверить, является ли это лес, состоит в том, чтобы удалить листья (вершины степени 1) и изолированные вершины, пока вы не получите пустой граф (это лес) или нетривиальный 2-ядро (подграф, в котором все вершины имеют степень ≥ 2, который обязательно содержит цикл). Алгоритм смешанного графа вырождается в это в неориентированном случае (за исключением того, что он ориентирует листья, а не немедленно удаляет их), так же как он вырождается в стандартный алгоритм топологической сортировки в направленном случае.

Дэвид Эппштейн

Не уверен , что если вы уже видели: есть почта на cs.stackexchange , что задает подобный вопрос реф . Ответчик дает алгоритм нахождения цикла в смешанном графе, ориентируя ненаправленные ребра, отклоняя граф, если он не существует. Там также документ (ы) об определении смешанного графа сильно ли ориентируем исй но как ни странно, не мог найти что - нибудь на самом деле найти связные компоненты в смешанных графах.

Цюаньцюань Лю

Спасибо - нет, я этого не видел. Вопрос «найти ориентацию, чтобы граф содержал направленный цикл», безусловно, тот же, и алгоритм в ответе выглядит правильно. Но в отличие от того, что я описываю, это не линейное время.

Дэвид Эппштейн

Ответы:

Нахождение смешанных циклов в смешанном графе эквивалентно нахождению элементарных направленных циклов (длиной> = 3) в соответствующем ориентированном графе. Соответствующий ориентированный граф получается из смешанного графа путем замены каждого неориентированного ребра двумя направленными ребрами, указывающими в противоположных направлениях. Доказательство: (1) Каждый элементарный направленный цикл (длиной> = 3) в орграфе непосредственно соответствует смешанному циклу в смешанном графе. (2) Каждый смешанный цикл в смешанном графе содержит элементарный смешанный цикл длины> = 3, и каждый такой цикл непосредственно соответствует элементарному направленному циклу (длины> = 3) в ориентированном графе. (1) и (2) вместе доказывают оба направления утверждения, qed, Поэтому мы ищем ссылки, как вычислить (все?) Элементарные циклы (длиной> = 3) в ориентированном графе.

Комментарии указывают, что cs.stackexchange содержит некоторые ответы на этот вопрос, но неясно, как организовать результаты в краткий ответ. Этот пост в блоге, похоже, суммирует (наиболее?) Важные ссылки:

Алгоритм Р. Тарьяна

Самый ранний алгоритм, который я включил, был опубликован Р. Тарьяном в 1973 году.
Enumeration of the elementary circuits of a directed graph
R. Tarjan, SIAM Journal on Computing, 2 (1973), pp. 211-216
http://dx.doi.org/10.1137/0202017
Алгоритм Д. Б. Джонсона

Алгоритм Д. Б. Джонсона с 1975 года улучшает алгоритм Тарьяна за счет его сложности.
Finding all the elementary circuits of a directed graph.
D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
http://dx.doi.org/10.1137/0204007
В худшем случае алгоритм Тарьяна имеет временную сложность O (n⋅e (c + 1)), тогда как алгоритму Джонсона, предположительно, удается остаться в O ((n + e) (c + 1)), где n - число вершин, е - число ребер и с - число циклов в графе.

Алгоритм К. А. Хоуика и Г. А. Джеймса

Алгоритм KA Hawick и HA James из 2008 года дополнительно улучшает алгоритм Джонсона и устраняет его ограничения.
Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs.
Hawick and H.A. James, In Proceedings of FCS. 2008, 14-20
www.massey.ac.nz/~kahawick/cstn/013/cstn-013.pdf
http://complexity.massey.ac.nz/cstn/013/cstn-013.pdf
В отличие от алгоритма Джонсона, алгоритм К. А. Хоуика и Г. А. Джеймса способен обрабатывать графы, содержащие ребра, которые начинаются и заканчиваются в одной и той же вершине, а также множественные ребра, соединяющие одни и те же две вершины.

Само тестирование ацикличности кажется простым: вычислить сильно связанные компоненты графа. Любой (элементарный) цикл полностью содержится в сильно связанном компоненте. Сильно связная компонента содержит элементарный цикл, если она не является ненаправленным деревом.

Предложенный Дэвидом Эппштейном алгоритм дополнительно вычисляет один элементарный цикл в качестве доказательства, а вышеприведенные алгоритмы перечисляют все элементарные циклы. Любая вершина или ребро, не содержащиеся в элементарном цикле, могут быть удалены в качестве шага предварительной обработки, чтобы повысить скорость выполнения вышеуказанных алгоритмов. Алгоритм Дэвида Эппштейна может быть использован для этой цели, но даже если он используется только для сильно связанных компонентов, он не удалит все возможные вершины или ребра, которые могут быть удалены. Но даже если его можно расширить для этого (вычисление дерева разреза блоков, по крайней мере, позволяет удалить каждую возможную вершину, которая может быть удалена), неясно, действительно ли это улучшит скорость вышеупомянутых алгоритмов.

Томас Климпел
источник

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

Дэвид Эппштейн

@DavidEppstein Нахождение смешанных циклов в смешанном графе эквивалентно нахождению элементарных циклов (длиной> = 3) в соответствующем ориентированном графе. Найти ссылку на это утверждение может быть непросто, но доказать это утверждение несложно. Теперь я добавил утверждение и его доказательство к ответу. (Также добавлено замечание без доказательства того, что вычисление дерева

разрезов

Хорошо, но они все еще не линейное время.

Дэвид Эппштейн

@DavidEppstein Само тестирование ацикличности выполняется за линейное время. Но вы правы, время, когда любой из этих алгоритмов должен найти первую элементарную схему (длиной> 3), не является линейным (в худшем случае). Хуже того, большинство доступных реализаций алгоритма Джонсона, кажется, используют больше времени O ((n + e) (c + 1)), когда применяются к одному ориентированному кругу (с n вершинами, e = n ребрами и c = 1 элементарным). циклы). Тем не менее, это был правильный ответ, потому что статья Джонсона, похоже, является самой цитируемой ссылкой для «поиска элементарных цепей».

Томас Климпел