Минимизировать набор ребер в ориентированном графе, сохраняя компоненты связности

Вот полный вопрос:

Предположим, у нас есть ориентированный граф G = (V, E), мы хотим найти граф G '= (V, E'), который обладает следующими свойствами:

  1. G 'имеет те же компоненты связности, что и G
  2. G 'имеет тот же граф компонентов, что и G
  3. E 'минимизирован. То есть E 'как можно меньше.

Вот что у меня получилось:

Сначала запустите алгоритм сильно связанных компонентов. Теперь у нас есть сильно связные компоненты. Теперь перейдите к каждому компоненту сильной связности и внутри этого SCC выполните простой цикл; то есть цикл, в котором единственными повторяющимися узлами являются узлы начала / окончания. Это минимизирует края внутри каждого SCC.

Теперь нам нужно минимизировать границы между SCC. Увы, я не могу придумать, как это сделать.

У меня два вопроса: (1) Правильно ли звучит алгоритм предшествующий части о минимизации краев между SCC? (2) Как минимизировать границы между SCC.

Что касается (2), я знаю, что это эквивалентно минимизации количества ребер в DAG. (Думайте о SCC как о вершинах). Но, похоже, это мне не помогает.


directed-acyclic-graphs algorithm graph-theory edges clrs
person user678392    schedule 19.02.2013    source источник
comment
Извините за мое незнание: что вы имеете в виду под compnent graph? Я не понимаю разницы между 1. и 2.   -  person dingalapadum    schedule 12.04.2015

Ответы (2)


arrow_upward
1
arrow_downward

  1. Алгоритм кажется правильным, если вы разрешаете закрытые обходы (то есть повторяющиеся вершины). Правильных циклов может не существовать (например, в компоненте в форме восьмерки), и найти их NP-сложно.

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

person Rafał Dowgird    schedule 19.02.2013
comment
Между двумя сильно связными компонентами могут быть дуги только в одном направлении; поэтому достаточно рассматривать неупорядоченные пары. - person Falk Hüffner; 19.02.2013
comment
@ FalkHüffner Верно, но на практике вам все равно нужно упорядочить пары, чтобы получить каноническое представление неупорядоченной пары :-) - person Rafał Dowgird; 19.02.2013
comment
@ Rafał Dowgird Спасибо! Но несколько вопросов: (1) каковы правильные циклы и (2) я не понимаю, о чем говорят ваши 2. Вы говорите, что просто оставляете границу между каждой парой SCC, которые связаны в графе SCC? Как это сохраняет свойство: G 'имеет тот же граф компонентов, что и G. - person user678392; 19.02.2013
comment
@ user678392 (1) Правильный цикл - это цикл, в котором ни одна вершина не появляется дважды (2) Ребро между компонентами A и B в графе компонентов существует, если и только если существует ребро между любыми двумя вершинами из A и B в исходном графе. Таким образом, пока между компонентами существует хотя бы одно исходное ребро, граф компонентов сохраняется. - person Rafał Dowgird; 19.02.2013

arrow_upward
0
arrow_downward

Что касается шага 2, минимизируйте границы между SCC, вы можете случайным образом выбрать вершину и запустить DFS, сохраняя только самый длинный путь для каждой пары (корень, конец), удаляя при этом другие пути. Сохраните все найденные вершины в списке L.

Выберите другую вершину, если она существует в L, перейти к следующей вершине; в противном случае повторите описанную выше процедуру.

person Alan Yang    schedule 02.12.2018