УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ

ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ИНФОРМАТИКИ И РОБОТОТЕХНИКИ

Отчет к курсовой работе по дисциплине

“Дискретная математика”

На тему: Задача о максимальном потоке, алгоритм Форда—Фалкерсона

Научный руководитель:

Васильева Л. И.

Выполнили:

студенты группы ПО-122

ФИРТ

Шаяхметов А.Р.

Корпухин М.В.

УФА

2007г

Задача о максимальном потоке, алгоритм Форда—Фалкерсона.

Содержание:

1. Введение ......................................................................................... стр. 2

2. Теория. Основные понятия .......................................................... стр. 3

3. Постановка задачи.......................................................................... стр. 6

4. Реализация ..................................................................................... стр. 8

5. Тестовый пример............................................................................ стр. 11

6. Заключение .................................................................................... стр. 12

7. Список литературы ....................................................................... стр. 13

Введение

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

Задача о максимальном потоке в сети изучается уже более 60 лет. Интерес к ней подогревается огромной практической значимостью этой проблемы. Методы решения задачи применяются на транспортных, коммуникационных, электрических сетях, при моделировании различных процессов физики и химии, в некоторых операциях над матрицами, для решения родственных задач теории графов, и даже для поиска Web-групп в WWW. Исследования данной задачи проводятся во множестве крупнейших университетов мира.

60 лет назад, задача о максимальном потоке решалась simplex методом линейного программирования, что было крайне не эффективно. Форд и Фалкресон предложили рассматривать для решения этой задачи ориентированную сеть и искать решение с помощью итерационного алгоритма. В течение 20 лет, все передовые достижения в исследовании данной задачи базировались на их методе. В 1970г. наш соотечественник, Диниц, предложил решать задачу с использованием вспомогательных бесконтурных сетей и псевдомаксимальных потоков, что намного увеличило быстродействие разрабатываемых алгоритмов. А в 1974 Карзанов улучшил метод Диница, введя такое понятие как предпоток. Алгоритмы Диница и Карзанова, как и исследования Форда и Фалкерсона, внесли огромный вклад в решение данной проблемы. На основе их методов 15 лет достигались наилучшие оценки быстродействия алгоритмов. В 1986г. появился третий метод, который также без раздумий можно отнести к фундаментальным. Этот метод был разработан Голдбергом и Таряном, и получил название Push-Relabel метода. Для нахождения максимального потока, он использует предпотоки и метки, изменяемые во время работы алгоритма. Push-Relabel алгоритмы очень эффективны, и исследуются до сих пор. И, наконец, в 1997г. Голдберг и Рао предложили алгоритм, присваивающий дугам неединичную длину. Это самый современный из всех известных мне алгоритмов.

В нашей курсовой работе, мы рассмотрим и реализуем на языке программирования C++ алгоритм решения задачи о максимальном потоке, предложенный Фордом и Фалкерсоном.

Теория и основные понятия

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых.

С помощью графов часто упрощалось решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии и др. С помощью графов изображаются схемы дорог, газопроводов, тепло- и электросети. Помогают графы в решении математических и экономических задач.

Определения теории графов

Простым графом G называется пара (V, E), где V - непустое конечное множество, элементы которого называются вершинами графа, а E - конечное множество неупорядоченных пар различных элементов из V, элементы множества E называются ребрами.

В дальнейшем будем рассматривать только простые графы, опуская при этом слово простые.

Если (u,v) - некоторое ребро графа G, то вершины u и v называются смежными, а вершины u и ребро (u,v), также как вершина v и ребро (u,v), называются инцидентными друг другу. Степенью вершины v в графе G называется число ребер графа G, инцидентных вершине v.

	v3	v4
v1			v5
v2			v6

Пример графа

В данном примере
V = {v₁, v₂, v₃, v₄, v₅, v₆},
E = {(v₁, v₂), (v₂, v₃), (v₁, v₃), (v₃, v₄), (v₄, v₅), (v₄, v₆), (v₅, v₆)}

Пусть G = (V, E) - некоторый граф, u и v - его вершины. Маршрутом в графе G, соединяющим вершины  u и v, называется конечная чередующаяся последовательность вершин и ребер вида v₁, e₁, v₂, e₂,...,e_k-1, v_k, где v₁,...,v_k из V, а e₁,...,e_k-1 из E. Маршрут называют цепью, если все его ребра различны. Цепь называют путем (или простой цепью), если все ее вершины кроме, быть может, концевых различны. Если начальная и конечная вершина пути совпадают, то его называют замкнутым путем или циклом.

Граф называется связным графом, если для любых двух его вершин существует соединяющий их маршрут.

Теперь мы можем определить особый класс графов - деревья. Деревом называется связный граф без циклов.

Ориентированным графом D называется пара (V, A), где V - непустое конечное множество, элементы которого называются вершинами графа, а A - конечное множество упорядоченных пар различных элементов из V, элементы множества A называются дугами.

Подобно графам для ориентированных графов вводятся понятие смежности вершин, понятие инцидентности и так далее.

