Учитывая , ориентированный граф , и две вершины . Пара простых путей от до является ребром, если они не разделяют ребро.
Используя максимальный поток, легко определить, существует ли пара непересекающихся ребер от до . Теперь, есть ли алгоритм полиномиальной временной задержки для перечисления всех пар ребер непересекающихся путей от до ?
cc.complexity-theory
graph-algorithms
любительский
источник
источник
Ответы:
Я считаю, что ответ Артема Казнатчеева правильный, но он не дает полиномиального пространства. Так что вот другой подход, который должен работать немного лучше в этом отношении.
Используя максимальный поток, можно решить чуть более общую проблему: найти пару непересекающихся путей ребер из некоторых двух вершин {s1, s2} к другой паре вершин {t1, t2}, но не контролируя, какая вершина источника соединена к какой вершине назначения.
Предположим, у нас есть граф G и вершины s1, s2, t1, t2, для которых мы хотим перечислить все пары путей. Найдите одну пару путей P1, P2, и пусть e = (s1, v) будет первым ребром на одном из этих путей. Затем мы можем разбить проблемное пространство на две подзадачи: пары путей, которые используют e, совпадают с путями из {v, s2} в {t1, t2} в G-s1, и пары путей, которые не используют e такие же, как пути из {s1, s2} в {t1, t2} в Ge. Выполните повторение в этих двух подзадачах и (чтобы избежать дублирования) сообщайте путь только тогда, когда вы находитесь в нижней части рекурсии.
источник
Это первый раз, когда я читал об алгоритмах полиномиальной задержки, поэтому я не уверен на 100% в своем ответе, но я думаю, что что-то вроде следующего должно работать.
Выберите какое-то соглашение для представления путей с естественным общим упорядочением определенным на нем. (Одним из примеров будет просто перечислить вершины пути и порядок лексикографически). Выберите свою любимую на месте структуру данных D, которая поддерживает логарифмический поиск и вставку (скажем, красно-черное дерево). Пусть G будет вашим графом< D г
Определим алгоритм :F
:F( с , т , G ,*Г )
(здесь ∗ D означает ссылку на внутреннюю структуру данных D )*D D
Если не в D .( P, Q ) D
2.1. Вставьте в D (и выведите, если вы предполагаете вывести при выполнении алгоритма).( P, Q ) D
источник
источник