Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

Скачать файл (16,20Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 195

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

150	ГЛ.	8. МАКСИМАЛЬНЫЙ ПОТОК
их пропускные способности.			Будем считать; что эта					сеть есть
N (F0). Предположим, что единица потока направляется по пути
A si,	A i3, A 3t\ дуга А 13 оказывается насыщенной, и						получается
сеть N (F]), изображенная на рис. 8 .8 . Мы считаем, что в этой
сети	дуги А 13 не существует,		а имеется			дуга А 31 с	пропускной
		способностью, равной 1. Если напра
	1,1	вить единицу потока по					увеличиваю
		щему поток пути A s2, А аз, А 31,							А ц ,
		A it,		то получится сеть			N	(F2),	изо
3,1	1,0	3,1 браженная на рис. 8.9.					В этой		сети
		дуги		А 31	не	существует,		а снова
		появляется			дуга A i3 с		пропускной
		способностью, равной 1.					Можно счи
	Р и с . 8.9.	тать,		что	оказалась		насыщенной
		дуга		A 3i в сети N (F2)			на рис. 8 .8 .

		Таким образом, видно,					что каждый
раз путь, увеличивающий поток,				меняет ориентацию			по крайней
мере у одной дуги из		сети N	(F). Этот результат сформулируем
в виде леммы.
Л емма 8.1. Пусть		N (F0),	'N (i^ ),		. . ., N (Fm) — произволь

ная последовательность сетей. В сети N (Fh) найдется по крайней мере одна дуга, которая не содержится в N (.Fft+1), где Fk+i — поток, полученный из Fk с помощью добавления в сеть N (Fh)

пути,	увеличивающего		поток, причем г (/ + 1 ) = min [е (/),
Ъ), j + i	%}, j+ i	Ej+i.	/1-

Назовем кардинальной длиной пути число дуг в этом пути.

Определим кардинальное расстояние между N s и N t в сети N (Fk)

как длину кратчайшего увеличивающего поток пути, ведущего из N s в N t в сети N (Fh). Если не существует пути, увеличивающего поток из N s в N t, то кардинальное расстояние между N s и N t полагаем равным оо. Будем обозначать кардинальное расстояние между N s и N t через lhst.

Заметим, что следует различать путь из N s в N t, увеличиваю щий поток, и цепь из N s в N t, по которой проходит поток (кото рую будем называть потоковой цепью). Например, на рис. 8 . 8

кратчайшая потоковая цепь N s, N и N 3, N t имеет кардинальную длину 3, в то время как кратчайший путь, увеличивающий поток, здесь такой: N s, N 2, N 3, N t, М4, N t (следовательно, кардинальное расстояние между N s и N t равно 5). На рис. 8.9 кратчайшая пото ковая цепь имеет кардинальную длину 3, а кардинальное рас стояние между N s и N t равно оо.

Определим кардинальное расстояние l\v между двумя узлами N u и N v в сети N (Fh) ■как длину кратчайшего увеличивающего поток пути, ведущего из N u в N v в сети N (Fh). Если такого пути не существует, то полагаем luv = оо.

	8.2. МЕТОД РАССТАНОВКИ ПОМЕТОК		151
Л емма 8.2.	При к = О, 1 , 2 , . . .	для любого узла N u спра
ведливы неравенства
и	L ^ l ksal		(а)
и
	Z u i< 4 +1.		(б)
Д оказательство. Поскольку (а) и (б)		доказываются аналогично,
рассмотрим одно из них, например (а).
Если	то соотношение (а) очевидно.
Пусть Zsu+1	конечно и равно h. Обозначим через		L h+l крат

чайший путь

из N s в N u,

увеличивающий поток в сети N {Fh+1).

Пусть

N S = N U(),

N Ui, . . . , N Ufi = N u—последовательность

узлов

пути Lh+l. Тогда

Zs„0 = 0.

Докажем,

что

4 .+1 < !

4 г,

г = 0 ,1 , ... ,

(в)

Очевидно,

если

дуга

Л„. „. +1 £ N ( F k+l),

то

либо

Au.u.+i £ N {Fh),

либо ^ u.+jUj. £ Lk. В первом случае lsui+1^

1 + leup поскольку всегда

можно получить путь из N s

в N u.+i не длиннее, чем 1 + 1*и., если

воспользоваться дугой

Аи.и.

. Во втором случае

u. =

1 +

Z* и.

1т1

I"Ь1*

откуда

ls>

— 1

+ Is, и. <

+ h, и..

Суммируя

все

неравенства

(в),

получим

Zs>

u0 =

_у __7ft+i

• ■

I V -- Vs, и

Л емма 8.3.

Пусть

некоторой

сети

N(Fh)

(к = 0,

1, . . . )

кратчайший

путь,

увеличивающий

поток, содержит

дугу Aij,

а в сети N (Fv),

р > к , кратчайший путь, увеличивающий поток,

содержит

дугу

А р.

Тогда

кардинальное

расстояние

Zff

между

узлами

N s и

сети

N ( F P)

превышает

1st

не меньше чем

на

2 единицы,

Z?t^ Z sH -2 .

Д оказательство.

Так как

А ц ^ Ь и, то Z^t =

/м +

1 +

In-

Кроме

того, 1% =

i . I s i и

Ip —1

Ijt'

Так как A j t £ L p,

то