Основанием ориентированного графа D = (V, A), называется граф G = (V, E), где E = A, то есть упорядоченные пары вершин заменяются на неупорядоченнные.

Транспортной сетью называется конечный Связный орграф G(V, E) без петель, каждой дуге которого поставлено в соответствие некоторое неотрицательное число c(), называемое пропускной способностью дуги, и существует:

1)   ровно одна вершина , в которую не заходит ни одна дуга, называемая источником или началом сети;

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

Потоком сети называется неотрицательная функция f(1) такая, что f(e) меньше или равно c(e). (Поток не может превышать пропускную способность дуги.)

Дуга называется насыщенной потоком f, если (Поток называется полным, если содержит насыщенную дугу f(e)=c(e).)

     Разрезом L  сети G(V,E) называется множество насыщенных дуг, отделяющих источник s от стока t.

Теорема Форда-Фалкерсона

Пусть D — транспортная сеть,  - допустимый поток в этой сети,  - множество вершин  таких, что длина минимального пути из  в  в орграфе приращений  равна нулю. Тогда, если , то  - максимальный поток, величина которого равна .

Пусть . Тогда выполняется равенство

        (1)

Если , так как в противном случае, используя  имеем , а следовательно, в силу  существует путь нулевой длины из  в , что противоречит условию . Но тогда из (1) получаем

Следствие 1. Используя теорему Форда-Фалкерсона получаем, что величина максимального потока в транспортной сети равна пропускной способности минимального разреза.

Следствие 2. Пусть  - допустимый поток в транспортной сети D. Тогда, если длина минимального пути из v1 в vn в орграфе приращений  равна бесконечности, то  - максимальный поток.

Постановка задачи

Основной задачей моей курсовой является запрограммировать алгоритм, являющийся важным следствием из теоремы Форда-Фалкерсона, по решению задачи о нахождение максимального потока в сети. Для написания программы мною был выбран язык программирования C++.

Алгоритм решения.

Сначала будем строить полный поток, затем проверим, можно ли его увеличить. Если нет, то этот поток является максимальным. Если же его можно увеличить, то будем строить другой полный поток и т.д. Решать задачу будем с помощью метода  расстановки пометок.

  Две основные процедуры (операции алгоритма):

· операция расстановки пометок;

· операция изменения потока.

  Рассмотрим первую процедуру. Для каждой вершины данной сети нужно приписать пометку, которая имеет следующий вид:  или где , а  — натуральное число или бесконечность. Вообще возможны три состояния вершины:

1)   не помечена;

2)   помечена, но не просмотрена;

3)   помечена и просмотрена.

  Расставлять пометки начнем с источника S. Он получит пометку  Источник помечен, но не просмотрен. Остальные вершины не помечены. Чтобы источник S был помечен и просмотрен, надо поместить все вершины, смежные с  S.

  Вершина  получит пометку , где .

  Теперь все вершины  смежные с S, помечены, но не просмотрены. А вершина S помечена и просмотрена. Начнём просматривать ту из вершин , которая имеет наименьший индекс. Для этого нужно расставить пометки вершинам, смежным с . Если для вершины  выполняется следующее условие , то она получит метку , где . Если же для вершины  выполняется условие , то  получает метку , где . Далее просматриваем следующую вершину, и так до тех пор, пока не пометим сток t или же пока нельзя будет больше пометить ни одной вершины, сток при этом останется не помеченным. Если сток окажется не помеченным, то процесс нахождения максимального потока в сети можно считать законченным, а если сток помечен, то нужно переходить к

процедуре 2.

  Рассмотрим процедуру изменения потока. Если вершина  имеет пометку , то  заменяем на , если же вершина  имеет пометку , то  заменяем на

  Переходим к следующей вершине и так до тех пор, пока не достигнем источника S. Здесь изменение потока прекращается. Далее переходим к процедуре 1 и так до тех пор, пока величину потока уже нельзя изменить.

Программа должна находить максимальный поток во введенную в неё транспортной сети.

Реализация

Программа написана на языке C++ и откомпилирована в Borland C++Builder 6.

#include <iostream.h>

#include <memory.h>

#include <stdio.h>

#include <conio.h>
char* rus (char* st)//функция подключения вывода символов на кириллице
 {
 unsigned char* p = st;
 while (*p)
 {
 if (*p >= 192)
 if (*p<=239)
 *p -= 64;
 else
 *p -= 16;
 p++;
 }
 return st;
 }
