Изменится ли шаблон SCC, если мы перевернем график (используя алгоритм Косараджу)?

Предположим, у нас есть орграф, это не полный граф и имеет более одного SCC. Интересно, изменятся ли шаблоны сильно связанных компонентов, если мы транспонируем граф и используем алгоритм Косараджу? Говоря «транспонировать график», я имею в виду изменение направления ребер. Если мы попытаемся найти SCC в транспонированном/обратном графе вместо исходного, будет ли найденный SCC другим?

Я придумал этот вопрос, так как неправильно понял алгоритм SCC и запустил его на своем транспонированном/обратном графике. То, что я получил, идентично SCC правильному ответу/который запускает алгоритм Косараджу. Верно ли это для всех графиков?


algorithm adjacency-list adjacency-matrix directed-graph depth-first-search
person jsh6303    schedule 20.11.2013    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Никакой SCC графа не останется прежним, даже если график перевернуть, и это очень важный момент в алгоритме Косараджу для SCC. Меняются только связи между SCC. Алгоритм Косараджу использует этот факт для оценки DFS на обратном графике, который теперь дает более высокие значения времени окончания для SCC, которые ближе к SCC приемника. Поскольку приемник SCC не имеет исходящего ребра к другому SCC, следовательно, оценка DFS на нем выдает SCC как целостный связный компонент, а также позволяет разложить граф на подграф с аналогичными свойствами, к которому мы снова применяем DFS, чтобы получить другой SCC.

person Vikram Bhat    schedule 20.11.2013

arrow_upward
1
arrow_downward

Если вы посмотрите на http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm вы увидите, что:

«транспонированный граф (тот же граф с обратным направлением каждого ребра) имеет точно такие же сильно связанные компоненты, как и исходный граф».

(Сильно связанный компонент — это компонент, в котором вы можете добраться из каждой вершины в любую другую вершину в компоненте, и это все равно будет выполняться, если вы поменяете все связи). Конечно, ссылки, соединяющие разные компоненты, будут обратными, поэтому я ожидаю, что вы получите компоненты, выходящие в другом порядке.

person mcdowella    schedule 20.11.2013