Дискретная математика: графы и автоматы. Альпин Ю.А - 57 стр.

§ 3. Приложения теоремы о потоках                                    57


   Предложение 1. Вершина j достижима из вершины i тогда
и только тогда, когда максимальный поток в (i, j)-сети имеет по-
ложительную величину.

    2. Непересекающиеся пути и теорема Менгера. Пусть i, j — раз-
личные вершины орграфа. Два (i, j)-пути называются непересекаю-
щимися по дугам, если они не имеют общих дуг. Каково максималь-
ное количество непересекающихся по дугам простых (i, j)-путей? Для
решения этой задачи снова воспользуемся понятием (i, j)-сети из п. 1.
    Предложение 2. Максимальное количество непересекающихся
по дугам простых (i, j)-путей равно величине максимального пото-
ка в (i, j)-сети.
    Д о к а з а т е л ь с т в о. Рассмотрим некоторое множество W непе-
ресекающихся по дугам простых (i, j)-путей, содержащее максималь-
ное число w элементов. Пусть через произвольно взятую вершину m
проходят k путей из W . Поскольку каждый из них (в силу простоты)
проходит через m единственный раз, и пути не имеют общих дуг, то
в m входит ровно k дуг и выходит из m ровно k дуг, принадлежащих
путям из W . Отсюда следует, что функция, равная единице на дугах
путей из W и нулю на прочих дугах, является потоком. Величина его,
очевидно, равна w.
    Обратно, пусть в сети имеется поток величины w. В силу пред-
ложения 1 §2 существует простой (i, j)-путь, на дугах которого поток
равен 1. Удалив дуги этого пути, получим сеть с потоком величины
w − 1. Будем повторять процедуру удаления путей, пока не получим
сеть с потоком величины 0. Легко заметить, что удаляемые пути не
имеют общих дуг и всего таких путей w.
    Мы установили, что в (i, j)-сети тогда и только тогда имеется
w-элементное множество простых (i, j)-путей, непересекающихся по
дугам, когда в этой сети есть поток величины w. Отсюда немедленно
следует доказываемое утверждение. ¤
    Из предложения 2 и теоремы о потоках вытекает
    Следствие 1. Максимальное количество непересекающихся по
дугам простых (i, j)-путей равно наименьшей из пропускных спо-
собностей разрезов (i, j)-сети.
    Множество C дуг графа называется (i, j)-разделяющим, если лю-
бой (i, j)-путь содержит дугу из C. Нетрудно понять, что количе-
ство непересекающихся по дугам простых (i, j)-путей не может пре-
вышать числа дуг любого (i, j)-разделяющего множества. Теперь
заметим, что для любого разреза (X, X̄) (i, j)-сети множество дуг