1st — l“sj -Ь 1 -Ь

lit-

Из

леммы

8.2

следует,

что

Ip^lu-

Поэтому

1st

1% ~"Ь 1 4~ l i t

(1 +

h i ) Ч~ 1 “Ь (1 ~h h t ) —

2 +

1st-

Справедлива следующая теорема.

Т еорема 8.3. Если в методе расстановки пометок при

поиске

путей

из N s

в N t,

увеличивающих поток,

каждый раз выбирать

кратчайший

путь, а в качестве пометки

использовать

е (;') =

min [е (г),

Ъц — хц + Хр],

то для

получения

максимального

152 ГЛ. 8. МАКСИМАЛЬНЫЙ ПОТОК

потока в сети достаточно не больше чем п3раз найти путь, увели чивающий поток (где п — число узлов в сети).

Д оказательство. Пока не получен максимальный поток, длина любого пути, увеличивающего поток, не превышает п — 1. Чтобы доказать теорему, достаточно показать, что расстояние между N s и N t должно стать больше, чем п — 1, если п3 раз найти путь, увеличивающий поток.

Из леммы 8.3 следует, что в последовательности сетей N (F0), N (F^, . . ., N (Fh) каждая дуга A tj может изменить свою ориен-

тацию самое большее—^— раз. По лемме 8.1 при переходе от сети

N (Fk) к сети N (Fk+i) каждый путь, увеличивающий поток, изме няет ориентацию не менее чем у одной дуги. Так как всего в сети имеется п (п — 1) дуг, а каждая дуга может менять ориентацию

не более

раз, то общее число путей *), увеличивающих поток,

не может быть больше чем \^п (п — 1) • —g-"] + 1 ^ п3.Л

Ясно, что полученная оценка может быть немного улучшена, если учесть, что у дуг вида A si и А и ориентация не изменяется. Однако в настоящее время неизвестно, как эту оценку существенно уменьшить, например, до О (п2)* 2).

8.3. Приложения

/М ногие обобщения задачи о максимальном потоке по существу /сводятся к ней. Известно, что эта задача находит приложения

	в различных комбинаторных задачах. Основная трудность при
	этом заключается в построении такой сети, чтобы нахождение
.	максимального потока в ней было эквивалентно решению постав-
	ленной комбинаторной задачи.
\	Рассмотрим несколько задач такого типа. Одной из них являет
	ся задача о потоке в сети с несколькими источниками и стоками,
	когда заданы	предложения товара в источниках и спрос товара
	в стоках. Множество всех узлов разбивается на источники S,
	*) Для нахождения одного пути, увеличивающего поток, в сети с р
	дугами требуется О (р) вычислительных операций. Следовательно, в алго
	ритме Эдмондса — Карпа всего требуется О (п3р ) операций для нахождения
	максимального	потока.	Е. А. [5*] и Карзанова В.	А. [8*] построены алго
	В работах	Диница
	ритмы, более экономные		по числу вычислительных	операций: в работе [4*}
	максимальный	поток находится за О (п2р ) операций, а в работе [8*] — за

О(п3) операций. — Прим, перев.

2)В работе Н. Заде [19*] приведен пример, когда поиск максимального потока по алгоритму Эдмондса — Карпа требует перебора О (п3) путей, увели чивающих поток.— Прим, перев.

8.3. П Р И Л О Ж Е Н И Я

153

промежуточные узлы R и стоки Т. Каждому узлу N t £ S поставле но в соответствие неотрицательное число a (N г) (предложение в N t), а каждому узлу N } 6 Т — неотрицательное число b (Nj) (спрос

Р(ис. 8.10.

вN j). Возникает вопрос: при каких условиях спрос в стоках мож но удовлетворить предложением в источниках, т. е. когда ограни чения

2 * ь i 2		&	N t e s \
j	k
i	2	=	N i t R ,
j	k		N i t T ,
f - 2		xki = b(Nt),	N i t T ,
	k

0 ^ Xij b%j

допустимы? - Если потоку разрешается течь из любого источника в-любой

сток, то эта задача легко сводится к задаче с одним источником

иодним стоком добавлением одного дополнительного источника

иодного дополнительного стока. Добавляются новые ориентиро

ванные дуги, ведущие из дополнительного источника во все N t £ S и имеющие пропускные способности а (Л^), а также ориентирован ные дуги с пропускными способностями Ъ(Nг), ведущие из каждо го N t £ Т в дополнительный сток. Получается сеть, изображенная на рис. 8.10. Тогда задача об удовлетворении требуемого спроса заданным предложением сводится к нахождении! максимального потока в расширенной сети. Подробности можно найти в [67].

Если в сети с несколькими источниками и стоками поток дол жен идти из определенных источников в заданные стоки, возникает так называемая задача о многопродуктовых потоках в сети. Она будет рассматриваться в гл. 11.

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

Смотрите также файлы

Циперович, М. В. Обогащение углей в тяжелых суспензиях.pdf

Чеботаревский, В. В. Лаки и краски - что это такое.pdf

Черкасов, Г. И. Введение в технологию бетона.pdf

Чупахин, В. М. Производство жестяной консервной тары учебник.pdf

Шамрай, Ф. И. Сплавы вольфрама, молибдена и ниобия с бором и углеродом.pdf

Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

Смотрите также файлы

Информация

Списки файлов

Дополнительно