Основы дискретной математики В.А. Осипова (552659), страница 25
Текст из файла (страница 25)
е. С не содержит граней-треугольников, то Действительно, в общем случае каждый цикл С состоит как минимум из трех ребер. Следовательно, край каждой грани состоит как минимум из трех ребер, входящих в простой цикл, а любое из ребер принадлежит двум граням. Отсюда 31 < 2т. 2 По формуле Эйлера и — т+ 1 = 2. Поскольку у < — т, имеем 3 2 и — т+ — т > 2, откуда 1п < Зи — 6. Если длина любого простого цикла больше или равна четырем, та и из формулы Эйлера т следует, что и — т + — > 2, откуда т < 2и — 4. В графе Ке и = 5, т = Се~ = 10. Если бы он был планарным, то должно было выполняться неравенство 10 < 3 5 — 6, т.
е. 10< 9. В графе Кзз и = 6, т = 9. Он не содержит граней треугольников, так как в противном случае были бы смежны вершины из им ит, из или ум уг, уз (соединены тропинкой два дама или два колодца). Если бы Кз з был пленарным, то должно было выполняться неравенство 9 < 2 6 — 4, т. е, 9 < 8. Критерий планарности графа определяется теоремой Куратовского — Понтрягина. Граф С' называется измельчением графа 4.7. Потоки в сетях 14б Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Рис. 4.30.
С, если С' получен из С добавлением новых вершин на ребра. Например, на рис. 4.30 изображены измельчения графов Кз г и Теорема Куратовского-Понтрягина. Необходимое и достаточное условие планарности графа состоит в том, что он не содероюит подграфов, являющихся измельчениями графов Кз г и Кв. Важность понятия планарности, в частности для микроэлектроники, несомненна. Именно из-за того, что существуют непланарные графы, создана технология многослойных печатных плат и микросхем. 4.7. Потоки в сетях 4.7.1.
Транспортные сети Если мы припишем каждой дуге ориентированного графа поток некоторого вещества, то граф становится удобной моделью при исследовании целого ряда проблем в транспорте, связи и других областях, связанных с действительным и воображаемым движением товаров, информации и людей.
Рассмотрим следуюшую задачу, связанную с морским грузооборотом (К. Берж). Пусть некоторые порты аы аг, ..., а» располагают продуктом, имеющим спрос в портах Ьм бг, ..., бы и пусть наличный запас продукта в порту а; равен в,, а потребность в этом продукте в порту б равна е( . Обозначим через с»у полное количество продукта, которые способны перевести суда, плывущие из а; в 6 . Возможно ли удовлетворить все потребности? Как организовать перевозки? Мы привели простейший пример «транспортной задачи». Вершинам графа соответствуют пункты размещения или выгрузки товара; дуга, идущая из одной вершины в другую, указывает на возможность транспортировки товара из пункта, соответствующего первой вершине, в пункт, соответствующий второй вершине.
Каждой дуге приписывается некоторое положительное число — максимальная пропускная способность дуги. Она показывает, какое максимальное количество товара может быть выгружено в единипу времени в соответствующем пункте. Для решения подобных задач целесообразно построить математическую модель, являющуюся графом некоторого специального вида.
Транспортной сетью называется ориентированный граф С =<»', Г > без петель с множеством вершин к' = (ип и2, ..., и„), для которого выполнены условия; 1) существует одна и только одна вершина и1 такая, что Г 1(и1) = Я; 2) существует одна и только одна вершина и„такая, что Г(и„) = 6; 3) каждой дуге < и, у > поставлено в соответствие число С(ю, у) > О называемое пропускной способностью дуги. Вершина и1 называется источником, в нее не заходит ни одна дуга, вершина и„называется стоком, из нее не исходит ни одной дуги. Остальные вершины называются промежуточными, На рис.
4,31, а) изображена транспортная сеть с источником щ и стоком ие. У каждой дуги в кружочке отмечена ее пропускная способность. Функция ~р(щ у), определенная на множестве дуг транспортной сети С, называется потоком по транспортной сети С, если 1) для любой дуги < щ у > (о(щ у) — целое неотрицательное число; 2) для любой промежуточной вершины и уег-1(е) гег(е) 3) для любой дуги < щ у > (о(щ у) < С(щ у) Значение со(щ у) на дуге < щ у > называется потоком по дуге < щ у >. Условия 1 — 3 означают, что поток по дуге 4.7.
Потоки в сетях 149 а» ©' Ь Ф = )»»»»(»», »»„). сег»(с ) © ь Рис. 4.32. б) а) Рис. 4,3Е 148 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ это неотрицательное число, которое не превышает пропускной способности этой дуги и что сумма потоков по дугам, заходящим в промежуточную вершину, равна сумме потоков по дугам, исходящим из нее. Величиной потока»»с по транспортной сети С называется число Ф, равное сумме потоков по всем дугам, заходящим в вершину»»„, т. е. На рис. 4.31, б) приведен пример потока по транспортной сети, изображенной на рис. 4.31, а). У каждой дуги указана величина потока по этой дуге.
Величина потока Ф по транспортной сети равна 3. 4.7.2. Максимальный поток в сети Поток»»с называется максим ль»*ым, если величина этого потока Ф принимает максимальное значение по сравнению с другими потоками по транспортной сети С. Задача отыскания максимального потока — одна из наиболее важных в теории транспортных сетей. Покажем как свести к ней рассмотренную выше задачу о морских перевозках. Каждый из портов а, соединим с портом 6 дугой, пропускной способности с; . Они соответствуют промежуточным вершинам сети. Затем рассмотрим две дополнительные вершины — источник о» и сток и„.
Соединим щ с каждой вершиной вя дугой, пропускной способности аб а каждую вершину 6 с еи дугой, пропускной способности»1 . Получим транспортную сеть, изображенную на рис. 4.32. Если»р — наибольший поток в этой сети, то»»»(аь Ь ) означает количество продукта, которое нужно перевести из а» в Ьз,чтобы удовлетворить потребности в наибольшей степени. Дуга < ю, у > транспортной сети С называется насыщенной, если поток по ней ранен ее пропускной способности, т.
е. »»»(и, у) = С(щ у). Поток»»» называется полнь м, если любой путь из щ в и„имеет хотя бы одну насыщенную дугу. Полный поток является некоторым приближением к максимальному потоку, и при нахождении максимального потока удобно начинать с отыскания полного потока. Опишем алгоритм отыскания полного потока. Пусть С = =< Ъ; Г > — транспортная сеть, »»»(ю, у) — некоторый поток по С (в качестве начального потока можно взять, например, нулевой поток, т. е, такой, для которого»»с(щ у) = 0 для любой дуги < щ у >).
Алгоритм 4.9. 1. Проверяем, является ли поток ео полным, Если да, то заканчиваем работу, если нет, то переходим к шагу 2. 2. Удаляем из графа С все насыщенные дуги, сохраняя при этом вершины. Полученный граф обозначаем С'. 3. Ищем в С» путь»2 из щ в и„, все дуги которого не насыщенные (такой путь найдется, так как поток не полный).
4. Увеличиваем поток по дугам вдоль пути р до тех пор, пока какая-нибудь дуга не станет насыщенной, а поток по остальным дугам не изменяем. (При этом опять получим поток по транспортной сети С, величина которого больше на соответствующее число единиц.) Переходим к шагу 1. 151 150 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 4.7. Потоки в сетях Пример 4.18. Пользуясь алгоритмом 4.9 найдем полный поток в транспортной сети, изображенной на рис.
4.33, а). Начинаем с нулевого потока; насыщенных дуг нет (рис. 4.33, б)). Выделим путь (и1, из, ив, ив) и увеличим поток вдоль этого пути' на 4. Дуга < из, иь > станет насыщенной. Получим поток, изображенный на рис. 4.33, в), который насыщает одну дугу. Удалим ее и построим граф, изображенный на Рис. 4.33, г).
ВыДелим в нем пУть (и1, ие, из, ив, ив) и Увеличим поток вдоль этого пути на 2. Насыщенные дуги — < и1, из >, < из, из >, < ив, ие >. Удалим их. Получим поток (рис. 4.33, д)), который является полным, так как в соответствующем графе (рис. 4.33, е)) нет пути, соединяющего вершины и1 и ив. Величина полного потока равна 6. Для нахождения максимального потока используются, например, известный алгоритм Форда — Фалкерсопа и его модификации. Мы приведем здесь простой алгоритм, который можно использовать для транспортных сетей с небольшим числом вершин.
Увеличивающей цепью из и1 в иа для данного потока р называется произвольная последовательность попарно различных ВЕРШИН И дуГ и1 = Х1, и1, ХЗ, ив, ..., Хзе иго Ха+1 = иа (Хе Е Ъ', з = 1, ..., и + 1) причем и, Е Г и ~р(х,, хиь1) < С(х;, х;11) или и; Е Г 1 и ~р(х;4.1, х;) > О. Если для данного потока существует увеличивающая цепь, то величину потока можно увеличить на и О а) О ) 5 ) 5 Ь = ппп Ь(и;), где 1<5(Ь ) Пз д) ) С(х,, хз+1) — ~р(х;, х;+1), если и; Е Г; '-'(и11 = 35(хее1, х;), если и; б Г -1 В качестве начального потока в транспортной сети С =< К Г > можно взять нулевой поток или,предварительно построенный полный поток.
Алгоритм 4.10. 1. Строим для данного потока 1о увеличивающую цепь из и1 в и„. Если такой цепи нет, то поток ~р — максимальный, иначе переходим к п. 2. 2. Для увеличивающей цепи и1 = х1, и1, хз, ие, ..., ХЫ ию Ха+1 = иа НаХОДИМ ЗиаЧЕНИЕ ВЕЛИЧИНЫ з 5.) Юз з з) Рис.
4.33. Ь = 1шп Ь(из). 1<5(Ь 152 Глава 4. ЭЛЕХ!ЕНТЫ ТЕОРИИ ГРАФОВ 4.7. Потоки в сетях 153 3. Строим новую функцию-поток по следующему правилу; на дугах увеличивающей цепи значение потока по дуге и; увеличиваем на Ь, если ит Е Г, и уменьшаем на Ь, если и; Е Г По дугам, не входящим в эту цепь, значение потока не меняем и переходим к п.
2. Пример 4.19. Найдем максимальный поток в графе, изображенном на рис. 4.33, а). В качестве начального потока выберем полный поток (рис. 4.33, д)). Выберем увеличивающую цепь с вершинами (ит, из, игн и4, иб) и соответствующими дугами. Здесь Ь = шш(5, 2, 5., 7). Изменим поток, увеличив его величину на 2 (рис. 4.33, ж)). Выберем увеличивающую цепь С ВЕрШИНаМИ (ит, иЗ, иб, и2, и4, иб).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
