Как найти все вершинно-непересекающиеся пути в графе?

Question

Предположим, есть 3 целевых узла на графике.

Путь, не связанный с вершиной, означает, что во время пути не существует ни одного и того же узла, кроме конечных узлов.

Для любого одного узла, скажем, узла i, как найти все непересекающиеся вершины пути от узла i до трех целевых узлов?

Answer 1

Вы можете решить эту проблему, сведя ее к задаче о максимальном потоке в правильно построенном графике.Идея заключается в следующем:

1. Разбить каждый узел v на графике на узлы: v _in и v _out .
2. Для каждого узла v добавьте ребро емкости один от v _в до v _out .
3. Замените каждое другое ребро (u, v) в графе накрай от u _out до v _in емкости 1.
4. Добавить новый выделенный целевой узел t.
5. Для каждого целевого узлаv, добавьте ребро из v _в к t с емкостью 1.
6. Найдите максимальный поток от s _out до t.Значение потока - это число узловых непересекающихся путей.

Идея этой конструкции заключается в следующем.Любой путь потока от начального узла s к узлу назначения t должен иметь емкость один, поскольку все ребра имеют емкость один.Поскольку все емкости являются интегральными, существует интегральный максимальный поток.Никакие два пути потока не могут проходить через один и тот же промежуточный узел, потому что при прохождении через узел в графе путь потока должен пересекать границу от v _в до v _out , а пропускная способностьздесь был ограничен одним.Кроме того, этот путь потока должен достигать t, заканчиваясь одним из трех специальных узлов, которые вы определили, а затем следуя за ребром от этого узла к t.Таким образом, каждый путь потока представляет собой непересекающийся путь узла от исходного узла s к одному из трех узлов назначения.Соответственно, вычисление максимального потока здесь соответствует нахождению максимального числа непересекающихся узлов путей, которые вы можете выбрать из s для любого из трех пунктов назначения.

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