Поиск другого типа подключенного компонента

Question

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

Я знаю, как найти слабо и сильно связанные компоненты. Как вы можете найти односвязные компоненты?

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

Answer 1

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

Несвязанный подграф ациклического ориентированного графа обладает тем свойством, что для разных узлов u и v существует либо путь от u до v, либо путь от v до u, но не оба. Напишите u < v, если существует путь от u до v и u! = V. Так как либо u < v, либо v < u, но не оба, и u < v и v < w подразумевает u < w, отношение < является строгий общий порядок. Сортируя вершины в подграфе, мы находим, что они лежат на одном пути. Этот путь максимален, если и только если никакая вершина не может быть вставлена, что означает, что она начинается с источника (без входящих ребер), заканчивается у приемника (без исходящих ребер) и состоит исключительно из ребер, которые появляются в transitive reduction ациклический ориентированный граф.

Вот один алгоритм для перечисления максимальных Uni-связных подграфов ориентированного графа Г.

1. Найти сильные компоненты G. Договора ними, что приводит к конденсации G».
2. Вычислить переходную редукцию G '' из G '.
3. Перечислите все пути источника раковины с помощью, например, поиск в глубине, а затем заменить каждый узел его сильным компонентом в G.

Здесь представлена ​​графики семья с экспоненциально многими максимальными однотонный соединенными подграфами. Все ребра направлены вниз.

* 
/\ 
* * 
\/
    * 
/\ 
* * 
\/
    * 
/\ 
    . 
    . 
    . 
\/
    * 
/\ 
* * 
\/
    * 

Answer 2

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

Найдите подключенные компоненты G по первому поиску по ширине. Перебирайте узлы, но начинайте новый поиск только в узлах, которые не являются частью ранее обнаруженного компонента. См. (https://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29#Algorithms)

Узлы каждого из этих компонентов также образуют узлы односвязной компоненты исходного ориентированного графа.

=============================================================================================================================================== ===============

Теперь я понимаю, что каждый узел должен иметь ребро к краю для каждого другого узла подмножества неориентированного графа, поэтому необходимо, чтобы clique в G, а не связный подграф G.К сожалению, форма решения проблемы NP-полная, а форма функции NP-hard.

См. algorithms для некоторых бесплатных вариантов поиска клики.