Размещено на http://www.allbest.ru/

Поиск максимальных потоков в сетях

ВВЕДЕНИЕ

Начало теории графов все единодушно относят к 1736 г., когда Эйлер не только решил популярную в то время задачу о кенигсбергских мостах, но и нашёл критерий существования в графе специального маршрута (эйлерова цикла, как теперь его называют). Однако этот результат более ста лет оставался единственным результатом теории графов. Лишь в середине XIX века инженер-электрик Г.Кирхгофф разработал теорию деревьев для исследования электрических цепей. А математик А. Кэли в связи с описанием строения углеводородов решил перечислительные задачи для трёх типов деревьев. К этому же периоду относится появление знаменитой проблемы четырёх красок.

Родившись при решении головоломок и занимательных игр (задачи о шахматном коне, о ферзях, “кругосветное путешествие”, задачи о свадьбах и гаремах и т. п.), теория графов в настоящее время стала простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. В виде графов можно, например, интерпретировать схемы дорог и электрические цепи, географические карты и молекулы химических соединений, связи между людьми и группами людей.

За последние десятилетия теория графов превратилась в один из наиболее бурно развивающихся разделов математики. Это вызвано запросами стремительно расширяющейся области приложений. В теоретико-графовых терминах формулируется большое число задач, связанных с дискретными объектами. Рассмотрим примеры некоторых практических задач.

1. «Транспортные» задачи, в которых вершинами графа являются пункты, а ребрами - дороги (автомобильные, железные и др.) или другие транспортные (например, авиационные) маршруты. Другой пример - сети снабжения (энергоснабжения, газоснабжения, снабжения товарами и т.д.), в которых вершинами являются пункты производства и потребления, а ребрами - возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т.д.). Соответствующий класс задач оптимизации потоков грузов, размещения пунктов производства и потребления и т.д., иногда называется задачами обеспечения или задачами о размещении. Их подклассом являются задачи о грузоперевозках.

2. «Технологические задачи», в которых вершины отражают производственные элементы (заводы, цеха, станки и т.д.), а дуги - потоки сырья, материалов и продукции между ними, заключаются в определении оптимальной загрузки производственных элементов и обеспечивающих эту загрузку потоков.

3. Обменные схемы, являющиеся моделями таких явлений как бартер, взаимозачеты и т.д. Вершины графа при этом описывают участников обменной схемы (цепочки), а дуги - потоки материальных и финансовых ресурсов между ними. Задача заключается в определении цепочки обменов, оптимальной с точки зрения, например, организатора обмена и согласованной с интересами участников цепочки и существующими ограничениями.

4. Управление проектами. С точки зрения теории графов проект - совокупность операций и зависимостей между ними. Хрестоматийным примером является проект строительства некоторого объекта. Совокупность моделей и методов, использующих язык и результаты теории графов и ориентированных на решение задач управления проектами, получила название календарно-сетевого планирования и управления (КСПУ). В рамках КСПУ решаются задачи определения последовательности выполнения операций и распределения ресурсов между ними, оптимальных с точки зрения тех или иных критериев (времени выполнения проекта, затрат, риска и др.).

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

6. Модели организационных структур, в которых вершинами являются элементы организационной системы, а ребрами или дугами - связи (информационные, управляющие, технологические и др.) между ними.

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

1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕОРИИ ГРАФОВ

1.1 Понятие графа

Пусть V - непустое множество, V ⁽²⁾ - множество всех его двухэлементных подмножеств. Пара (V, E), где Е - произвольное подмножество множества V ⁽²⁾, называется графом (неориентированным графом).

Элементы множества 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 - множество вершин, А - множество ориентированных рёбер, которые называются дугами, АV². Если а = (v₁, v₂) - дуга, то вершины v₁ и v₂ называются её началом и концом соответственно. Если граф ориентированный, его обозначают .

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

Если у ребра начало и конец совпадают, то такое ребро называют петлёй.

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, б), такие рёбра называются кратными. Этот случай соответствует наличию нескольких одинаковых пар (v_i,v_j) E(G). Граф, который содержит кратные рёбра, называется мультиграфом. Ребро может соединять некоторую вершину саму с собою (рис. 1.2, в), такое ребро называется петлёй. Этот случай соответствует наличию в множестве Е пар вида (v,v). Граф с петлями и кратными рёбрами называется псевдографом. Конечный неориентированный граф без петель и кратных рёбер называется обычным.