const int MAX_VERTICES = 40;
int NUM_VERTICES; // число вершин в графе
const int INFINITY = 10000; // условное число обозначающее бесконечность
// f - массив, содержащий текущее значение потока
// f[i][j] - поток, текущий от вершины i к j
int f[MAX_VERTICES][MAX_VERTICES];
// с - массив содержащий вместимости ребер,
// т.е. c[i][j] - максимальная величину потока способная течь по ребру (i,j)
int c[MAX_VERTICES][MAX_VERTICES];
// набор вспомогательных переменных используемых функцией FindPath - обхода в ширину
// Flow - значение потока через данную вершину на данном шаге поиска
int Flow[MAX_VERTICES];
// Link используется для нахождения собственно пути
// Link[i] хранит номер предыдущей вершины на пути i -> исток
int Link[MAX_VERTICES]; 
int Queue[MAX_VERTICES]; // очередь
int QP, QC; // QP - указатель начала очереди и QC - число эл-тов в очереди
// поиск пути, по которому возможно пустить поток алгоритмом обхода графа в ширину
// функция ищет путь из истока в сток, по которому еще можно пустить поток,
// считая вместимость ребра (i,j) равной c[i][j] - f[i][j],
// т.е. после каждой итерации (одна итерация - один поиск пути) уменьшаем вместимости ребер,
// на величину пущеного потока
int FindPath(int source, int target) // source - исток, target - сток
{
 QP = 0; QC = 1; Queue[0] = source;
 Link[target] = -1; // особая метка для стока
 int i;
 int CurVertex;
 memset(Flow, 0, sizeof(int)*NUM_VERTICES); // в начале из всех вершин кроме истока течет 0
 Flow[source] = INFINITY; // а из истока может вытечь сколько угодно
 while (Link[target] == -1 && QP < QC)
 {
 // смотрим, какие вершины могут быть достигнуты из начала очереди
 CurVertex = Queue[QP];
 for (i=0; i<NUM_VERTICES; i++)
 // проверяем, можем ли мы пустить поток по ребру (CurVertex,i):
 if ((c[CurVertex][i] - f[CurVertex][i])>0 && Flow[i] == 0) 
 {
 // если можем, то добавляем i в конец очереди
 Queue[QC] = i; QC++;
 Link[i] = CurVertex; // указываем, что в i добрались из CurVertex
 // и находим значение потока текущее через вершину i
 if (c[CurVertex][i]-f[CurVertex][i] < Flow[CurVertex])
 Flow[i] = c[CurVertex][i];
 else
 Flow[i] = Flow[CurVertex];
 }
 QP++;// прерходим к следующей в очереди вершине
 }
 // закончив поиск пути
 if (Link[target] == -1) return 0; // мы или не находим путь и выходим
 // или находим:
 // тогда Flow[target] будет равен потоку, который "дотек" по данному пути из истока в сток
 // тогда изменяем значения массива f для данного пути на величину Flow[target]
 CurVertex = target;
 while (CurVertex != source) // путь из стока в исток мы восстанавливаем с помощью массива Link
 {
 f[Link[CurVertex]][CurVertex] +=Flow[target];
 CurVertex = Link[CurVertex];
 }
 return Flow[target]; // Возвращаем значение потока которое мы еще смогли "пустить" по графу
}
// основная функция поиска максимального потока
int MaxFlow(int source, int target) // source - исток, target - сток
{
 // инициализируем переменные:
 memset(f, 0, sizeof(int)*MAX_VERTICES*MAX_VERTICES); // по графу ничего не течет
 int MaxFlow = 0; // начальное значение потока
 int AddFlow;
 do
 {
 // каждую итерацию ищем какй-либо простой путь из истока в сток
 // и какой еще поток мажет быть пущен по этому пути
 AddFlow = FindPath(source, target);
 MaxFlow += AddFlow;
 } while (AddFlow >0);// повторяем цикл пока поток увеличивается
 return MaxFlow;
}
int main()
{
 printf(rus("\n НАХОЖДЕНИЕ МАКСИМАЛЬНОГО ПОТОКА \n"));
 printf(rus("\n АЛГОРИТМ ФОРДА-ФАЛКЕРСОНА \n\n"));
 printf(rus("\n КУРСОВАЯ РАБОТА ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ \n"));
 printf(rus("\n выполнили: Шаяхметов А.Р. , Корпухин М.В. \n\n"));
 printf(rus("\n ПО-122 ФИРТ УГАТУ 2007г\n\n"));
 printf(rus("\n\n нажмите любую клавишу для продолжения...."));
 getch();
 clrscr();
 int source, target;
 printf(rus("\n Введите число вершин в графе\n-->"));
 scanf("%d", &NUM_VERTICES);
 printf(rus("\n Введите значения истока и стока \n-->"));
 scanf("%d %d", &source, &target);
 printf(rus("\n Введите матрицу содержащею вместимость ребер: \n "));
 printf(rus("каждый элемент - вместимость ребра ведушего \n из вершины с номером его строки к вершине с номером его столбца\n"));
 int i, j;
 for (i=0; i<NUM_VERTICES; i++)
 for (j=0; j<NUM_VERTICES; j++)
 scanf("%d",&c[i][j]);
 printf(rus("\n максимальный поток равен:"));
 printf("%d", MaxFlow(source, target));
 getch();
 return 0;
}
 
Тестовый пример
 
С клавиатуры вводятся следующие значения:
 
6 — число вершин в графе
0 5 - вводим значения истока и стока
0 16 0 0 13 0 - вводим массив содержащей вместимоть ребер
0 0 12 0 6 0 (элемент - вместимость ребра ведущего из вершины 
0 0 0 0 9 20 №строки к вершине №столбца)(взвешенная матрица смежности)
0 0 7 0 0 4
0 0 0 14 0 0