Приведенный ориентированный граф, мы можем использовать алгоритмы edmonds-karp или ford-fulkerson, чтобы найти максимальное количество пересекающихся границ пути в ориентированном графе.Найти непересекающиеся контуры пути (не число, пути)
Скажите, что в G есть k пересекающих границу путей, как можно найти фактические пути в полиномиальное время? Мой лучший выбор - BFS, и как только найден путь, отметьте те грани, которые используются.
Большое спасибо!
Вы можете использовать разложение потока. Это выглядит следующим образом:
Бежит в глубину поиска от начального узла и игнорировать ребра, которые имеют нулевой или отрицательный поток.
Как только вы достигнете конечного узла, вычтите его из потока через все ребра по пути от стартового узла к терминальному и распечатайте их (они образуют путь).
Продолжайте делать это, пока конечный узел доступен.
Каждый пробег использует полиномиальное количество времени и находит и удаляет один путь из графика. Количество непересекающихся путей явно полиномиально, поэтому этот алгоритм имеет многочленную временную сложность.
Вы также можете использовать поиск по ширине (тоже нужно игнорировать края с неположительным потоком).
Вижу, так трюк заключается в том, чтобы использовать алгоритм поиска для возвращаемого потока? большое спасибо! – Ruben
@ Рубен Да. Вам нужно использовать поток. – kraskevich
@kraskevich Привет! Я пытаюсь решить эту проблему, и все, что я нахожу в этой теме, имеет «дыру», где я не могу понять. Итак, в каком графике я должен запустить DFS? Остаточный график из максимального потока или исходного графика? Как мне лечить циклы? Заранее спасибо. – Marco
Вы применяете BFS к исходному графу или просто к ограниченному графику, образованному из ребер с ненулевым потоком? –