а б в

Рисунок 1.2. Графы: а) - обычный, б) - с кратными рёбрами, в) - с петлёй

1.4 Элементы графов

Путь - это последовательность рёбер e₁, e₂, …, e_m, такая, что рёбра e_i, e_i+1 имеют общую вершину. Число рёбер называется длинной пути. Если ни одна из вершин не появляется больше одного раза, то путь называется простым. Понятно, что в простом пути ни одно ребро не используется дважды.

Путь называется циклом, если его начальная вершина совпадает с конечной; простым циклом, если это не выполняется для других вершин.

Чередующаяся последовательность v₁, e₁, v₂, e₂, …, e_l,v_l+1 вершин и рёбер графа, такая, что e_i = v_iv_i+1 (i = 1, l), называется маршрутом. Если v₁ = v_l+1, то маршрут замкнутый, иначе открытый.

Маршрут называется цепью, если все его рёбра различны, и простой цепью, если все вершины, кроме, возможно, крайних, различны. В цепи вершины v₀ и v_k называются концами цепи. Цепь, которая соединяет вершины v_i и v_j, обозначается .

Для орграфов цепь называется путём, а цикл - контуром.

Две вершины в графе называются связными, если существует соединяющая их (простая) цепь. Граф, у которого все вершины связны, называется связным. Ориентированный граф называется сильно связным, если для любых двух вершин существует ориентированный путь, который соединяет их.

1.5 Представление графов с помощью матриц

1.5.1 Матрицы инцидентности и списки рёбер

Задать граф, значит, задать множество его вершин и рёбер, а также отношение инцидентности. Когда граф G - конечный, для описания его вершин и рёбер достаточно их занумеровать. Пускай v₁, v₂,…, v_n - вершины графа G; e₁, e₂,…, e_m - его рёбра. Отношение инцидентности можно обозначить матрицей , которая имеет m строк и n столбцов. Столбцы соответствуют вершинам графа, а строки - его рёбрам. Если ребро е_і является инцидентным вершине v_j, то , в другом случае . Это матрица инцидентности обычного графа G, являющаяся одним из способов его определения (для графа на рис. 1.3), она задана в табл. 2, а.



Рис. 1.3. Обычный граф

