Тема: Каким аглоритмом можно произвести декомпозицию сильно связанного графа

Есть следующий сильно связанный граф:

http://www.translationdirectory.com/images_articles/glossaries/graph_theory/220px-Directed_cycle.svg.png

Хотелось бы как-то разбить его на 3 сильно связанных подграфа и получить их структуру.

Спасибо!

2

Re: Каким аглоритмом можно произвести декомпозицию сильно связанного графа

Это точки артикуляции - их можно найти так: http://e-maxx.ru/algo/cutpoints

3

Re: Каким аглоритмом можно произвести декомпозицию сильно связанного графа

Вроде, получается, спасибо. А как теперь получить подграфы, на которые разбивается основной граф?

4

Re: Каким аглоритмом можно произвести декомпозицию сильно связанного графа

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

Искать их можно в том же обходе в глубину, который применяется для поиска точек артикуляции. Надо ввести глобальный стек для рёбер, и при каждом проходе по ребру (в обходе в глубину) добавлять его в этот стек (только не надо добавлять одно и то же ребро дважды: из двух вариантов ориентации надо добавлять только первый), а при обнаружении точки сочленения ("if (fup[to] >= tin[v])") доставать из стека все рёбра вплоть до ребра (v,to) - эти рёбра образуют очередную компоненту вершинной двусвязности. После обхода в глубину из рёбер, оставшихся в стеке, также следует образовать отдельную компоненту.

5

Re: Каким аглоритмом можно произвести декомпозицию сильно связанного графа

Спасибо за разъяснения. Нашел реализацию на java - буду портировать на python smile

http://www.ibluemojo.com/school/articul_algorithm.html

6

Re: Каким аглоритмом можно произвести декомпозицию сильно связанного графа

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

http://www.sofsem.cz/sofsem12/files/pre … aliano.pdf

Гуру могут прокоментировать?

7

Re: Каким аглоритмом можно произвести декомпозицию сильно связанного графа

Классный график, спасибо