Поиск максимальных потоков в сетях
Министерство образования и науки Украины
Луганский национальный педагогический университет имени Тараса Шевченко
Кафедра алгебры и дискретной математики
Киршта Александр Михайлович
Поиск максимальных потоков в сетях
Магистерская работа по специальности 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.
а б
1.5.2. Матрицы смежности
Матрица смежности графа – это квадратная матрица δij равняется количеству рёбер, инцидентных i-й та j-й вершинам, для ориентированного графа этот элемент матрицы смежности соответствует количеству рёбер с началом в і-й вершине и концом в j-й. Таким образом, матрица смежности неориентированного графа симметрична (δij = δji), а ориентированного – необязательно. Если она всё-таки симметрична, то для каждого ребра ориентированного графа существует ребро, которое соединяет те же вершины, но направлено в противоположную сторону. Очевидно, ориентированный граф с симметричной матрицей смежности канонично соответствует неориентированному графу, который имеет ту же матрицу смежности.
Матрицы смежности рассмотренных выше графов (см. рис. 1.3 и 1.4) приведены в таблице 4.
Матрица смежности полностью определяет соответствующий неориентированный или ориентированный граф. Число его вершин равняется размерности матрицы n, i-й и j-й вершинам графа инцидентны ребер. Для неориентированного графа
а б
Количество их равняется сумме в этом треугольнике, то есть матрицы смежности. В обоих случаях с помощью матрицы смежности легко строится, например, список ребер, который определяет граф. Элементу матрицы смежности, расположенном в і-й строке и 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, v s, v t, (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) < c(e), то vj 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) < cr, приписываем пометку (+vi, l(vj)), где l(vj) = min(l(vi)), cr - φ(еr)).
Всем непомеченным вершинам vj, из которых выходят дуги er в xi и для которых φ(er) > 0, приписываем пометку (-vi, l(vj)), где l(vj) = min(l(vi)), φ(еr)).
Теперь вершина vi и помечена, и просмотрена, а вершина vj, помечена, но не просмотрена.
Шаг 3. Повторять шаг 2 до тех пор, пока или сток – вершина vt – будет помечена, или вершина vt будет не помечена и никаких других пометок нельзя будет расставить. В первом случае переходим к операции Б, а во втором случае алгоритм заканчивает работу с максимальным потоком φ. Во втором случае множество помеченных и множество непомеченных вершин образовывают две стороны минимального сечения (Vs, Vt).
Операция Б (увеличения потока)
Шаг 4. Принять v = vt и перейти к шагу 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 = vs, то стереть все пометки и вернуться к шагу 1, чтобы снова начать расставлять пометки, но, используя уже улучшенный поток, который найден на шаге 5.
Если z ≠ vs, то взять v = z и вернуться к шагу 5.
Рассмотрим на примере работу алгоритма Форда-Фалкерсона.
1. Возьмём поток, изображённый на рисунке 2.1 как начальный допустимый поток. Он имеет величину 3.
2. Присвоим источнику, вершине v1, пометку (+, v1 помечена, но не просмотрена.
3. Просмотрим вершины, смежные с вершиной v1. Вершине v2 присвоим пометку (+v1, 1), а вершине v3 – пометку (-v1, 2) (φ(v1, v2) = 5 < 6 = c1, φ(v3, v1) = 2 > 0). Вершина v1 помечена и просмотрена, а вершины v2 и v3 помечены, но не пересмотрены.
4. Пересмотрим вершины, смежные с вершиной v3. Из вершин, смежных с вершиной v3, не помечены вершины v4 и v5. Вершине v4 присвоим пометку (-v3, 2), поскольку φ(v4, v3) = 4 > 0 и min(2, 4) = 2. Вершину v5 не помечаем, поскольку φ(v5, v3) = 0.
5. Просмотрим вершины, смежные с вершиной v2. Вершине v5 присвоим пометку (+v2, 1), поскольку φ(v2, v5) = 7 < 8 = c5. Сток помечен. Переходим к операции В – увеличения потока.
6. Сток имеет пометку (+v2, 1). Поэтому увеличиваем поток вдоль дуги (v2, v5) на 1.
7. Вершина v2 имеет пометку (+v1, 1). Поэтому увеличиваем поток вдоль дуги (v1, v2) на 1. Мы получили новый поток величины 4 (рис. 2.2).
Рис. 2.2. Поток величины 4
8. Стираем все пометки.
9. Присваиваем вершине v1 пометку (+,
10. Пересматриваем вершины, смежные с вершиной v1. Вершине v3 присваиваем пометку (-v1, 2). Вершину v2 не помечаем, так как φ(v1, v2) = 6 = c(y1).
11. Пересмотрим вершины, смежные с вершиной v3. Вершине v4 присвоим пометку (-v3, 2), поскольку φ(v4, v3) = 4 > 0, l(v3) = 2 и min(2, 4) = 2.
12. Пересмотрим вершины, смежные с вершиной v4. Вершине v5 присвоим пометку (-v4, 2), так как φ(v5, v4) = 4 > 0, l(v4) = 2 и min(2, 4) = 2. Сток помечен. Переходим к операции Б – увеличения потока.
13. Сток имеет пометку (-v4, 2). Поэтому уменьшаем поток вдоль дуги (v5, v4) на 2.
14. Вершина v4 имеет пометку (-v3, 2). Поэтому уменьшаем поток вдоль дуги (v4, v3) на 2.
15. Вершина v3 имеет пометку (-v1, 2). Поэтому уменьшаем поток вдоль дуги (v3, v1) на 2. Мы получили новый поток величины 6 (рис. 2.3). По теореме 1 этот максимальный. Проверим это.
Рис. 2.3. Максимальный поток
16. Стираем все пометки.
17. Присваиваем вершине v1 пометку (+, ).
18. Вершины, смежные вершине v1, нельзя помечать, поскольку дуга (v4, v3) насыщенна – φ(v1, v2) = φ(е1) = с(е1) = 6, а через дугу (v3, v1) поток не передаётся. Сток остался не помеченным. Значит, полученный поток максимальный. Дуги (v1, v2) и (v3, v1) образуют минимальный разрез. Множество помеченных вершин образует ту его сторону, которая содержит источник: Vs = {v1}. Непомеченные вершины образуют другую сторону разреза, который содержит сток: Vt = { v2, v3, v4, v5}. Построенный поток имеет вид φ(е1) = 6, φ(е5) = 8, φ(е6) = 2, φ(е4) = 2, φ(е3) = 2, φ(е2) = φ(е7) = 0.
2.5. Графы со многими источниками и стоками
Алгоритм Форда-Фалкерсона примененный и для определения величины максимального потока между множеством вершин – источников и множеством вершин – стоков. Разобьем множество вершин на множество источников V+ = {v V: Q(v) > 0}, которые образуют поток, множество стоков V- = {v V: Q(v) < 0}, которые используют поток и множество промежуточных вершин V0 = {v V: Q(v) = 0}, которые сохраняют поток . Преобразуем поток φ в поток, который имеет только один источник и только один сток, увеличив количество вершин в сети. Для этого добавим две новые вершины – “фиктивный” источник vs и “фиктивный” сток vt. Соединим вершину vs со всеми действительными источниками. Этим дугам припишем поток, который образован соответствующим источником. А из каждого действительного стока направим дугу в “фиктивный” сток vt. Этим дугам припишем поток, который используется соответствующим стоком. При этом пропускные способности добавленных дуг считаем бесконечными. В результате получаем сеть с одним источником и одним стоком. Применяя к ней алгоритм Форда-Фалкерсона, находим максимальный поток, который максимальный и для исходной сети.
Проиллюстирируем на примере преобразования сети с несколькими источниками и несколькими стоками до сети с одним источником и одним стоком.
Рис. 2.4. Сеть с двумя стоками
На рис. 2.4 изображена сеть с двумя источниками v1 и v3 и тремя стоками v7, v8, v9 Q (v1) = 5, Q (v3) = 3, Q (v7) = 3, Q (v8) = 4, Q (v9) = 1, Q (v2) = Q (v4) = Q (v5) = Q (v6) = 0
Преобразуем эту сеть в сеть с одним источником и одним стоком.
На рис. 2.5 изображена сеть уже с одним источником vs и одним стоком vt.
Рис. 2.5. Преобразованная сеть
2.6. Задача о многополюсном максимальном потоке
Рассмотрим задачу нахождения максимального потока для всех пар узлов в неориентированной сети. Эту задачу можно рассматривать как обобщение задачи с одним источником и одним стоком, которую можно решить, применяя алгоритм Форда-Фалкерсона для каждой пары вершин. Однако более эффективным является алгоритм, предложенный Р. Гомори и Т. Ху.
Алгоритм Гомори-Ху
1. Выберем некоторые две вершины графа. Обозначим одну из них через vs, а другую через vt.
2. Применим алгоритм Форда-Фалкерсона и найдём максимальный поток из источника vs в сток vt. При этом множество помеченных вершин и множество непомеченных вершин образуют две стороны минимального разреза Vs и Vt.
3. Выберем две вершины графа vi и vj Vs.
4. Заменим дуги из минимального разреза (Vs, Vt) одной дугой, а вершины бока разреза, в котором не лежат вершины vi , vj, (например, Vt), – одной вершиной. Пропускную способность в таким образом определённой дуге примем равной пропускной способности разреза (Vs, Vt).
5. Положим: vi = vs, vj = vt и вернемся ко второму шагу. После того, как будет выбрана n - 1 пара вершин, мы определим все величин максимального потока для исходной сети. Основная идея алгоритма лежит в итеративном построении максимального остовного дерева, ветви которого соответствуют разрезам, а пропускные возможности ветвей равны пропускным способностям этих разрезов. Если бы мы применили алгоритм Форда-Фалкерсона к каждой паре вершин, то нам бы пришлось его применить раз. В алгоритме же Гомори-Ху максимальный поток между парой вершин определяется с помощью алгоритма расстановки пометок только n - 1 раз. Проиллюстрируем на примере алгоритм Гомори-Ху.
Рассмотрим сеть, изображённую на рис. 2.6.
Рис. 2.6. Сеть с пропускными возможностями
Числа, приписанные дугам, отвечают их пропускным способностям, отвечают их пропускным способностям. Нужно для каждой пары узлов сети определить величину максимального потока между ними. Эта задача решается при n – 1= 6 – 1 = 5 итераций алгоритма Гомори-Ху. Если алгоритм Форда-Фалкерсона расстановки пометок применялся бы к каждой паре узлов, то нужно было бы решить пятнадцать задач о максимальном потоке.
Реализуем алгоритм Гомори-Ху на данной сети.
1. Выберем вершины s = v1 и t = v2. Минимальную пропускную способность относительно источника s = v1 и стока t = v2 имеет разрез со сторонами Vs = {v1, v3, v4, v5, v6} и Vt = {v2}. По теореме 1 величина максимального потока между вершинами v1 и v2 равна пропускной способности разреза (Vs, Vt): w12 = w21 = c(Vs, Vt) = 2 + 3 = 5. Объединим вершины с Vs в одну вершину и соединим её с вершиной v2 веткой с пропускной способностью 5 (рис. 2.7).
Рис. 2.7. Первый шаг алгоритма
2. Выберем вершины s = v1 и t = v3. Минимальную пропускную способность относительно источника s = v1 и стока t = v3 имеет разрез со сторонами Vs = {v1} и Vt = {v2, v3, v4, v5, v6}. По теореме 1 величина максимального потока между вершинами v1 и v3 равна пропускной способности разреза (Vs, Vt): w13 = w31 = c(Vs, Vt) = 2 + 4 + 2 = 8. Объединим вершины v3, v4, v5, v6 в одну вершину и соединим её с вершиной v1 веткой с пропускной способностью 8 (рис. 2.8).
Рис 2.8. Второй шаг
3. Выберем вершины s = v4 и t = v3. Минимальную пропускную способность относительно источника s = v4 и стока t = v3 имеет разрез со сторонами Vs = {v4} и Vt = {v1, v2, v3, v5, v6}. По теореме 1 величина максимального потока между вершинами v4 и v3 равна пропускной способности разреза (Vs, Vt): w43 = w34 = c(Vs, Vt) = 2 + 5 + 4 = 11. Объединим вершины v3, v5, v6 в одну вершину и соединим её с вершиной v4 веткой с пропускной способностью 11 (рис. 2.9).
Рис. 2.9. Третий шаг
4. Выберем вершины s = v5 и t = v3. Минимальную пропускную способность относительно источника s = v5 и стока t = v3 имеет разрез со сторонами Vs = {v5} и Vt = {v1, v2, v3, v4, v6}. Величина максимального потока между вершинами v5 и v3 равна пропускной способности разреза (Vs, Vt): w53 = w35 = c(Vs, Vt) = 5 + 4 = 9. Объединим вершины v3, v6 в одну вершину и соединим её с вершиной v5 веткой с пропускной способностью 9 (рис. 2.10).
Рис. 2.10. Четвёртый шаг
5. Выберем вершины s = v6 и t = v3. Минимальную пропускную способность относительно источника s = v6 и стока t = v3 имеет разрез со сторонами Vs = {v6} и Vt = {v1, v2, v3, v4, v5}.
Рис. 2.11. Остаточное дерево разрезов
Величина максимального потока между вершинами v6 и v3 равна пропускной способности разреза (Vs, Vt): w63 = w36 = c(Vs, Vt) = 5 + 6 + 4 = 15. Объединим вершину v3 с вершиной v6 веткой с пропускной способностью 15 (рис. 2.11).
По дереву перерезов, изображённого на рис. 2.11, легко найти остальные величины максимальных потоков. Например, v16 = v61 = 8, поскольку в цепи дерева разрезов, которая соединяет вершины v1 и v2, минимальная пропускная способность веток равна 8. Запишем величины максимальных потоков в виде матрицы:
.
Здесь на пересечение i-строки и j-столбца стоит величина максимального потока между вершинами vi и vj.
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. Присвоим источнику, вершине v1, пометку (+, ∞). Вершина v1 помечена, но не просмотрена.
3. Просмотрим вершины, смежные с вершиной v1. Вершине v2 присвоим пометку (+v1, 1), а вершине v3 – пометку (+v1, 1),т.к. φ(v1, v2) = 2 < 3 = с1, φ(v1, v3) = 1 < 2 = с2. Вершина v1 помечена и просмотрена, а вершины v2 и v3 помечены, но не просмотрены.
Рис. 3.8. Поток величины 3
4. Просмотрим вершины, смежные с вершиной v2. Из вершин, смежных с вершиной v2, не помечена только вершина v4. Вершине v4 присваиваем пометку (+v2, 1), поскольку φ(v2, v4) = 1 < 3 = с3.
5. Просмотрим вершины, смежные с вершиной v3. Из вершин, смежных с вершиной v3, не помечена только вершина v5. Вершине v5 присваиваем пометку (+v3, 1), поскольку φ(v3, v5) = 2 < 4 = с4.
6. Просмотрим вершины, смежные с вершиной v4. Смежной и непомеченной является вершина v6. Присваиваем ей пометку (+v4, 1), поскольку φ(v4, v6) = 1 < 4 = с5.
7. Просмотрим вершины, смежные с вершиной v5. Смежной и непомеченной является вершина v7. Присваиваем ей пометку (+v5, 1), поскольку φ(v5, v7) = 2 < 3 = с6.
8. Просмотрим вершины, смежные с вершиной v6. Смежной и непомеченной является вершина v8. Присваиваем ей пометку (+v6, 1), поскольку φ(v6, v8) = 2 < 5 = с7. Сток помечен. Переходим к операции Б – увеличению потока.
9. Сток имеет пометку (+v6, 1). Поэтому увеличиваем поток по дуге (v6, v8) на 1.
10. Вершина v6 имеет пометку (+v4, 1). Поэтому увеличиваем поток по дуге (v4, v6) на 1.
11. . Вершина v4 имеет пометку (+v2, 1). Поэтому увеличиваем поток по дуге (v2, v4) на 1.
12. . Вершина v2 имеет пометку (+v1, 1). Поэтому увеличиваем поток по дуге (v1, v2) на 1. Мы получили новый поток величины 4 (рис. 3.9).
Рис. 3.9. Поток величины 4
13. Стираем все пометки.
14. Присваиваем вершине v1 пометку (+, ∞).
15. Просмотрим вершины, смежные с вершиной v1. Вершину v2 не помечаем, поскольку φ(v1, v2) = 3 = c(e1), а вершине v3 присваиваем пометку (+v1, 1).
16. Просмотрим вершины, смежные с вершиной v3. Вершине v2 присваиваем пометку (-v3, 1), поскольку φ(v2, v3) = 1 > 0, l(v) = 1 и min(1, 1) = 1, а вершине v5 припишем пометку (+v3, 1), так как φ(v3, v5) = 2 < 4 = c8.
17. Просмотрим вершины, смежные с вершиной v4. Вершине v6 присваиваем пометку (+v4, 1), поскольку φ(v4, v6) = 3 < 5 = с9.
18. Просмотрим вершины, смежные с вершиной v5. Вершине v7 присваиваем пометку (+v5, 1), поскольку φ(v5, v7) = 2 < 3 = с10.
19. Просмотрим вершины, смежные с вершиной v6. Вершине v8 присваиваем пометку (+v6, 1), поскольку φ(v6, v8) = 3 < 5 = с11. Сток помечен. Переходим к операции Б – увеличению потока.
20. Сток имеет пометку (+v6, 1). Поэтому увеличиваем поток по дуге (v6, v8) на 1.
21. Вершина v6 имеет пометку (+v4, 1). Поэтому увеличиваем поток по дуге (v4, v6) на 1.
22. Вершина v4 имеет пометку (+v2, 1). Поэтому увеличиваем поток по дуге (v2, v4) на 1.
23. Вершина v2 имеет пометку (-v3, 1). Поэтому уменьшаем поток по дуге (v2, v3) на 1.
24. Вершина v3 имеет пометку (+v1, 1). Поэтому увеличиваем поток по дуге (v1, v3) на 1. Получили новый поток величины 5 (рис. 3.10).
Рис. 3.10. Поток величины 5
25. Стираем все пометки.
26. Присваиваем вершине v1 пометку (+, ∞).
27. Вершины, смежные вершине v1, нельзя пометить, поскольку дуга (v1, v2) насыщена – φ(v1, v2) = φ(е1) = с(е1) = 3, и дуга (v1, v3) тоже насыщена – φ(v1, v3) = φ(е2) = с(е2) = 2. Сток остался непомеченным. Значит, полученный поток максимален.
А теперь найдём максимальный поток с помощью программы. Для этого введём матрицу пропускных способностей в соответствующие поля программы. Матрица имеет следующий вид:
Результат вычислений оказался тем же. Мы получили максимальный поток величины 5 (рис. 3.11).
Рис. 3.11.
3.4. Описание программного кода
Прикладная программа Max_potоk написана языком Object Pascal в интегрированной среде Delphi7.
Окно программы (Form1: TForm) содержит такие компоненты:
- текстовые поля (Eij: TEdit ; Inij: TEdit (i,j = 1..10));
– компоненты (STy: TStaticText (y = 1..10), OSTx: TStaticText (x = 1..10), VSTz: TStaticText (z = 1..10), OVSTe: TStaticText (e = 1..10), StaticTextij: TStaticText (i = 4, j = 1..4));
- надписи (Label1, Label2, Label3: TLabel);
- панель группировки компонентов (GB1: TGroupBox);
- кнопки (Buttonk: TButton (k = 1..5)).
В программе отслеживается 7 действий (табл. 6).
Таблица 6
|
Название действия |
Назначение |
|
TButton1.Click |
Рассчитывает максимальный поток |
|
TButton2.Click |
Создаёт таблицы матриц пропускных способностей и потока заданной размерности |
|
TButton3.Click |
Считает одну итерацию |
|
TButton4.Click |
Выводит пометки |
|
TButton5.Click |
Начинает итерацию заново |
|
TForm1.Create |
Задаёт высоту и ширину окна программы |
|
TForm1.Close |
Совершает затухание формы при её закрытии |
Предназначение текстовых полей приведено в таблице 7.
|
Метка поля |
Название поля |
Предназначение |
|
Количество |
Col |
Задаётся количество вершин сети |
|
s= |
SSS |
Задаётся источник сети |
|
t= |
TTT |
Задаётся сток сети |
|
Вершина |
р1 |
Задаётся вершина, пометки которой будут рассчитываться |
|
Предыдущая вершина |
р2 |
Выводятся пометки вершины |
|
Знак |
р3 |
|
|
d |
р4 |
|
|
Максимальный поток |
max |
Выводится максимальный поток сети |
|
Xij |
Inij |
Задаётся матрица пропускных способностей сети |
|
Xij |
Eij |
Выводится матрица потока в сети |
Таблица 7
ВЫВОДЫ
Решая жизненные практические задачи, мы неоднократно сталкиваемся с проблемой поиска максимальных потоков в сетях (поиск максимального потока машин в сети дорог без возникновения пробок, поиск максимального количества нефти, которую можно перекачать по трубопроводу и др.).
В данной работе изучалась эта проблема, была рассмотрена теория, которая изучает методы поиска максимальных потоков в сетях, изучен алгоритм поиска максимального потока (алгоритм Форда-Фалкерсона), в интегрированной среде Delphi было разработано дополнение, которое позволяет в удобной для пользователя форме найти максимальный поток в заданной сети.
Это дополнение может быть использовано при проведении практических занятий по теме ”Теория графов” для студентов специальностей “Математика” и “Информатика” при изучении дисциплины “Дискретная математика”, а также для проверки тестовых заданий по этой теме.
ЛИТЕРАТУРА
1. Алгоритмы и программы решения задач на графах и сетях. Отв. ред. М.И. Нечепуренко. – Новосибирск: Наука. Сиб. отделение, 1990. – 513 с.
2. Андрійчук В.І., Комарницький М.Я., Іщук Ю.Б. Вступ до дискретної математики: Навчальний посібник. – Київ: Центр навчальної літератури, 2004. – 254 с.
3. Архангельский А.Я. Приемы программирования в Delphi. Версии 5 – 7. М.: ЗАО «Издательство БИНОМ», 2003.
4. Дискретна математика: Підручник/ Ю.М. Бардачов, Н.А. Соколова, В.Є. Ходаков; за ред. В.Є. Ходакова. – К.: Вища шк., 2002. – 287 с.: іл.
5. Дискретная математика: логика, группы, графы/ О.Е. Акимов. – 2-е изд., доп. – М.: Лаборатория Базовых Знаний, 2003. – 376 с.: ил.
6. Зыков А.А. Основы теории графов. – М.: Наука, 1987. – 381 с.
7. Климова Л.М. Delphi 7. Основы программирования. Решение типовых задач. Самоучитель – М.: КУДИЦ-ОБРАЗ, 2004. – 480 с.
8. Крістофідес Р. “Теория графов”. Переклад на російську мову “Мир” 1978.
9. Лекции по дискретной математике/ Ю.В. Капитонова, С.Л. Кривой, А.А. Летичевский и др. – СПб.: БХВ-Петербург, 2004. – 624 с.
10. Лекции по теории графов/ Емеличев В.А., Мельниченков О.И., Сарванов В.И., Тышкевич Р.И. – М.: Наука, Гл. ред. физ.-мат. лит., 1990. – 384 с.
11. Лекции по теории графов: Учебн. пособие. – М.: Наука, 1990. – 384 с.
12. Липский В. Комбинаторика для программистов: Пер. с польск. – М.: Мир, 1988. – 213 с.: ил.
13. Магрупов Т.М. Графы, сети, алгоритмы и их приложения/ Под ред. Ф.Б. Абуталиева; АН УсССР, Ин-т кибернетики с ВЦ УзНПО “Кибернетика”: – Ташкент: Фан, 1990. – 120 с.
14. Математическое программирование (с элементами информационных технологий): Учеб. пособие для студ. нематемат. спец. вузов/ В.Р. Кулян, Е.А. Юнькова, А.Б. Жильцов. – К.: МАУП, 2000. – 124 с.: ил.
15. Мiхайленко В.М. Дискретна математика. – К.: Європейський ун-т, 2003. – 319.
16. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2004. – 302 с.: ил.
17. Седжвік Д. “Програмирование на С++. Часть 5. Алгоритмы на графах”. Київ, 2003.
18. Теория графов и её применение: сборник научных трудов/ Институт математики им. С.Л. Соболева. – Новосибирск, 1996. – 106 с.
19. Яблонский С.В. Введение в дискретную митематику. – М.: Наука, 1986. – 384 с.
ПРИЛОЖЕНИЕ
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Grids, DBGrids, AxCtrls, OleCtrls, VCF1, ComCtrls, StdCtrls;
type
TForm1 = class(TForm)
E11: TEdit; E21: TEdit; E31: TEdit; E41: TEdit; E51: TEdit; E61: TEdit;
E71: TEdit; E81: TEdit; E91: TEdit; E101: TEdit; E12: TEdit; E22: TEdit;
E32: TEdit; E42: TEdit; E52: TEdit; E62: TEdit; E72: TEdit; E82: TEdit;
E92: TEdit; E102: TEdit; E13: TEdit; E23: TEdit; E33: TEdit; E43: TEdit;
E53: TEdit; E63: TEdit; E73: TEdit; E83: TEdit; E93: TEdit; E103: TEdit;
E14: TEdit; E24: TEdit; E34: TEdit; E44: TEdit; E54: TEdit; E64: TEdit;
E74: TEdit; E84: TEdit; E94: TEdit; E104: TEdit; E15: TEdit; E25: TEdit;
E35: TEdit; E45: TEdit; E55: TEdit; E65: TEdit; E75: TEdit; E85: TEdit;
E95: TEdit; E105: TEdit; E16: TEdit; E26: TEdit; E36: TEdit; E46: TEdit;
E56: TEdit; E66: TEdit; E76: TEdit; E86: TEdit; E96: TEdit; E106: TEdit;
E17: TEdit; E27: TEdit; E37: TEdit; E47: TEdit; E57: TEdit; E67: TEdit;
E77: TEdit; E87: TEdit; E97: TEdit; E107: TEdit; E18: TEdit; E28: TEdit;
E38: TEdit; E48: TEdit; E58: TEdit; E68: TEdit; E78: TEdit; E88: TEdit;
E98: TEdit; E108: TEdit; E19: TEdit; E29: TEdit; E39: TEdit; E49: TEdit;
E59: TEdit; E69: TEdit; E79: TEdit; E89: TEdit; E99: TEdit; E109: TEdit;
E110: TEdit; E210: TEdit; E310: TEdit; E410: TEdit; E510: TEdit;
E610: TEdit; E710: TEdit; E810: TEdit; E910: TEdit; E1010: TEdit;
In11: TEdit; In21: TEdit; In31: TEdit; In41: TEdit; In51: TEdit;
In61: TEdit; In71: TEdit; In81: TEdit; In91: TEdit; In101: TEdit;
In12: TEdit; In22: TEdit; In32: TEdit; In42: TEdit; In52: TEdit;
In62: TEdit; In72: TEdit; In82: TEdit; In92: TEdit; In102: TEdit;
In13: TEdit; In23: TEdit; In33: TEdit; In43: TEdit; In53: TEdit;
In63: TEdit; In73: TEdit; In83: TEdit; In93: TEdit; In103: TEdit;
In14: TEdit; In24: TEdit; In34: TEdit; In44: TEdit; In54: TEdit;
In64: TEdit; In74: TEdit; In84: TEdit; In94: TEdit; In104: TEdit;
In15: TEdit; In25: TEdit; In35: TEdit; In45: TEdit; In55: TEdit;
In65: TEdit; In75: TEdit; In85: TEdit; In95: TEdit; In105: TEdit;
In16: TEdit; In26: TEdit; In36: TEdit; In46: TEdit; In56: TEdit;
In66: TEdit; In76: TEdit; In86: TEdit; In96: TEdit; In106: TEdit;
In17: TEdit; In27: TEdit; In37: TEdit; In47: TEdit; In57: TEdit;
In67: TEdit; In77: TEdit; In87: TEdit; In97: TEdit; In107: TEdit;
In18: TEdit; In28: TEdit; In38: TEdit; In48: TEdit; In58: TEdit;
In68: TEdit; In78: TEdit; In88: TEdit; In98: TEdit; In108: TEdit;
In19: TEdit; In29: TEdit; In39: TEdit; In49: TEdit; In59: TEdit;
In69: TEdit; In79: TEdit; In89: TEdit; In99: TEdit; In109: TEdit;
In110: TEdit; In210: TEdit; In310: TEdit; In410: TEdit; In510: TEdit;
In610: TEdit; In710: TEdit; In810: TEdit; In910: TEdit; In1010: TEdit;
ST1: TStaticText; ST2: TStaticText; ST3: TStaticText; ST4: TStaticText;
ST5: TStaticText; ST6: TStaticText; ST7: TStaticText; ST8: TStaticText;
ST9: TStaticText; ST10: TStaticText; OST1: TStaticText;
OST4: TStaticText; OST3: TStaticText; OST2: TStaticText;
OST5: TStaticText; OST6: TStaticText; OST7: TStaticText;
OST8: TStaticText; OST9: TStaticText; OST10: TStaticText;
VST1: TStaticText; VST2: TStaticText; VST3: TStaticText;
VST4: TStaticText; VST5: TStaticText; VST6: TStaticText;
VST7: TStaticText; VST8: TStaticText; VST9: TStaticText;
VST10: TStaticText; OVST1: TStaticText; OVST2: TStaticText;
OVST3: TStaticText; OVST4: TStaticText; OVST5: TStaticText;
OVST6: TStaticText; OVST7: TStaticText; OVST8: TStaticText;
OVST9: TStaticText; OVST10: TStaticText; SSS: TEdit;
StaticText41: TStaticText; TTT: TEdit; StaticText42: TStaticText;
Button1: TButton; StaticText43: TStaticText; StaticText44: TStaticText;
col: TEdit; label1: TLabel; Button2: TButton; Label2: TLabel;
max: TEdit; Button3: TButton; GB1: TGroupBox; Label3: TLabel;
Label4: TLabel; Label5: TLabel; Label6: TLabel; p1: TEdit;
p2: TEdit; p3: TEdit; p4: TEdit; Button4: TButton; Button5: TButton;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure FormClose(Sender: TObject; var Action: TCloseAction);
procedure FormCreate(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
procedure Button5Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
function min(x,y: double): double;
const p1=10;
type
sign=(minus,plus);
ibool=0..1;
Rec=record
s:sign; {направление дуги}
n:1..p1; {предшествующая вершина в аугментальной цепи}
delta:double; {величина возможного увеличения потока}
end;
var
Form1: TForm1;
F: array of array of double;
P: array of Rec;
implementation
{$R *.dfm}
function min(x,y: double): double;
begin
if x < y then
Result := x
else
Result := y;
end;
procedure TForm1.Button1Click(Sender: TObject);
label M;
const p1=10;
type
sign=(minus,plus);
ibool=0..1;
Rec=record
s:sign; {направление дуги}
n:1..p1; {предшествующая вершина в аугментальной цепи}
delta:double; {величина возможного увеличения потока}
end;
var i,j: integer;
del,ch:double;
C,F: array of array of double;
P: array of Rec;
N,S: array of ibool;
a:ibool;
pp,s1,t1,x: byte;
input,output:array of array of TEdit;
begin
pp:=StrToInt(col.Text);
SetLength(input,pp);
SetLength(output,pp);
SetLength(C,pp);
SetLength(F,pp);
SetLength(P,pp);
SetLength(N,pp);
SetLength(S,pp);
for i:=0 to pp-1 do
begin
SetLength(input[i],pp);
SetLength(output[i],pp);
SetLength(C[i],pp);
SetLength(F[i],pp);
end;
for i:=1 to pp do
for j:=1 to pp do
begin
F[i-1,j-1] := 0; {вначале поток нулевой}
input[i-1,j-1]:=FindComponent(Format('In%d%d',[i,j])) as TEdit;
output[i-1,j-1]:=FindComponent(Format('E%d%d',[i,j])) as TEdit;
if input[i-1,j-1].Text<>'' then C[i-1,j-1]:=StrToFloat(input[i-1,j-1].Text)
else C[i-1,j-1]:=0;
end;
s1 := StrToInt(SSS.Text[2]);
if (s1=1) and (length(SSS.Text)=3) then
s1:=10;
t1 := StrToInt(TTT.Text[2]);
if (t1=1) and (length(TTT.Text)=3) then
t1:=10;
M: {итерация увеличения потока}
for i:=1 to pp do
begin
S[i-1] := 0;
N[i-1] := 0;
with P[i-1] do
begin
//s := null;
//n := nil;
delta := 0;
end;
end;
S[s1-1]:=1;
with P[s1-1] do
begin
s:=plus;
n:=s1;
end;
repeat
a:=0; {признак расширения S}
for i:=1 to pp do
begin
if (S[i-1]=1) and (N[i-1]=0) then
begin
for j:=1 to pp do
begin
if C[i-1,j-1]<>0 then
begin
if (S[j-1]=0) and (F[i-1,j-1] < C[i-1,j-1]) then
begin
S[j-1] := 1;
with P[j-1] do
begin
s := plus;
n := i;
if i=s1 then delta := C[i-1,j-1] - F[i-1,j-1]
else delta := min(P[i-1].delta,C[i-1,j-1] - F[i-1,j-1]);
end;
a := 1;
end;
end;
if C[j-1,i-1]<>0 then
begin
if (S[j-1]=0) and (F[j-1,i-1]>0) then
begin
S[j-1] := 1;
with P[j-1] do
begin
s := minus;
n := i;
if i=s1 then delta := F[j-1,i-1]
else delta := min(P[i-1].delta,F[j-1,i-1]);
end;
a:=1;
end;
end;
end;
N[i-1] := 1;
end;
end;
if S[t1-1]<>0 then
begin
x:=t1;
del:=P[t1-1].delta;
while x<>s1 do
begin
if P[x-1].s=plus then
F[P[x-1].n-1,x-1]:=F[P[x-1].n-1,x-1]+del
else
F[x-1,P[x-1].n-1]:=F[x-1,P[x-1].n-1]-del;
x:=P[x-1].n
end;
goto M;
end;
until a=0;
ch:=0;
for i:=1 to pp do
begin
ch:=ch+F[s1-1,i-1];
for j:=1 to pp do
begin
if C[i-1,j-1]<>0 then
output[i-1,j-1].Text := FloatToStr(F[i-1,j-1])
else
output[i-1,j-1].Text := '';
end;
end;
max.Text := FloatToStr(ch);
end;
//----------------------------------------------------
procedure TForm1.Button2Click(Sender: TObject);
const p1=10;
var InG,InV,OutG,OutV :array[1..p1] of TStaticText;
i,pp,j: byte;
input,output:array[1..p1,1..p1] of TEdit;
begin
SSS.Text:='';
TTT.Text:='';
max.Text:='';
pp:=StrToInt(Col.Text);
SetLength(F,pp);
for i:=1 to pp do
begin
SetLength(F[i-1],pp);
for j:=1 to pp do
F[i-1,j-1] := 0;
end;
for i:=1 to p1 do
begin
InG[i] := FindComponent(Format('ST%d',[i])) as TStaticText;
InV[i] := FindComponent(Format('VST%d',[i])) as TStaticText;
OutG[i] := FindComponent(Format('OST%d',[i])) as TStaticText;
OutV[i] := FindComponent(Format('OVST%d',[i])) as TStaticText;
if i<=pp then
begin
InG[i].Visible:=true;
InV[i].Visible:=true;
OutG[i].Visible:=true;
OutV[i].Visible:=true;
end
else
begin
InG[i].Visible:=false;
InV[i].Visible:=false;
OutG[i].Visible:=false;
OutV[i].Visible:=false;
end;
for j:=1 to p1 do
begin
input[i,j] := FindComponent(Format('In%d%d',[i,j])) as TEdit;
output[i,j] := FindComponent(Format('E%d%d',[i,j])) as TEdit;
if (i<=pp) and (j<=pp) then
begin
input[i,j].Visible:=true;
output[i,j].Visible:=true;
input[i,j].Text:='';
output[i,j].Text:='';
end
else
begin
input[i,j].Visible:=false;
output[i,j].Visible:=false;
end;
end;
end;
end;
procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);
var
i, cavb : 0..255;
begin
if AlphaBlend=False then
begin
AlphaBlendValue:=255;
AlphaBlend:=True;
end;
cavb:=AlphaBlendValue;
for i := cavb downto 0 do
begin
AlphaBlendValue := i;
Application.ProcessMessages;
end
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
Form1.Height:=600;
Form1.Width:=800;
end;
procedure TForm1.Button3Click(Sender: TObject);
var i,j: integer;
del:double;
C: array of array of double;
N,S: array of ibool;
a:ibool;
pp,s1,t1,x: byte;
input,output:array of array of TEdit;
begin
p1.Text :='';
p2.Text :='';
p3.Text :='';
p4.Text :='';
pp:=StrToInt(col.Text);
SetLength(input,pp);
SetLength(output,pp);
SetLength(C,pp);
SetLength(P,pp);
SetLength(N,pp);
SetLength(S,pp);
for i:=0 to pp-1 do
begin
SetLength(input[i],pp);
SetLength(output[i],pp);
SetLength(C[i],pp);
end;
for i:=1 to pp do
for j:=1 to pp do
begin
input[i-1,j-1]:=FindComponent(Format('In%d%d',[i,j])) as TEdit;
output[i-1,j-1]:=FindComponent(Format('E%d%d',[i,j])) as TEdit;
if input[i-1,j-1].Text<>'' then C[i-1,j-1]:=StrToFloat(input[i-1,j-1].Text)
else C[i-1,j-1]:=0;
end;
s1 := StrToInt(SSS.Text[2]);
if (s1=1) and (length(SSS.Text)=3) then
s1:=10;
t1 := StrToInt(TTT.Text[2]);
if (t1=1) and (length(TTT.Text)=3) then
t1:=10;
for i:=1 to pp do
begin
S[i-1] := 0;
N[i-1] := 0;
with P[i-1] do
begin
//s := null;
//n := nil;
delta := 0;
end;
end;
S[s1-1]:=1;
with P[s1-1] do
begin
s:=plus;
n:=s1;
end;
repeat
a:=0; {признак расширения S}
for i:=1 to pp do
begin
if (S[i-1]=1) and (N[i-1]=0) then
begin
for j:=1 to pp do
begin
if C[i-1,j-1]<>0 then
begin
if (S[j-1]=0) and (F[i-1,j-1] < C[i-1,j-1]) then
begin
S[j-1] := 1;
with P[j-1] do
begin
s := plus;
n := i;
if i=s1 then delta := C[i-1,j-1] - F[i-1,j-1]
else delta := min(P[i-1].delta,C[i-1,j-1] - F[i-1,j-1]);
end;
a := 1;
end;
end;
if C[j-1,i-1]<>0 then
begin
if (S[j-1]=0) and (F[j-1,i-1]>0) then
begin
S[j-1] := 1;
with P[j-1] do
begin
s := minus;
n := i;
if i=s1 then delta := F[j-1,i-1]
else delta := min(P[i-1].delta,F[j-1,i-1]);
end;
a:=1;
end;
end;
end;
N[i-1] := 1;
end;
end;
if S[t1-1]<>0 then
begin
x:=t1;
del:=P[t1-1].delta;
while x<>s1 do
begin
if P[x-1].s=plus then
F[P[x-1].n-1,x-1]:=F[P[x-1].n-1,x-1]+del
else
F[x-1,P[x-1].n-1]:=F[x-1,P[x-1].n-1]-del;
x:=P[x-1].n
end;
Break;
end;
until a=0;
for i:=1 to pp do
begin
for j:=1 to pp do
begin
if C[i-1,j-1]<>0 then
output[i-1,j-1].Text := FloatToStr(F[i-1,j-1])
else
output[i-1,j-1].Text := '';
end;
end;
end;
procedure TForm1.Button4Click(Sender: TObject);
var s1,ver: byte; // Вершина
begin
p4.Font.Name := 'MS Sans Serif';
ver := StrToInt(p1.Text[2]);
if (ver=1) and (length(p1.Text)=3) then
ver:=10;
s1 := StrToInt(SSS.Text[2]);
if (s1=1) and (length(SSS.Text)=3) then
s1:=10;
if P[ver-1].s=plus then p3.Text := '+'
else p3.Text := '-';
p2.Text := 'x' + IntToStr(P[ver-1].n);
if ver<>s1 then
p4.Text := FloatToStr(P[ver-1].delta)
else
begin
p4.Font.Name :='Symbol';
p4.Text := 'Ґ';
end;
end;
procedure TForm1.Button5Click(Sender: TObject);
var pp,i,j : integer;
output:array of array of TEdit;
begin
pp:=StrToInt(Col.Text);
SetLength(F,pp);
SetLength(output,pp);
for i:=1 to pp do
begin
SetLength(output[i-1],pp);
SetLength(F[i-1],pp);
for j:=1 to pp do
begin
F[i-1,j-1] := 0;
output[i-1,j-1]:=FindComponent(Format('E%d%d',[i,j])) as TEdit;
output[i-1,j-1].Text := '';
end;
end;
end;
end.