В матрице инцидентности ориентированного графа G, если вершина v_j - начало ребра e_i, то ; если v_j - конец e_i, то ; если e_i - петля, а v_j - инцидентная ей вершина, , где б - любое число, отличное от 1, 0 и -1, в других случаях (пример - табл. 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-м столбце, соответствует строк списка ребер (при =0 нет ни одной строки), в каждом из которых записываются номера і, j. Для неориентированного графа эти строки соответствуют только элементам названного выше верхнего правого треугольника матрицы смежности, то есть элементам с , а для ориентированного графа нужно рассматривать все элементы .

Итак, граф можно представить разными способами. Он может быть изображён на рисунке, задан матрицей инцидентности, списком рёбер или матрицей смежности. Графический вид зависит от формы линий и взаимного расположения вершин. Вид матриц и списка рёбер зависит от нумерации вершин и рёбер графа.

2. ПОТОКИ В СЕТЯХ

2.1 Понятие сети

Сетью будем называть ориентированный связный граф без петель и параллельных рёбер. Потоки в неориентированных графах можно изобразить в виде потоков в соответствующих ориентированных. Поток в петле не влияет на распределение потока между вершинами. Рассмотрим сеть G = (V, E), |V | = n, |E| = m. Пускай каждой дуге е_j E поставлено в соответствие неотрицательное действительное число с_j , которое назовём пропускной способностью дуги е_j. Обозначим через v_i > V множество дуг, выходящих из вершины v_i, через V > v_i - множество дуг, заходящих в вершину v_i.

Потоком в сети G из вершины v_s в вершину v_t величины w называется неотрицательная, определенная на дугах е_j, функция ц: Е > R₊ {0}, такая, что

- = (1)

ц(е_j) ? c_j, j = 1, …, m.

Вершина v_s называется источником, вершина v_t - стоком, а остальные вершины - промежуточными узлами. Число Q(v_i) = - называется чистым потоком из вершины v_i относительно ц. Число ц(е) называется потоком по дуге е. Если “реальный” поток по дуге отрицательный, то его можно сделать положительным, выбрав соответствующую ориентацию дуги e. Систему уравнений (1) можно переписать в векторном виде:

ВФ = l,(2)

где В - матрица инцидентной размерности n m, Ф = (ц(e₁) … ц(e_m))^T, l = (0..0w0..0 - w0..0)^T. Поскольку ранг матрицы инциденций равен n - 1, то система уравнений (1) избыточна: . Также можно сказать, что поток ц из v_s в v_t величины w есть поток величины -w из v_t в v_s.

Пример

Рис. 2.1. Поток величины 3

Сеть, изображённая на рис. 2.1, состоит из пяти узлов и восьми дуг. Будем рассматривать поток от v₁ до v₅. Каждой дуге приписаны два числа: первое - величина потока по дуге, второе - пропускная способность дуги. Величина этого потока равна 3. Действительно,

Q(v₁) = 5 - 2 = 3,

Q(v₂) = 7 - (5 + 2) = 0,

Q(v₃) = -4 - 0 +2 + 2 = 0,(3)

Q(v₄) = -4 + 4 = 0,

Q(v₅) = 4 + 0 - 7 = -3.

Систему уравнений (3) можно записать в векторном виде ВФ = l (2):

, , .

2.2 Задача о максимальном потоке

На практике часто возникает проблема определения максимальной проводимости некоторой реальной сети: сети транспортной, сети ЭВМ, других. Иногда нужно определить самый дешёвый поток и т.д. Все эти и многие другие задачи решаются с помощью алгоритмов, которые работают на сетях. Так, алгоритм о максимальном потоке ищет максимально возможную пропускную способность сети, алгоритм минимальной стоимости - самый дешёвый поток. В данном разделе будем рассматривать задачу о максимальном потоке.

Задача заключается в нахождении такого множества потоков по дугам, чтобы величина Q(v_s) была максимальной.

Разрез S отделяет v_s от v_t, если вершины v_s, v_t принадлежат разным сторонам разреза: v_s V_s, v_t V_t, V = V_s V_t. Пропускной способностью с(S) разреза S называется сумма пропускных способностей дуг разреза, которые начинаются в V_s и заканчивается в V_t:

с(S) = .

2.3 Алгоритм размещения пометок для задачи о максимальном потоке

Алгоритм размещения пометок основан на следующей теореме.

Теорема 1.Теорема про максимальный поток и минимальный разрез. Для произвольной сети максимальная величина потока из v_s в v_t равняется минимальной пропускной способности разреза, который отделяет v_s от v_t.

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

Покажем, что величина w произвольного потока ц не превышает пропускной способности разреза (V_s,V_t), который отделяет v_s от v_t. Поскольку функция ц поток, то она удовлетворяет уравнению (1) сохранении потока:

- = w,

- = 0, v v_s, v _t,(2)

- = -w.

Сложим те уравнения из (2), которые соответствуют вершинам из V_s. Учитывая, что v_s V_s, v_t V_t, получаем:

w = - .

Всё множество вершин распадается на две стороны: V = V_s V_t. Получаем

w = - =

= + - - =

= - ? ? = c(V_s, V_t).

Теперь нужно показать, что существуют некоторые поток ц и разрез (V_s, V_t), для которых величина потока равняется пропускной способности разреза. Как видно, все потоки от V_s до V_t ограничены и среди них можно выбрать максимальный поток ц. С её помощью определим разрез (V_s, V_t), для которого

= c(V_s, V_t), = 0.

Определим множество V_s рекуррентно:

1) v_s V_s.

2) Если, v_s V_s дуга e идёт из вершины v_i в какую-либо вершину v_j и ц(e) < c(e), то v_j V_s.

3) Если v_i V_s, дуга e идёт из вершины v_r в вершину v_i и ц(e), то v_j V_s.

