3.10.2. Потоки в сетях

Для данной сети (G, P) Потоком называется функция , ставящая в соответствие каждой дуге E Некоторое неотрицательное число, такое что:

1) (т. е. поток неотрицателен и не превосходит пропускной;

Способности данной дуги);

2) для всякой вершин U, кроме источника и стока , где первая сумма вычисляется по всем дугам , для которых вершина u является концом, а вторая сумма по всем ребрам , для которых U является началом (т. е. общий поток, втекающий в данную вершину, равен суммарному потоку, вытекающему из этой вершины.)

Дуги, для которых поток равен пропускной способности: , называются Насыщенными; в противном случае, если-- ненасыщенными.

Из леммы о "рукопожатиях" и условия 2) следует, что суммарный поток, вытекающий из источника , равен суммарному потоку, втекающему в сток . Эта величина называется величиной потока (,)-сети.

Основная задача, которая ставится для вышеописанных сетей, состоит в отыскании максимального потока данной сети, т. е. потока, величина которого наибольшая при условиях 1) - 2).

Решение этой задачи связано предварительно с ответом на несколько более простых вопросов, касающихся связного (неориентированного) мультиграфа G и фиксированной пары его вершин и :

1. Сколько существует реберно-непересекающихся простых (,)- цепей в графе G?

2. Сколько существует вершинно - непересекающихся простых (,)- цепей в графе G?

Для того, чтобы сформулировать ответы на эти вопросы, введем следующие определения.

Множество называется (,)-Разделяющим, если всякая простая (,)- цепь содержит ребро из множества А.

Множество называется (,)-Отделяющим, если всякая простая (,) - цепь содержит ребро из В.

Теорема 1 (Менгер). Максимальное число реберно-непересекающихся простых (,)-цепей в графе G равно минимальному числу ребер в (,)-разделяющем множестве графа G.

Теорема 2 (Менгер). Максимальное число вершинно-неперксекающихся (,)-цепей в графе G равно минимальному числу вершин в (,)-отделяющем множестве графа G.

Теорема 3 (о целочисленности). Максимальное число непересекающихся по дугам простых (,)-цепей в (,)-сети равно минимальному числу дуг в (,)-разделяющем множестве цепи.

Теорема 4 (Форд - Фалкерсон). Величина максимального потока в (,)-сети равна минимальной пропускной способности (,)-разреза сети. (Пропускная способность разреза подсчитывается как сумма пропускных способностей всех ребер, составляющих данный разрез).

Схема доказательства. Если пропускные способности P(E) всех дуг выражаются целыми положительными числами, то расщепим каждую дугу Е На P(E) параллельных дуг с пропускной способностью 1. И тогда утверждение теоремы следует из теоремы о целочисленности.

Если пропускные способности P(E)Для всех ребер Е сети, то умножив их все на общий знаменатель, придем к предыдущему случаю.

Если P(E) не являются рациональными, то воспользуемся аппроксимацией действительных чисел рациональными, т. е. заменим P(E) последовательностями рациональных чисел, такими, что lim при . Для каждого N и сети с пропускными способностями An имеем предыдущий случай, при котором утверждение теоремы верно. Переходя к пределу при N¥, получим, что теорема справедлива в общем случае.

< Предыдущая		Следующая >