Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 5
Текст из файла (страница 5)
5.2). 1лй ТЕОРЕМА О МАКСИМАЛЪНОМ ПОТОКЕ И МИНИМАЛЪНОМ РАЗРЕЗЕ Пусть (! — величина потока, протекающего из источника з в сток ! по дугам сети 6= (й(, А). Если предположить, что пропускная способность дуг из множества А конечна, то максимальная величина потока будет ограничена величинами пропускной способности дуг сети. Максимальный поток определяется с помощью одного ив основных понятий теории сетей †разре. Разрез может быть определен как множество дуг, исключение которых из сети отделило бы некоторое множество узлов от остальной части 23 Введение узлов.
На рис. 1.8 изображена сеть, в которой, разрез, состоящий из дуг (2, 4) и (3, 4), отделяет узел 4 от группы узлов 1, 2, 3. При решении задачи о максимальном потоке мы будем рассматривать только разрезы, отделяющие источник от стока. Пропускной способностью, или величиной, разреза называется сумма пропускных способностей всех дуг (ориентированных определенным образом'>),разреза. Пропускная способность разреза, указанного на рис. 1.8, равна сзе+сзч О4 Рис. 1.8. Разрез. Принцип работы алгоритмов поиска максимального потока в сети достаточно прост. Пусть Х вЂ” такое подмножество множества»(, что зФХ, а 1енХ. По определению множество всех дуг, инцидентных Х и заходящих в Х'>, образует разрез сети бз>. Обозначим через с(Ах) пропускную способность этого разреза.
Тогда величина максимального потока из узла з в узел 1 должна удовлетворять условию У~ с(Ах). (1.4) Таким образом, если для некоторого потока величиной У я некоторого разреза Ат выполнено равенство У=с(Ат), то данный поток является максимальным. Сформулируем теперь один из наиболее важных результатов теории потоков в сетях — теорему о максимальном потоке и минимальном разрезе, доказанную Фордом и Филкерсоном [8): для любой сети с одним источником и одним стоком величина максимального потока от источника к стоку равна ве- н Пусть разрез отделяет множество узлов Х от множества узлов Х, и предположим, что ймХ, зтиХ.
Тогда для ориентированной сети пропускной способностью разреза в направлении от з к т называется сумма пропускных способностей всех его ориентированных дуг, начальные узлы которых принадлежат множеству Х, а конечные — множеству Х.— Прим. перев. з> То есть начальные узлы этих дуг принадлежат множеству Хр М/Х, а конечные — множеству Х. — Прим. перев, '> Данное определение разреза отличается от приведенного выше определения. — Прим, лерее. Глава т' личине минимального разреза. Доказательство этой теоремы приводится в гл. 2. Рассмотрим сеть, изображенную на рис.
1.9. Числа, приписанные дугам, соответствуют их пропускным способностям в направлениях, указанных стрелками. Можно по- .Миниыаяьн разрез l I / т 1 1 Рис, !ЯЬ Минимальный разрез. О4 Рис. 1.1О. Разрез, не являющийся минимальным. Рнс. 1.11. Минимальный разрез неорнентированной сети. казать, что величина максимального потока из з в г равна 3. Минимальный разрез'> состоит из дуг (1, 2) и (3, 4) и имеет пропускную способность, равную 3. Рассмотрим другой разрез, отделяющий узел 1 от узла 4 и состоящий из дуг (1, 3), (2, 3) и (2, 4) (рис.
1.10). Этот разрез имеет пропускную способность, равную 15, и не может быть минимальным. " Согласно второму определению разреза.— Прим. иерее. Введение В заключение отметим, что если рассматриваемая сеть была бы неориентированной, то максимальный поток из 3 в Ф равнялся бы 4, поскольку минимальный разрез в данном случае состоит из дуг (1, 2), (2, 3) гз (3, 4) (рис. 1.11). УПРАЖНЕНИЯ 1. Почему методы сетевого анализа являются более предпочтительными по сравнению с другими методами исследования операций? Указать четыре причины. 2. Дать определения следующих понятий: (а) дуга; (б) узел; (в) ориентированная дуга; (г) биориентированная дуга; (д) неорнентированная дуга; (е) источник; (ж) сток; (з) главный источник; (н) главный сток. 3.
Дать определение цепи н пути. В чем различие между ними? 4. Дать определение цикла и контура. В чем различие между нимиу 5. Дать определение цикличесной и ациклической сетей. 6. Почему для циклических сетей в алгоритме нахождения потока минимальной стоимости могут возникнуть трудностиу 7. Дать определение дерева и остовного дерева: (а) словесно; (б) математически; (в) с использованием понятий теории графов. 8. Дать определение древовидности.
В чем различие между древовидностью и остовным деревому 9. Используя изображенную ниже сеть, построить: (а) дерево; (б) остовное дерево. 1О. Сформулировать все положения, вытекающие из структуры матрицы инциденций сети, изображенной на рис. 1.7. 11. Сформулировать принцип сохранения потока: (а) словесно; (б) математически. 12. Что такое (а) разрез; (б) величина разреза; (в) максимальный разрез; (г) минимальный разрезу 13.
Выписать матрицу инциденций узлы-дуги и матрицу смежности для изображенной ниже неориентнрованиой сети. Глава ! 14. Выписать матрицу инциденций узлы-дуги и матрицу смежности для изображенной ниже ориентированной сети. 15. В сети из упражнения 13 найти цикл, контур, путь из з в ! и цепь из з в Г.
Аналогичную задачу решить для сети из упражнения 14. 16. Рассмотреть сеть б (М, А), где М=(1, 2, .„, 9), А = (аь аз, -.. аы) а матрица инциденций узлы-дуги имеет вид (а) начертить сеть; (б) выписать матрицу смежности. 17. Рассмотреть ориентированную сеть б=(М, А), где М=(1, 2, 3, 4, 5), А= ((1, 2), (1, 3), (3, 1), (2, 3), (2, 4), (2, 5), (3, 5), (4, 5)): (а) начертить сеть; (б) выписать матрицу смежности; (в) выписать матрицу инциденций узлы-дуги.
18. Для изображенной ниже сети найти минимальное значение параметра а, при котором узел 4 принадлежит кратчайшему пути из узла 1 в увел 7, не содержащему циклов. При каком условии, наложенном на пара. метр а, длина кратчайшего пути может неограниченно уменьшаться? а, аз аз аз 1 1 О О О 1 О О 1 О 1 1 О О О 1 О О О О О О О О О О О О О О ! О О О О О аз а, а, О О О 1 О О О О О О 1 1 О 1 О О О О 1 О О О О О О О аз аз азо О О О О О О О О О О О О О О О О О 1 О 1 1 1 О О 1 1 О а„а,з, О О О О О О 1 О 1 О О 1 О О О О О 1 Введение 19.
Чему равна величина максимального потока нз узла з в узел Г длн изображенной ниже сети? Найти минимальный разрез. Указанные числа соответствуют пропускным способностям дуг. 20. Рассмотреть сеть из упражнения 19. Написать уравнение сохранения потока для узлов з, 3 и й ЛИТЕРАТУРА 1. Вахагга М., ?апг)в Я. Л., Ыпеаг Ргойтаппп!пя апб Хе!чгогй Г!овгз, %1!еу, 1пс., Хегч 'г'огй, 1978. 2. Вгаб!еу О.
Н., А Зигчеу о1 1)е!егш!п!зИс Хе!чгогйз, А??Е ТгалзасИопз, ?, 222 †2 (1975). 3. Визасйег К. О., Зав1у Т., Р!пйе ОгарЬз апб Хе!гчогйз, Мсбгам-НИ! Со., Хегч Уогй, 1965. [Имеется перевод: Басакер Р., Саати Т. Л. Конечные графы и сети. — Мл Наука, 1974.) 4. СЬагпез А., Соорег %. Чгг., Мзпайешеп! Мобе!в апб !пбиз(па! Арр1!саИопз о1 )йпеаг Ргойгапип(пя, Чо!в. 1 — 2, Чггйеу, ! пс., Хеч гог)г, 1961. 5. Пап!г!и О. 1,, 1лпеаг Ргобташш!пб апб Ех1епюопв, Рг!псе!оп Цпгчегвйу Ргевз, Рг!псе1оп, Х.
Л, 1963. (Имеется перевод: Данциг Д. Л. Линейное программирование и его применения н обобщения.— Мл Прогресс, 1966.) 6. Е!шаййгзЬу 3., Зоше Хе!гчог)г Мобе!з гп Мапаяешеп( Зс!епсе, Зрг!пиег- Чег!ая, 1пс., Хечг Уог1с, 1970. 7. Еи!ег Ь., ТЬе Коп!изЬегя Вг!диез, Бс!епЩгс АтеХсал, 189, 66 — 70 (1953). 8. Гогб 1.. К., Ри!кегзоп О. К., Р!отче!п Хе(чгог)гв, Рппсе1оп Цпшегзйу Ргезз, Рппсе1оп, Х.
3., 1962, (Имеется перевод: Форд Л. Р., Фалкерсон Д. Потоки в сетях. — Мс Мир, 1966.) 9. Ггапй Н., Гг!зсЬ 1. Т., Сошшип!саИоп, Тгапвпивз!оп, апб Тгапврог1аИоп ХеЬчог)гз, Абб!воп-)Уез1еу РиЫ. Со., 1пс., Ееаб1пя Маза., 1971. (Имеется перевод: Фрэнк Г., Фриш И. Сети, связь и потони.— Мс Связь, !978.! 10. ГиИгегзоп !). Е., Г!отч Хе1чгогйв апб СошЬ!па(опа! ОрегаИопв ЕезеагсЬ, Агаег!сап А(а!лета!!са! МопГЫу, 73, 115 — 138 (1966). 11. Нйсбсос1г Р. 1., ТЬе Р!в!пбиИоп о1 а Ргобис! 1гош Зечега1 Зоигсев 1о Хитегоиз 1.осзИИез, !оагаа! о) МасйелгаВсз алг( Рйуз!сз, 20, 224 — 230 (1941) . 12. Ни Т.
С., 1п!еиег Ргойтапнп!пи апб ХеИчог1г Р1очгз, Абб(воп-Ъ'ев!еу РиЬЬ Со., 1пс., Кеаб!пн Маза., !969.,(Имеется перевод: Ху Т. Целочисзенное программирование и потоки в сетях. — Мз Мир, 1974.) 13. !г! М., Хе!гчогй Р1отч, Тгапзрог(аИоп апб ЗсЬеби!!пб, Асабеш!с Ргезв, 1пе., Хечг Уогй, 1969. Рн )епзеп Р. А., Вагпев !У., Хе(чгогй Р1отч Ргойтаппп)пй, )Ч!1еу, 1пс., Хевг Уогй, ! 980. 15. Кооршапз Т.
С., ОрИшиш ЦбйггаИоп о1 1Ье Тгапврог1аИоп Зув1епь Ргосееб!пяз о( 1Ье 1п1егпаИопа! 3!аИвИса1 Соп!егепсе, %авЫпй1оп, 1). С 1947. Глава 1 16. Маппап!1 Т. 1., бо!реп В. 1., Тгапврог1а1юп Р!апп(п80 Хе(тчогЬ Мобе1в апб ТЬе!г 1птр!егпеп!а!1оп, %огЫп8 Рарег 77-008, оп!чегв!!у о1 Магу!апов, бепега! КевеагсЬ Ваагн, РасиВу Кевеагсп Атчагй, 1977. 17. М!п!е1са Е., Ор1!пива!1оп А!8ог!!Ыпв 1ог Хе!гасов апд бгарЬв, Магсе1 ВеЬ1гег, 1пс., Ыетч УогЬ, 1978. (Имеется перевод: Майника Э. Алгоритми оптимизации на сетях и графах. — Мл Мир, 198Ц 18.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