Шаг 1) построения множества V_s означает, что источник v_s принадлежит построенной стороне разреза. Покажем, что сток тогда лежит на другой стороне разреза - v_t V_t = V/V_s. Допустим противоположное: пусть v_t V_s. Тогда существует “неориентированная” цепь, которая идёт из источника v_s в сток v_t, такая, что для каждой дуги e_i цепи с направлением, совпадающим с ориентацией “от источника к стоку” > 0.

Обозначим через l₁ = min{c(e_j) - c(e_i)} все дуги e_i цепи с направлением, совпадающим с ориентацией “от источника к стоку”, l₂ = min{ц(e_i)} все дуги e_i цепи с направлением, не совпадающим с ориентацией “от источника к стоку”, l = min(l₁, l₂). Поток ц можно увеличить на l, увеличив на l поток на дугах цепи, ведущих “от стока к источнику”. Это противоречит тому, что величина потока ц максимальная величина допустимого потока из вершины v_s в вершину v_t.

2.4 Алгоритм Форда-Фалкерсона

Доказательство теоремы 1 даёт алгоритм для построения минимального разреза (V_s, V_t), который отделяет v_s от v_t, и максимальный поток ц от v_s до v_t. Этот алгоритм был предложен Л. Фордом и Д. Фалкерсоном. Алгоритм начинает работу с известного допустимого потока ц (например, с нулевого). Потом расчеты развиваются в виде последовательности “расстановки пометок” (операция А), каждая из которых приводит к потоку с большей величиной (операция Б), или же завершается выводом, что рассмотренный поток максимален.

Будем предполагать, что пропускные способности c_j дуг сети целые числа.

Операция А (расстановка пометок). Каждая вершина может находиться в одном из трёх состояний: вершине приписана пометка и вершина просмотрена (то есть она имеет пометку и все смежные с ней вершины “обработаны”), вершина помечена, но не просмотрена, вершина не помечена. Пометка вершины v_i имеет один из двух видов: (+v_j, l) или (-v_j, l). Часть +v_j пометки первого типа показывает, что поток допускает увеличение вдоль дуги (v_j, v_i) на величину l. Часть -v_j пометки второго типа показывает, что поток допускает уменьшения вдоль дуги (v_i, v_j) на величину l. Сначала все вершины не имеют пометок.

Шаг 1. Источнику v_s присваивается пометка (+, ). Вершина v_s помечена, но не “просмотрена”.

Шаг 2. Возьмём произвольную помеченную, но не просмотренную вершину. Пусть оно имеет пометку (v_r, l(v_j)). “Просмотрим” её, то есть просмотрим все вершины, смежные с ней, и пометем те из них, которые не помечены.

Всем непомеченным вершинам v_j, в которые входят дуги e_r из v_i и для которых ц(е_r) < c_r, приписываем пометку (+v_i, l(v_j)), где l(v_j) = min(l(v_i)), c_r - ц(е_r)).

Всем непомеченным вершинам v_j, из которых выходят дуги e_r в x_i и для которых ц(e_r) > 0, приписываем пометку (-v_i, l(v_j)), где l(v_j) = min(l(v_i)), ц(е_r)).

Теперь вершина v_i и помечена, и просмотрена, а вершина v_j, помечена, но не просмотрена.

Шаг 3. Повторять шаг 2 до тех пор, пока или сток - вершина v_t - будет помечена, или вершина v_t будет не помечена и никаких других пометок нельзя будет расставить. В первом случае переходим к операции Б, а во втором случае алгоритм заканчивает работу с максимальным потоком ц. Во втором случае множество помеченных и множество непомеченных вершин образовывают две стороны минимального сечения (V_s, V_t).

Операция Б (увеличения потока)

Шаг 4. Принять v = v_t и перейти к шагу 5.

Шаг 5. Если пометка в вершине v имеет вид (+z, l(v)), то изменить поток вдоль дуги (z, v) с ц(z, v) на ц(z, v) + l(v).

Если пометка в вершине v имеет вид (-z, l(v)), то изменить поток вдоль дуги (v, z) с ц(v, z) на ц(v, z) - l(v).

