Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Алгоритм Гомори-Ху

Если пропускная способность каждой дуги не зависит от направления движения потока по этой дуге и если каждую пару узлов можно рассматривать как пару источник – сток, то общее число задач о максимальном потоке, которое должно быть решено, равно , где - число узлов в сети. При работе алгоритма Гомори – Ху максимальный поток определяется только раз.

Пусть G = (N,A) – неориентированная сеть, где N – множество узлов, A – множество дуг. Пусть - пропускная способность дуги () из множества A, и пусть . Предположим также, что множество узлов задается в виде N = {1,2,...,n}. При описании алгоритма будут использоваться следующие обозначения:

- максимальный поток между узлами и ;

- максимальный разрез, отделяющий от ();

- пропускная способность минимального разреза, отделяющего от .

Если некоторый узел s рассматривать как источник, а другой узел t – как сток, то, согласно теореме о максимальном потоке и минимальном разрезе,

= . Если затем в качестве источника и с тока выбирается другая пара узлов (и соответственно), удовлетворяющих одному простому условию, то в алгоритме Гомори – Ху при определении величины используется решение задачи о максимальном потоке, найденное на предыдущем шаге. А именно, если узлы и выбираются таким образом, что оба они принадлежат X (или ), то множество узлов (или, если и принадлежат ) может быть объединено в один узел. При этом величина максимального потока из в будет одной и той же для исходной и конденсированной сетей.

Пусть - множество узлов, образованное в результате конденсации всех узлов, лежащих по ту сторону разреза, где не содержатся узлы и . Пусть - множество дуг, соединяющих узлы из . Тогда модифицированная сеть может быть представлена в виде . Если известны пропускные способности дуг, принадлежащих , то для нахождения величины максимального потока между узлами и можно воспользоваться процедурой расстановки пометок. Эти пропускные способности мы определим с помощью следующей простой процедуры. Пусть - узлы из , непосредственно связанные с узлом . Если конденсируется множество , то дуги заменяются одной дугой, соединяющий узел и конденсированный узел . Пропускная способность этой дуги вычисляется следующим образом:

.

Как отмечалось выше, величина максимального потока из в может быть вычислена с помощью процедуры расстановки пометок, примененной к сети . Для определения величины вновь необходимо найти минимальный разрез, отделяющий от. Пусть - соответствующий разрез с минимальной пропускной способностью. Теперь можно выбрать другую пару узлов, принадлежащую либо , либо , и построить другую конденсированную сеть. В результате выполнения процедуры расстановки пометок можно будет определить другой разрез и построить новую конденсированную сеть. Можно показать, что, после того как будет выбрана пара узлов, мы определим все величин максимального потока для исходной сети .



Блок – схема алгоритма Гомори – Ху изображена на рис. 3.3. Основная идея алгоритма состоит в интерактивном построении максимального остовного дерева , ветви которого соответствуют разрезам, а параметры ветвей -величинам разрезов. Ниже приводится обоснование алгоритма и приводится иллюстративный пример.

Рис. п1.1. Блок – схема алгоритма Гомори – Ху.

 

 

Обоснование алгоритма.

Пусть - неориентированная сеть, и пусть пропускные способности всех дуг из удовлетворяют условию . Пусть . Согласно теореме о максимальном потоке и минимальном разрезе, . Если , то , а если , то . Следовательно, и , откуда следует, что , где - связное множество узлов из N. Следовательно . В общем случае

, (п1.1)

где - связное множество узлов из N.

Перед тем как продолжить наши рассуждения , докажем следующие свойства максимального остовного дерева:

, (п1.2)

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

Если веса дуг остовного дерева положить равными , то для любой дуги , не принадлежащей дереву, будет справедливо соотношение

, (п1.3)

где - связная последовательность узлов дерева, принадлежащих пути из в. Из неравенств (п1.1) и (п1.2) получаем, что для любой дуги, не принадлежащей дереву,

. (п1.4)

Максимальное остовное дерево, удовлетворяющее равенству (п1.4), называется деревом разрезов потому, что каждая его ветвь соответствует разрезу, а вес ветви равен пропускной способности разреза. Если требуется определить величину максимального потока между двумя произвольными узлами, надо в дереве найти путь, соединяющий эти два узла, и выбрать в этом пути дугу с минимальным весом. Вес этой дуги равен величине потока между рассматриваемыми узлами.

 

<== предыдущая лекция | следующая лекция ==>
| Алгоритм Гомори-Ху

Дата добавления: 2014-01-07; Просмотров: 1141; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ‚аш ip: 54.198.188.116
Генерация страницы за: 0.091 сек.