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

56                           Глава 3. Задача о максимальном потоке в сети




                                Рис. 6

задан поток положительной величины, то существует (s, t)-путь,
на дугах которого поток положителен.
    Д о к а з а т е л ь с т в о. Первое утверждение оставим в виде
несложного упражнения. Чтобы доказать второе, обозначим через X
множество вершин, достижимых из s путями, на дугах которых поток
положителен. Предположим, что t не содержится в X, и рассмотрим
разрез (X, X̄). Из определения X следует, что не существует дуг с
началом в X и концом в X̄, несущих положительный поток. Но тогда
величина потока через разрез (X, X̄) оказывается равной нулю, что
противоречит данному условию. ¤
    Упражнение 1. Примените описанный выше алгоритм для на-
хождения максимального потока и минимального разреза в сети из
примера 1.

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

    С помощью теоремы о максимальном потоке и минимальном раз-
резе и соответствующего алгоритма можно решать разнообразные за-
дачи теории графов.
     1. Достижимость вершин. Пусть i, j — различные вершины ор-
графа. Достижима ли вершина j из i, то есть, существует ли в графе
(i, j)-путь?
     Если существует (i, j)-путь, то существует и простой (i, j)-путь,
поэтому ответ на наш вопрос не изменится, если удалить дуги, вхо-
дящие в i, и дуги, выходящие из j. Пропускные способности всех
дуг положим равными 1 и получим сеть с источником i и сто-
ком j, или, короче, (i, j)-сеть. Отметим, что для (i, j)-сети пропуск-
ная способность разреза (X, X̄) равна числу элементов в множестве
EX = {k → l : k ∈ X, l ∈ X̄}. Следующее утверждение прямо следует
из предложения 1 §2.