Шаг 6. Если z = v_s, то стереть все пометки и вернуться к шагу 1, чтобы снова начать расставлять пометки, но, используя уже улучшенный поток, который найден на шаге 5.

Если z ? v_s, то взять v = z и вернуться к шагу 5.

Рассмотрим на примере работу алгоритма Форда-Фалкерсона.

1. Возьмём поток, изображённый на рисунке 2.1 как начальный допустимый поток. Он имеет величину 3.

2. Присвоим источнику, вершине v₁, пометку (+, ). Вершина v₁ помечена, но не просмотрена.

3. Просмотрим вершины, смежные с вершиной v₁. Вершине v₂ присвоим пометку (+v₁, 1), а вершине v₃ - пометку (-v₁, 2) (ц(v₁, v₂) = 5 < 6 = c₁, ц(v₃, v₁) = 2 > 0). Вершина v₁ помечена и просмотрена, а вершины v₂ и v₃ помечены, но не пересмотрены.

4. Пересмотрим вершины, смежные с вершиной v₃. Из вершин, смежных с вершиной v₃, не помечены вершины v₄ и v₅. Вершине v₄ присвоим пометку (-v₃, 2), поскольку ц(v₄, v₃) = 4 > 0 и min(2, 4) = 2. Вершину v₅ не помечаем, поскольку ц(v₅, v₃) = 0.

5. Просмотрим вершины, смежные с вершиной v₂. Вершине v₅ присвоим пометку (+v₂, 1), поскольку ц(v₂, v₅) = 7 < 8 = c₅. Сток помечен. Переходим к операции В - увеличения потока.

6. Сток имеет пометку (+v₂, 1). Поэтому увеличиваем поток вдоль дуги (v₂, v₅) на 1.

7. Вершина v₂ имеет пометку (+v₁, 1). Поэтому увеличиваем поток вдоль дуги (v₁, v₂) на 1. Мы получили новый поток величины 4 (рис. 2.2).

Рис. 2.2. Поток величины 4

8. Стираем все пометки.

9. Присваиваем вершине v₁ пометку (+, ).

10. Пересматриваем вершины, смежные с вершиной v₁. Вершине v₃ присваиваем пометку (-v₁, 2). Вершину v₂ не помечаем, так как ц(v₁, v₂) = 6 = c(y₁).

11. Пересмотрим вершины, смежные с вершиной v₃. Вершине v₄ присвоим пометку (-v₃, 2), поскольку ц(v₄, v₃) = 4 > 0, l(v₃) = 2 и min(2, 4) = 2.

12. Пересмотрим вершины, смежные с вершиной v₄. Вершине v₅ присвоим пометку (-v₄, 2), так как ц(v₅, v₄) = 4 > 0, l(v₄) = 2 и min(2, 4) = 2. Сток помечен. Переходим к операции Б - увеличения потока.

13. Сток имеет пометку (-v₄, 2). Поэтому уменьшаем поток вдоль дуги (v₅, v₄) на 2.

14. Вершина v₄ имеет пометку (-v₃, 2). Поэтому уменьшаем поток вдоль дуги (v₄, v₃) на 2.

15. Вершина v₃ имеет пометку (-v₁, 2). Поэтому уменьшаем поток вдоль дуги (v₃, v₁) на 2. Мы получили новый поток величины 6 (рис. 2.3). По теореме 1 этот максимальный. Проверим это.

Рис. 2.3. Максимальный поток

16. Стираем все пометки.

17. Присваиваем вершине v₁ пометку (+, ).

18. Вершины, смежные вершине v₁, нельзя помечать, поскольку дуга (v₄, v₃) насыщенна - ц(v₁, v₂) = ц(е₁) = с(е₁) = 6, а через дугу (v₃, v₁) поток не передаётся. Сток остался не помеченным. Значит, полученный поток максимальный. Дуги (v₁, v₂) и (v₃, v₁) образуют минимальный разрез. Множество помеченных вершин образует ту его сторону, которая содержит источник: V_s = {v₁}. Непомеченные вершины образуют другую сторону разреза, который содержит сток: V_t = { v₂, v₃, v₄, v₅}. Построенный поток имеет вид ц(е₁) = 6, ц(е₅) = 8, ц(е₆) = 2, ц(е₄) = 2, ц(е₃) = 2, ц(е₂) = ц(е₇) = 0.

