Министерство образования и науки Украины
Луганскийнациональный педагогический университет имени Тараса Шевченко
Кафедра алгебры и дискретной математикиКиршта Александр МихайловичПоиск максимальных потоков в сетях
Магистерская работа по специальности 8.080101
“Математика”
Научный руководитель –
к.ф.-м.н., доцент
Михайлова И.А.
Луганск – 2006 г.
Содержание
Введение………………………………………………………………………….3
Раздел I. Основные понятия и определения теории графов…………………..6
1.1. Понятиеграфа…………………………………………………….6
1.2. Графическоепредставление графов…………………………….7
1.3. Видыграфов………………………………………………………7
1.4. Элементыграфов…………………………………………………8
1.5. Представлениеграфов с помощью матриц……………………..9
1.5.1. Матрицы инцидентности и списки рёбер……………...9
1.5.2. Матрицы смежности…………………………………….12
Раздел II. Потоки в сетях………………………………………………………..14
2.1. Понятиесети………………………………………………………14
2.2. Задачао максимальном потоке…………………………………..16
2.3. Алгоритмразмещения пометок для задачи о максимальном потоке………………………………………………………………16
2.4. АлгоритмФорда-Фалкерсона…………………………………18
2.5. Графсо многими источниками и стоками………………………22
2.6. Задачао многополюсном максимальном потоке………………24
Раздел III. Автоматизация поиска максимальных потоков в сетях…………29
3.1. Описаниеинтерфейса программы……………………………….29
3.2. Инструкцияпользователя………………………………………30
3.3. Реализацияпрограммы…………………………………………33
3.4. Описаниепрограммного кода……………………………………38
Выводы…………………………………………………………………………40
Литература……………………………………………………………………….41
Приложение………………………………………………………………………43
ВВЕДЕНИЕ
Начало теории графов всеединодушно относят к 1736 г., когда Эйлер не только решил популярную в то времязадачу о кенигсбергских мостах, но и нашёл критерий существования в графеспециального маршрута (эйлерова цикла, как теперь его называют). Однако этотрезультат более ста лет оставался единственным результатом теории графов. Лишьв середине XIX века инженер-электрик Г.Кирхгофф разработал теорию деревьев дляисследования электрических цепей. А математик А. Кэли в связи с описанием строенияуглеводородов решил перечислительные задачи для трёх типов деревьев. К этому жепериоду относится появление знаменитой проблемы четырёх красок.
Родившись при решенииголоволомок и занимательных игр (задачи о шахматном коне, о ферзях, “кругосветноепутешествие”, задачи о свадьбах и гаремах и т. п.), теория графов в настоящеевремя стала простым, доступным и мощным средством решения вопросов, относящихсяк широкому кругу проблем. В виде графов можно, например, интерпретировать схемыдорог и электрические цепи, географические карты и молекулы химических соединений,связи между людьми и группами людей.
За последние десятилетиятеория графов превратилась в один из наиболее бурно развивающихся разделовматематики. Это вызвано запросами стремительно расширяющейся областиприложений. В теоретико-графовых терминах формулируется большое число задач,связанных с дискретными объектами. Рассмотрим примеры некоторых практическихзадач.
1. «Транспортные»задачи, в которых вершинами графа являются пункты, а ребрами – дороги(автомобильные, железные и др.) или другие транспортные (например, авиационные)маршруты. Другой пример – сети снабжения (энергоснабжения, газоснабжения,снабжения товарами и т.д.), в которых вершинами являются пункты производства ипотребления, а ребрами – возможные маршруты перемещения (линии электропередач,газопроводы, дороги и т.д.). Соответствующий класс задач оптимизации потоков грузов,размещения пунктов производства и потребления и т.д., иногда называется задачамиобеспечения или задачами о размещении. Их подклассом являются задачио грузоперевозках.
2. «Технологическиезадачи», в которых вершины отражают производственные элементы (заводы,цеха, станки и т.д.), а дуги – потоки сырья, материалов и продукции между ними,заключаются в определении оптимальной загрузки производственных элементов иобеспечивающих эту загрузку потоков.
3. Обменные схемы,являющиеся моделями таких явлений как бартер, взаимозачеты и т.д. Вершины графапри этом описывают участников обменной схемы (цепочки), а дуги – потокиматериальных и финансовых ресурсов между ними. Задача заключается в определениицепочки обменов, оптимальной с точки зрения, например, организатора обмена исогласованной с интересами участников цепочки и существующими ограничениями.
4. Управлениепроектами. С точки зрения теории графов проект – совокупность операций изависимостей между ними. Хрестоматийным примером является проект строительстванекоторого объекта. Совокупность моделей и методов, использующих язык ирезультаты теории графов и ориентированных на решение задач управления проектами,получила название календарно-сетевого планирования и управления (КСПУ).В рамках КСПУ решаются задачи определения последовательности выполненияопераций и распределения ресурсов между ними, оптимальных с точки зрения техили иных критериев (времени выполнения проекта, затрат, риска и др.).
5. Модели коллективови групп, используемые в социологии, основываются на представлении людей илиих групп в виде вершин, а отношений между ними (например, отношений знакомства,доверия, симпатии и т.д.) – в виде ребер или дуг. В рамках подобного описаниярешаются задачи исследования структуры социальных групп, их сравнения,определения агрегированных показателей, отражающих степень напряженности, согласованностивзаимодействия, и др.
6. Моделиорганизационных структур, в которых вершинами являются элементыорганизационной системы, а ребрами или дугами – связи (информационные, управляющие,технологические и др.) между ними.
Изучение этих и другихподобных им практических задач приводит к теории потоков в сетях. В даннойработе рассматривается только одна (но наиболее существенная) задача этойтеории, а именно задача нахождения максимального потока.
1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯТЕОРИИ ГРАФОВ1.1. Понятие графа
Пусть V – непустое множество, V (2) – множество всех его двухэлементных подмножеств.Пара (V, E), где Е – произвольное подмножество множества V (2), называется графом (неориентированным графом).
Элементы множества V называютсявершинами графа, а элементы множества Е – рёбрами. Множество вершин ирёбер графа G обозначаются символами VG и EGсоответственно. Число |VG| вершинграфа G называются его порядком иобозначаются через |G|. Если |G| =n, |EG| = m, то G называют (n,m)-графом.
Двевершины u и v графа смежны, если множество {u, v} является ребром, и не смежны в противном случае. Если e ={u, v} – ребро, то вершины u и vназывают его концами. Такое реброобозначают uv.
Дваребра называются смежными, если они имеют общий конец.
Вершинаv и ребро e называются инцидентными, если vявляется концом ребра e (т.е. e = uv), и не инцидентными в противномслучае.
Множествовсех вершин графа G, смежных снекоторой вершиной v, называется окружениемвершины v и обозначается через N(v).
Упорядоченнаяпара вершин называется ориентированным ребром.
Ориентированныйграф (или орграф) – это пара (V, A), где V – множество вершин, А –множество ориентированных рёбер, которые называются дугами, АV2. Еслиа = (v1, v2) – дуга, то вершины v1и v2называются её началом и концом соответственно. Если графориентированный, его обозначают
Каждомунеориентированному графу можно поставить в соответствие ориентированный граф стем же самым множеством вершин, в которых каждое ребро заменено двумя ориентированнымирёбрами, которые инцидентны тем самым вершинам и имеют обратные направления.Такое соответствие будем называть каноничным.
Если у ребраначало и конец совпадают, то такое ребро называют петлёй. 1.2.Графическое представление графов
Графы удобно изображать в виде рисунков,состоящих из точек и линий, соединяющих некоторые из этих точек. При этом точкисоответствуют вершинам графа, а соединяющие пары точек линии (прямолинейныелибо криволинейные) – рёбрам (табл.1).
Таблица1
Элементы графов
Геометрические элементы
1. v ÎV–вершина
1.• – точка в пространстве.
2. {u,v} – ребро неориентированного графа
2. u•−•v – отрезок.
3. (v1,v2) – дуги в ориентированном графе
3. v1•→v2 – направленный отрезок.
4. {v,v} – петля
4. – замкнутый отрезок. 1.3.Виды графов
Множество рёбер Е может быть пустым (рис. 1.1). Такой граф называетсянуль-графом и обозначается Ø.
рис. 1.1. Нуль-граф
Если же множество вершин V – пустое, то пустым является также множествоЕ. Такой граф называется пустым.Линии, которые изображают рёбра графа,могут пересекаться, но точки пересечения не являются вершинами (рис. 1.2, а);разные рёбра могут быть инцидентными одной и той же паре вершин (рис. 1.2, б),такие рёбра называются кратными. Этот случай соответствует наличию несколькиходинаковых пар (vi,vj) E(G). Граф, который содержит кратныерёбра, называется мультиграфом. Ребро может соединять некоторую вершину саму ссобою (рис. 1.2, в), такое ребро называется петлёй. Этот случай соответствуетналичию в множестве Е пар вида (v,v). Граф с петлями и кратными рёбраминазывается псевдографом. Конечный неориентированный граф без петель и кратныхрёбер называется обычным.
а б в
Рисунок1.2. Графы: а) – обычный, б) – с кратными рёбрами, в) – с петлёй1.4.Элементы графов
Путь – этопоследовательность рёбер e1, e2,…, em, такая, что рёбра ei,ei+1имеют общую вершину. Число рёбер называется длинной пути. Если ни одна из вершин не появляетсябольше одного раза, то путь называется простым. Понятно, что в простом пути ниодно ребро не используется дважды.
Путь называется циклом,если его начальная вершина совпадает с конечной; простым циклом, если это не выполняется для других вершин.
Чередующаясяпоследовательность v1, e1,v2, e2, …, el,vl+1вершини рёбер графа, такая, что ei =vivi+1 (i =1, l), называется маршрутом. Если v1 = vl+1, то маршрут замкнутый, иначеоткрытый.
Маршрут называется цепью,если все его рёбра различны, и простой цепью,если все вершины, кроме, возможно, крайних, различны. В цепи вершины v0и vk называются концамицепи. Цепь, которая соединяет вершины viи vj, обозначается
Для орграфов цепьназывается путём, а цикл – контуром.
Две вершины в графеназываются связными, если существует соединяющая их (простая) цепь. Граф, укоторого все вершины связны, называется связным. Ориентированный графназывается сильно связным, если для любыхдвух вершин существует ориентированный путь, который соединяет их.1.5.Представление графов с помощью матриц
1.5.1. Матрицы инцидентности и списки рёбер
Задать граф, значит,задать множество его вершин и рёбер, а также отношение инцидентности. Когдаграф G – конечный, для описания еговершин и рёбер достаточно их занумеровать. Пускай v1, v2,…,vn – вершины графа G; e1,e2,…, em – его рёбра. Отношение инцидентности можно обозначитьматрицей mстрок и n столбцов. Столбцысоответствуют вершинам графа, а строки – его рёбрам. Если ребро еі является инцидентнымвершине vj, то G, являющаяся одним из способов егоопределения (для графа на рис. 1.3), она задана в табл. 2, а.
Рис. 1.3.Обычный граф
В матрицеинцидентности ориентированного графаG, если вершина vj – начало ребра ei,то vj– конец ei, то ei –петля, а vj – инцидентнаяей вершина, (пример – табл. 2, бдля графа рис. 1.4).
Рис.1.4. Ориентированный граф
Таблица 2
а б
В каждой строке матрицыинцидентности для неориентированного или ориентированного графа только дваэлемента отличны от нуля(или один, если реброявляется петлёй). Потому такой способ задания графа не достаточно экономный.Отношение инцидентности можно задать ещё списком рёбер графа. Каждая строкаэтого списка соответствует ребру, в нём записаны номера вершин, инцидентных ему.Для неориентированного графа порядок этих вершин в строке произвольный, дляориентированного первым записывается номер или другое наименование началаребра, а другим – его конца. В таблице 3, а и б приведены списки рёбер дляграфов, изображённых на рис. 1.3 и 1.4.
По спискурёбер графа можно легко определить матрицу инцидентности. Действительно, каждаястрока этого списка соответствует строке матрицы с тем же номером. Длянеориентированного графа в строке списка записываются номера элементов строкиматрицы инцидентности, которые равняются 1, а для ориентированного графа в этойстроке первым записывается номер элемента строки матрицы, который равен -1, вторым– номер элемента, который равен 1.
Таблица3
а б1.5.2. Матрицы смежности
Матрицасмежности графа – это квадратная матрица δijравняется количеству рёбер, инцидентных i-йта j-й вершинам, для ориентированногографа этот элемент матрицы смежности соответствует количеству рёбер с началом ві-й вершине и концом в j-й. Таким образом, матрица смежностинеориентированного графа симметрична (δij= δji), а ориентированного– необязательно. Если она всё-таки симметрична, то для каждого ребра ориентированногографа существует ребро, которое соединяет те же вершины, но направлено в противоположнуюсторону. Очевидно, ориентированный граф с симметричной матрицей смежности каноничносоответствует неориентированному графу, который имеет ту же матрицу смежности.
Матрицы смежностирассмотренных выше графов (см. рис. 1.3 и 1.4) приведены в таблице 4.
Матрица смежностиполностью определяет соответствующий неориентированный или ориентированныйграф. Число его вершин равняется размерности матрицы n, i-й и j-й вершинам графа инцидентны ребер. Для неориентированногографа
Таблица 4
а б
Количество ихравняется сумме в этом треугольнике,то есть матрицы смежности. Вобоих случаях с помощью матрицы смежности легко строится, например, списокребер, который определяет граф. Элементу матрицы смежности, расположенном в і-й строке и j-м столбце, соответствует строк списка ребер(при і, j. Для неориентированного графа эти строки соответствуют только элементамназванного выше верхнего правого треугольника матрицы смежности, то есть элементам с
Итак, граф можно представитьразными способами. Он может быть изображён на рисунке, задан матрицей инцидентности,списком рёбер или матрицей смежности. Графический вид зависит от формы линий ивзаимного расположения вершин. Вид матриц и списка рёбер зависит от нумерациивершин и рёбер графа.
2. ПОТОКИ В СЕТЯХ2.1.Понятие сети
Сетью будем называтьориентированный связный граф без петель и параллельных рёбер. Потоки внеориентированных графах можно изобразить в виде потоков в соответствующихориентированных. Поток в петле не влияет на распределение потока междувершинами. Рассмотрим сеть G= (V, E), |V|= n,|E| = m. Пускай каждой дуге еj Eпоставлено в соответствие неотрицательноедействительное число сj, которое назовём пропускной способностью дугиеj. Обозначим через vi→ Vмножестводуг, выходящих из вершины vi, через V→ vi– множество дуг, заходящих в вершинуvi.
Потоком в сети Gиз вершины vsв вершину vtвеличиныwназывается неотрицательная,определенная на дугах еj, функция φ: Е → R+ {0}, такая, что
– = (1)
φ(еj) ≤ cj, j= 1, …, m.
Вершина vsназывается источником, вершина vt– стоком, а остальные вершины –промежуточными узлами. Число Q(vi)= — называется чистымпотоком из вершины viотносительно φ. Число φ(е)называется потоком по дуге е. Если “реальный”поток по дуге отрицательный, то его можно сделать положительным, выбравсоответствующую ориентацию дуги e. Систему уравнений (1) можнопереписать в векторном виде:
ВФ = l, (2)
где В – матрицаинцидентной размерности n m, Ф = (φ(e1) … φ(em))T, l= (0..0w0..0 – w0..0)T. Поскольку ранг матрицы инциденций равен n– 1, то система уравнений (1) избыточна: φ из vsв vtвеличиныwесть поток величины -wиз vtв vs.
Пример
Рис. 2.1. Поток величины 3
Сеть, изображённая нарис. 2.1, состоит из пяти узлов и восьми дуг. Будем рассматривать поток от v1до v5. Каждой дуге приписаны два числа:первое – величина потока по дуге, второе – пропускная способность дуги.Величина этого потока равна 3. Действительно,
Q(v1) = 5 — 2 = 3,
Q(v2) = 7 – (5 + 2) = 0,
Q(v3) = –4 – 0 +2 + 2 = 0, (3)
Q(v4) = –4 + 4 = 0,
Q(v5) = 4 + 0 – 7 = –3.
Систему уравнений (3)можно записать в векторном виде ВФ = l(2):
2.2.Задача о максимальном потоке
На практикечасто возникает проблема определения максимальной проводимости некоторой реальнойсети: сети транспортной, сети ЭВМ, других. Иногда нужно определить самыйдешёвый поток и т.д. Все эти и многие другие задачи решаются с помощьюалгоритмов,которые работают на сетях. Так, алгоритм о максимальном потоке ищет максимальновозможную пропускную способность сети, алгоритм минимальной стоимости – самыйдешёвый поток. В данном разделе будем рассматривать задачу о максимальном потоке.
Задача заключается внахождении такого множества потоков по дугам, чтобы величина Q(vs) была максимальной.
Разрез Sотделяет vsот vt,если вершины vs, vtпринадлежат разным сторонам разреза: vs Vs, vt Vt, V= Vs Vt.Пропускной способностью с(S) разреза Sназываетсясумма пропускных способностей дуг разреза, которые начинаются в Vsизаканчивается в Vt:
с(S) = .2.3.Алгоритм размещения пометок для задачи о максимальном потоке
Алгоритм размещенияпометок основан на следующей теореме.
Теорема 1.Теорема промаксимальный поток и минимальный разрез. Для произвольной сети максимальнаявеличина потока из vsв vtравняется минимальной пропускной способности разреза, который отделяет vsот vt.
Доказательство
Покажем, что величина wпроизвольного потока φ не превышает пропускной способности разреза (Vs,Vt), который отделяет vsот vt.Поскольку функция φ поток, тоона удовлетворяет уравнению (1) сохранении потока:
— = w,
— = 0, vs, vt, (2)
— = -w.
Сложим те уравнения из(2), которые соответствуют вершинам из Vs.Учитывая, что vs Vs, vt Vt,получаем:
w= — .
Всё множество вершин распадаетсяна две стороны: V= Vs Vt.Получаем
w= — =
= + — — =
= — ≤ ≤ = c(Vs, Vt).
Теперь нужно показать,что существуют некоторые поток φи разрез (Vs, Vt),для которых величина потока равняется пропускной способности разреза. Каквидно, все потоки от Vsдо Vtограничены и среди них можно выбрать максимальный поток φ. С её помощью определим разрез (Vs,Vt), для которого
= c(Vs,Vt), = 0.
Определиммножество Vs рекуррентно:
1) vs Vs.
2) Если, vs Vs дуга eидёт из вершины vi вкакую-либо вершину vj и φ(e) Vs.
3) Если vi Vs,дуга e идёт из вершины vrв вершину vi и φ(e), то vj Vs.
Шаг 1)построения множества Vsозначает, что источник vsпринадлежит построенной стороне разреза. Покажем, что сток тогда лежит надругой стороне разреза – vt Vt = V/Vs.Допустим противоположное: пусть vt Vs.Тогда существует “неориентированная” цепь, которая идёт из источника vs в сток vt, такая, что для каждойдуги ei цепи с направлением,совпадающим с ориентацией “от источника к стоку” > 0.
Обозначимчерез l1 = min{c(ej) — c(ei)} все дуги eiцепи с направлением, совпадающим с ориентацией “отисточника к стоку”, l2= min{φ(ei)} все дуги eiцепи с направлением, несовпадающим с ориентацией “от источника к стоку”, l= min(l1, l2). Поток φ можно увеличить на l, увеличив на lпоток на дугах цепи,ведущих “от стока к источнику”. Это противоречит тому, что величина потока φ максимальная величина допустимогопотока из вершины vsв вершину vt.2.4. Алгоритм Форда-Фалкерсона
Доказательствотеоремы 1 даёт алгоритм для построения минимального разреза (Vs, Vt), который отделяет vsот vt, и максимальный поток φот vsдо vt. Этот алгоритм былпредложен Л. Фордом и Д. Фалкерсоном. Алгоритм начинает работу с известногодопустимого потока φ (например,с нулевого). Потом расчеты развиваются в виде последовательности “расстановкипометок” (операция А), каждая из которых приводит к потоку с большей величиной(операция Б), или же завершается выводом, что рассмотренный поток максимален.
Будемпредполагать, что пропускные способности cjдуг сети целые числа.
Операция А(расстановка пометок). Каждая вершина может находиться в одном из трёхсостояний: вершине приписана пометка и вершина просмотрена (то есть она имеетпометку и все смежные с ней вершины “обработаны”), вершина помечена, но непросмотрена, вершина не помечена. Пометка вершины viимеет один из двух видов:(+vj, l)или (-vj, l).Часть +vjпометки первого типапоказывает, что поток допускает увеличение вдоль дуги (vj, vi) на величину l.Часть -vjпометки второго типапоказывает, что поток допускает уменьшения вдоль дуги (vi, vj) на величину l.Сначала все вершины не имеют пометок.
Шаг 1.Источнику vsприсваивается пометка (+,vsпомечена, но не “просмотрена”.
Шаг 2.Возьмём произвольную помеченную, но не просмотренную вершину. Пусть оно имеетпометку (vr, l(vj)). “Просмотрим” её, тоесть просмотрим все вершины, смежные с ней, и пометем те из них, которые не помечены.
Всемнепомеченным вершинам vj,в которые входят дуги er изvi и для которых φ(еr)
Всемнепомеченным вершинам vj,из которых выходят дуги erв xi и для которых φ(er) > 0, приписываем пометку (-vi, l(vj)), где