Устранение циклических потоков из графа - PullRequest
5 голосов
/ 20 марта 2011

У меня есть ориентированный граф с объемами потока по краям, и я хотел бы упростить его, удалив все циклические потоки.Это может быть сделано путем нахождения минимума объемов потока вдоль каждого ребра в любом данном цикле и уменьшения потоков каждого ребра в цикле на этот минимальный объем, удаляя ребра с нулевым потоком.Когда все циклические потоки будут удалены, граф будет ациклическим.

Например, если у меня есть граф с вершинами A, B и C с потоками 1 из A → B, 2 из B → C и 3из C → A, тогда я могу переписать это без потока из A → B, 1 из B → C и 2 из C → A.Число ребер в графе уменьшилось с 3 до 2, и полученный граф является ациклическим.

Какой алгоритм (ы), если таковые имеются, решают эту проблему?

Ответы [ 4 ]

3 голосов
/ 01 сентября 2011

Может оказаться полезным использовать теорему о разложении потока (см. §6.2 из этого обсуждения максимального потока ), в которой говорится, что любой поток может быть разбит нанабор путей и циклов потока.Кроме того, на графике может быть не более m общих путей и циклов потока.Это означает, что одним простым алгоритмом исключения циклов потока было бы найти все пути потока в графе, а затем удалить весь оставшийся поток в графе, поскольку он должен соответствовать циклам потока.

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

Поскольку каждая DFS занимает время O (m + n) и существует не более O (m) путей потока, общее время выполнения этого шага составляет O (m 2 + mn), чтоявляется полиномом от размера графа.

Надеюсь, это поможет!

2 голосов
/ 25 марта 2011

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

Тогда результирующий поток не должен содержать циклов, поскольку он будет неоптимальным (по отношению к стоимости).

1 голос
/ 20 марта 2011

Вы можете использовать топологическую сортировку http://en.wikipedia.org/wiki/Topological_sorting

Это прекрасно работает, когда дело доходит до нахождения циклов в ориентированных графах

0 голосов
/ 20 марта 2011

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...