2.5 Графы со многими источниками и стоками

Алгоритм Форда-Фалкерсона примененный и для определения величины максимального потока между множеством вершин - источников и множеством вершин - стоков. Разобьем множество вершин на множество источников V₊ = {v V: Q(v) > 0}, которые образуют поток, множество стоков V_- = {v V: Q(v) < 0}, которые используют поток и множество промежуточных вершин V₀ = {v V: Q(v) = 0}, которые сохраняют поток . Преобразуем поток ц в поток, который имеет только один источник и только один сток, увеличив количество вершин в сети. Для этого добавим две новые вершины - “фиктивный” источник v_s и “фиктивный” сток v_t. Соединим вершину v_s со всеми действительными источниками. Этим дугам припишем поток, который образован соответствующим источником. А из каждого действительного стока направим дугу в “фиктивный” сток v_t. Этим дугам припишем поток, который используется соответствующим стоком. При этом пропускные способности добавленных дуг считаем бесконечными. В результате получаем сеть с одним источником и одним стоком. Применяя к ней алгоритм Форда-Фалкерсона, находим максимальный поток, который максимальный и для исходной сети.

Проиллюстирируем на примере преобразования сети с несколькими источниками и несколькими стоками до сети с одним источником и одним стоком.



Рис. 2.4. Сеть с двумя стоками

На рис. 2.4 изображена сеть с двумя источниками v₁ и v₃ и тремя стоками v₇, v₈, v₉ Q (v₁) = 5, Q (v₃) = 3, Q (v₇) = 3, Q (v₈) = 4, Q (v₉) = 1, Q (v₂) = Q (v₄) = Q (v₅) = Q (v₆) = 0

Преобразуем эту сеть в сеть с одним источником и одним стоком.

На рис. 2.5 изображена сеть уже с одним источником v_s и одним стоком v_t.

Рис. 2.5. Преобразованная сеть

2.6 Задача о многополюсном максимальном потоке

Рассмотрим задачу нахождения максимального потока для всех пар узлов в неориентированной сети. Эту задачу можно рассматривать как обобщение задачи с одним источником и одним стоком, которую можно решить, применяя алгоритм Форда-Фалкерсона для каждой пары вершин. Однако более эффективным является алгоритм, предложенный Р. Гомори и Т. Ху.

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

1. Выберем некоторые две вершины графа. Обозначим одну из них через v_s, а другую через v_t.

2. Применим алгоритм Форда-Фалкерсона и найдём максимальный поток из источника v_s в сток v_t. При этом множество помеченных вершин и множество непомеченных вершин образуют две стороны минимального разреза V_s и V_t.

3. Выберем две вершины графа v_i и v_j V_s.

4. Заменим дуги из минимального разреза (V_s, V_t) одной дугой, а вершины бока разреза, в котором не лежат вершины v_i , v_j, (например, V_t), - одной вершиной. Пропускную способность в таким образом определённой дуге примем равной пропускной способности разреза (V_s, V_t).

5. Положим: v_i = v_s, v_j = v_t и вернемся ко второму шагу. После того, как будет выбрана n - 1 пара вершин, мы определим все величин максимального потока для исходной сети. Основная идея алгоритма лежит в итеративном построении максимального остовного дерева, ветви которого соответствуют разрезам, а пропускные возможности ветвей равны пропускным способностям этих разрезов. Если бы мы применили алгоритм Форда-Фалкерсона к каждой паре вершин, то нам бы пришлось его применить раз. В алгоритме же Гомори-Ху максимальный поток между парой вершин определяется с помощью алгоритма расстановки пометок только n - 1 раз. Проиллюстрируем на примере алгоритм Гомори-Ху.

Рассмотрим сеть, изображённую на рис. 2.6.



Рис. 2.6. Сеть с пропускными возможностями

Числа, приписанные дугам, отвечают их пропускным способностям, отвечают их пропускным способностям. Нужно для каждой пары узлов сети определить величину максимального потока между ними. Эта задача решается при n - 1= 6 - 1 = 5 итераций алгоритма Гомори-Ху. Если алгоритм Форда-Фалкерсона расстановки пометок применялся бы к каждой паре узлов, то нужно было бы решить пятнадцать задач о максимальном потоке.

