Понятие остаточной сети

Теорема Форда-Фалкерсона: В любой сети максимальная величина потока из истока в сток равна минимальной пропускной способности разреза отделяющего от.

Задача о максимальном потоке

ПОТОКИ В СЕТЯХ

Лекция 11

Сеть – это ориентированный граф, каждому ребру которого поставлено в соответствие число, называемое пропускной способностью, а также выделено две вершины - исток и - сток,.

Поток – это функция, обладающая тремя свойствами:

1.;

2. (кососимметричность);

3.,

Величина потока это

Примем,,

- величина входящего потока для вершины

- величина исходящего потока для вершины

Разрез сети называется разбиение множества на две части и такое, что,,,.

Пропускная способность разреза –это сумма пропускных способностей дуг соединяющих вершины в и.

Минимальный разрез сети – это разрез с минимальной пропускной способностью.

Разрез,

Поток через разрез

{0,1}

{0,2}

{0,1,2}

{0,3}

{0,3, 1}

{0,3, 2}

{0,3, 2, 1}

{0,4}

{0,1,4}

{0,2,4}

{0,1, 2,4}

{0,3,4}

{0,1, 3,4}

{0,2, 3,4}

{01,,2, 3,4}

S

T

+¥

+¥

+¥

+¥

Рассмотрим ориентированный граф. Будем рассматривать его как сеть труб, по которым некоторое вещество движется от истока (где оно производится с постоянной скоростью) к стоку (где оно потребляется — с той же скоростью). Вместо потоков вещества можно рассматривать движение тока по проводам, деталей по конвейеру, информации по линиям связи или товаров от производителя к потребителю.

Как и в задаче о кратчайших путях, на каждом ребре графа мы пишем число. Но если раньше это число означало длину пути, то теперь это скорее ширина дороги, или пропускная способность трубы — максимальная скорость потока в этой трубе.

Мы считаем, что в вершинах вещество не накапливается — сколько приходит, столько и уходит (если вершина не является истоком или стоком).

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

Ключевую роль в методе Форда-Фалкерсона играют два понятия: остаточные сети и дополняющие пути.

Поиск максимального потока данным методом проводится по шагам. Вначале поток нулевой (и величина его равна нулю). На каждом шагу мы увеличиваем значение потока. Для этого мы находим "дополняющий путь", по которому можно пропустить ещё немного вещества, и используем его для увеличения потока. Этот шаг повторяется, пока есть дополняющие пути. Как следует из теории, полученный поток будет максимальным.

Остаточные сети

Пусть дана сеть и поток в ней. Тогда остаточная сеть состоит из тех ребер (называемых также остаточными), поток по которым можно увеличить. Заметим, что остаточное ребро не обязано быть ребром исходной сети. Такие "странные" ребра появляются когда имеется поток вещества в обратном направлении — ведь этот поток можно уменьшить.

У остаточных сетей есть интересное свойство — если в остаточной сети существует поток f, то прибавив его к исходному потоку в сети, мы получим также поток, удовлетворяющий всем требованиям, но который больше исходного.

Дополняющие пути

Назовем дополняющим путем простой путь из истока в сток в остаточной сети. Из определения остаточной сети вытекает, что по всем ребрам дополняющего пути можно переслать ещё сколько-то вещества, не превысив их пропускную способность. Величину наибольшего потока, который можно переслать по дополняющему пути назовем остаточной пропускной способностью пути. Очевидно, она равна значению минимального остаточного ребра, входящего в данный путь.

Сеть, - пропускная способность дуги

Поток

АЛГОРИТМ ФОРДА-ФАЛКЕРСОНА

1. Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.

2. В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.

3. Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:

- На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью c_min.

- Для каждого ребра на найденном пути увеличиваем поток на cmin, а в противоположном ему - уменьшаем на c_min.

- Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.

4. Возвращаемся на шаг 2.

	-4
		-4
					-4
			-4
				-4

	-11
		-4		-7
					-11
		-7	-4
			--7	-4

	-11				-1
		-12		-7
					-11
	-8		-4
			-15	-4

-12

	-11				-1
		-12		-7
					-11
	-12		-0
			-19	-4

-12

	-11				-1
		-12		-7
					-11
	-12		-0
			-19	-4

АЛГОРИТМ ФОРДА