Реализуем алгоритм Гомори-Ху на данной сети.

1. Выберем вершины s = v₁ и t = v₂. Минимальную пропускную способность относительно источника s = v₁ и стока t = v₂ имеет разрез со сторонами V_s = {v₁, v₃, v₄, v₅, v₆} и V_t = {v₂}. По теореме 1 величина максимального потока между вершинами v₁ и v₂ равна пропускной способности разреза (V_s, V_t): w₁₂ = w₂₁ = c(V_s, V_t) = 2 + 3 = 5. Объединим вершины с V_s в одну вершину и соединим её с вершиной v₂ веткой с пропускной способностью 5 (рис. 2.7).

Рис. 2.7. Первый шаг алгоритма

2. Выберем вершины s = v₁ и t = v₃. Минимальную пропускную способность относительно источника s = v₁ и стока t = v₃ имеет разрез со сторонами V_s = {v₁} и V_t = {v₂, v₃, v₄, v₅, v₆}. По теореме 1 величина максимального потока между вершинами v₁ и v₃ равна пропускной способности разреза (V_s, V_t): w₁₃ = w₃₁ = c(V_s, V_t) = 2 + 4 + 2 = 8. Объединим вершины v₃, v₄, v₅, v₆ в одну вершину и соединим её с вершиной v₁ веткой с пропускной способностью 8 (рис. 2.8).

Рис 2.8. Второй шаг

3. Выберем вершины s = v₄ и t = v₃. Минимальную пропускную способность относительно источника s = v₄ и стока t = v₃ имеет разрез со сторонами V_s = {v₄} и V_t = {v₁, v₂, v₃, v₅, v₆}. По теореме 1 величина максимального потока между вершинами v₄ и v₃ равна пропускной способности разреза (V_s, V_t): w₄₃ = w₃₄ = c(V_s, V_t) = 2 + 5 + 4 = 11. Объединим вершины v₃, v₅, v₆ в одну вершину и соединим её с вершиной v₄ веткой с пропускной способностью 11 (рис. 2.9).

Рис. 2.9. Третий шаг

4. Выберем вершины s = v₅ и t = v₃. Минимальную пропускную способность относительно источника s = v₅ и стока t = v₃ имеет разрез со сторонами V_s = {v₅} и V_t = {v₁, v₂, v₃, v₄, v₆}. Величина максимального потока между вершинами v₅ и v₃ равна пропускной способности разреза (V_s, V_t): w₅₃ = w₃₅ = c(V_s, V_t) = 5 + 4 = 9. Объединим вершины v₃, v₆ в одну вершину и соединим её с вершиной v₅ веткой с пропускной способностью 9 (рис. 2.10).

Рис. 2.10. Четвёртый шаг

5. Выберем вершины s = v₆ и t = v₃. Минимальную пропускную способность относительно источника s = v₆ и стока t = v₃ имеет разрез со сторонами V_s = {v₆} и V_t = {v₁, v₂, v₃, v₄, v₅}.

Рис. 2.11. Остаточное дерево разрезов

Величина максимального потока между вершинами v₆ и v₃ равна пропускной способности разреза (V_s, V_t): w₆₃ = w₃₆ = c(V_s, V_t) = 5 + 6 + 4 = 15. Объединим вершину v₃ с вершиной v₆ веткой с пропускной способностью 15 (рис. 2.11).

По дереву перерезов, изображённого на рис. 2.11, легко найти остальные величины максимальных потоков. Например, v₁₆ = v₆₁ = 8, поскольку в цепи дерева разрезов, которая соединяет вершины v₁ и v₂, минимальная пропускная способность веток равна 8. Запишем величины максимальных потоков в виде матрицы:

.

Здесь на пересечение i-строки и j-столбца стоит величина максимального потока между вершинами v_i и v_j.

3. АВТОМАТИЗАЦИЯ ПОИСКА МАКСИМАЛЬНЫХ ПОТОКОВ В СЕТЯХ

3.1 Описание интерфейса программы

Главное окно программы содержит:

– таблицу для введения матрицы пропускных способностей;

– окно для просмотра матрицы максимального потока;

– поле для введения количества вершин;

– поля для введения начала и конца транспортной сети;

– поле для просмотра величины максимального потока;

– поле для введения номера вершины, пометку которой ми бы хотели увидеть;

– поля для просмотра этих пометок;

– кнопки “Количество вершин”, “Считать поток”, “Итерации”, “Начать сначала”, “Показать пометки” (рис. 3.1).

Рис. 3.1. Главное окно программы

3.2 Инструкция пользователя

Для запуска программы нужно запустить файл Max_potоk.exe.

Для поиска максимального потока в сети необходимо выполнить следующие действия:

1) ввести количество вершин сети (n) в поле “Количество” и нажать кнопку “Количество вершин”. В зависимости от количества вершин изменятся размеры таблиц, которыми задаются матрицы пропускных способностей и максимального потока сети. Количество вершин не может превышать 10. На рисунках 3.2(а) та 3.2(б) представлен вид этих таблиц при n=8 та n=3 соответственно.

а

б

Рис. 3.2.

2) заполнить матрицу пропускных способностей и указать номера вершин, которые будут началом (поле “s=”) и концом (поле “t=”) сети (рис. 3.3). Введение этих данных является обязательным условием для продолжения роботы программы;

Рис. 3.3.

3) рассчитать поток:

– если для выполнения этого этапа использовать кнопку “Считать поток”, то в таблице для представления матрицы максимального потока результат отображается немедленно, а в поле “Максимальный поток” при этом отображается величина максимального потока (рис. 3.4);

– если использовать кнопку “Итерации”, то в таблице для представления матрицы максимального потока результат отображается постепенно, в зависимости от насыщения и перераспределения потока в сети. Когда поток станет максимальным - кнопка больше не буде исполнять ни одних действий (рис. 3.5). Для выведения величины максимального потока в поле “Максимальный поток” нужно нажать кнопку “Считать поток”;

Рис. 3.4.



Рис. 3.5.

С помощью программы можно совершить дополнительные действия:

1) просмотреть пометки какой-либо вершины. Для этого нужно:

- задать вершину, для которой нужно вывести пометки (поле “Вершина”);

- нажать кнопку “Показать пометки”. При этом в поле “Предыдущая вершина” появится имя предыдущей вершины; в поле “Знак” появится знак “+”, если направление дуги совпадает с направлением потока, или “-“ - в противоположном случае; в поле “д” - величина увеличения потока по данной дуге (рис. 3.6);

Рис. 3.6.

2) сделать таблицу матрицы максимального потока пустой. Для этого нужно нажать кнопку “Начать сначала”, но таблица матрицы пропускных способностей останется неизменной (рис. 3.7);

3) работать с новой сетью и с новой матрицей пропускных способностей. Для этого нужно ввести новое количество вершин, нажать кнопку “Количество вершин” и обе матрицы и все поля станут пустыми.

Рис. 3.7.

3.3 Реализация программы

Сравним результаты вычислений с помощью программы и вручную. Для ручного способа вычислений будем использовать алгоритм Форда-Фалкерсона.

1. Возьмём поток, изображённый на рисунке 3.8 как начальный допустимый поток. Он имеет величину 3.

2. Присвоим источнику, вершине v₁, пометку (+, ?). Вершина v₁ помечена, но не просмотрена.

3. Просмотрим вершины, смежные с вершиной v₁. Вершине v₂ присвоим пометку (+v₁, 1), а вершине v₃ - пометку (+v₁, 1),т.к. ц(v₁, v₂) = 2 < 3 = с₁, ц(v₁, v₃) = 1 < 2 = с₂. Вершина v₁ помечена и просмотрена, а вершины v₂ и v₃ помечены, но не просмотрены.



Рис. 3.8. Поток величины 3

4. Просмотрим вершины, смежные с вершиной v₂. Из вершин, смежных с вершиной v₂, не помечена только вершина v₄. Вершине v₄ присваиваем пометку (+v₂, 1), поскольку ц(v₂, v₄) = 1 < 3 = с₃.

...