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

Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Сибирский государственный университет телекоммуникаций и информатики»

Уральский технический институт связи и информатики (филиал) в г. Екатеринбурге

Кафедра информационных систем и технологий

КУРСОВОЙ ПРОЕКТ

По междисциплинарному курсу: «Математические методы»

На тему: «Нахождение максимального потока в графе»

Вариант № 4

Выполнил: студент группы 481

Иксанов С.А.

Руководитель: преподаватель

Тюпина О.М.

г. Екатеринбург, 2015г.

Содержание

• Введение
• 1. Основные понятия теории графов
• 1.1 Поток в транспортной сети
• 1.2 Орграф приращений
• 1.3 Теорема Форда-Фалкерсона
• 2. Постановка задачи
• 2.1 Алгоритм построения максимального потока
• 3. Выбор языка программирования
• 4. Блок-схема работы программы
• 5. Работа программы
• 6. Руководство пользователя
• Список используемой литературы
• Введение

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

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

В 1970г. наш соотечественник, Диниц, предложил решать задачу с использованием вспомогательных бесконтурных сетей и псевдомаксимальных потоков, что намного увеличило быстродействие разрабатываемых алгоритмов. А в 1974г. Карзанов улучшил метод Диница, введя такое понятие как предпоток. Алгоритмы Диница и Карзанова, как и исследования Форда и Фалкерсона, внесли огромный вклад в решение данной проблемы.

На основе их методов 15 лет достигались наилучшие оценки быстродействия алгоритмов. В 1986г. появился третий метод, который также без раздумий можно отнести к фундаментальным.

Цели:

Разработать программу, которая реализует один из алгоритмов нахождения максимального потока в графах.

Задачи:

1. Изучить теоретический материал;

2. Ознакомиться с алгоритмами нахождения максимального потока в графах;

3. Реализовать программное решение задачи о максимальном потоке в сети;

4. Выбрать язык программирования и компилятор;

5. Создать программу для нахождения максимального потока в графе.

графа приращение программирование алгоритм

1. Основные понятия теории графов

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

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

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

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

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

Пример графа представлен на рисунке 1.

	v3	v4
v1		v5
v2		v6

Рисунок 1- Пример графа

В данном примере

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.

1.1 Поток в транспортной сети

Функция , определенная на множестве X дуг транспортной сети D и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в транспортной сети D, если:

*для любой дуги величина , называемая потоком по дуге , удовлетворяет условию ;

*для любой промежуточной вершины v выполняется равенство

т.е. сумма потоков по дугам, заходящим в v, равна сумме потоков по дугам, исходящим из v.

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

По определению допустимого потока имеем:

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

Аналогично для каждой дуги , величина входит в левую часть равенства (2) лишь один раз и при этом со знаком минус. С другой стороны, для каждой дуги величина входит в левую часть равенства (2) один раз со знаком плюс (при ) и один раз со знаком минус (при ), что в сумме даёт нулевой вклад в левую часть равенства (2). Учитывая сказанное, заключаем, что из равенства (2) следует справедливость равенства (1).

Величиной потока в транспортной сети D называется величина , равная сумме потоков по всем дугам, заходящим в , или, что то же самое - величина, равная сумме потоков по всем дугам, исходящим из

Пусть - допустимый поток в транспортной сети D. Дуга называется насыщенной, если поток по ней равен её пропускной способности, т.е. если . Поток называется полным, если любой путь в D из содержит, по крайней мере, одну насыщенную дугу.

Поток называется максимальным, если его величина принимает максимальное значение по сравнению с другими допустимыми потоками в транспортной сети D.

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

1.2 Орграф приращений

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

т.е. орграф является нагруженным. При этом очевидно, что длина любого пути из в в орграфе равна либо 0, либо бесконечности.

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

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

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

(1)

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

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

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

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

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

2.1 Алгоритм построения максимального потока

Важным следствием теоремы Форда-Фалкерсона является алгоритм построения максимального потока в транспортной сети.

Шаг 1. Полагаем i=0. Пусть - любой допустимый поток в транспортной сети D (например, полный, можно начинать с нулевого потока: ).

Шаг 2. По сети D и потоку строим орграф приращений .

Шаг 3. Находим простую цепь , являющуюся минимальным путем из в в нагруженном орграфе . Если длина этой цепи равна бесконечности, то поток максимален, и работа алгоритма закончена. В противном случае увеличиваем поток вдоль цепи на максимально допустимую величину , такую, что при этом сохраняется условие 1 допустимого потока (для любой дуги величина , называемая потоком по дуге х, удовлетворяет условию ). В силу , используя и , получаем, что указанная величина существует. В результате меняется поток в транспортной сети D, т.е. от потока мы перешли к потоку , и при этом . Присваиваем и переходим к шагу 2.

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

3. Выбор языка программирования

Для написания программы мною был выбран язык программирования C++ и компилятор Visual Studio 2015.

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

Поддерживаются различные стили и технологии программирования, включая традиционное директивное программирование, ООП, обобщённое программирование, метапрограммирование (шаблоны, макросы);

Предсказуемое выполнение программ является важным достоинством для построения систем реального времени;

Весь код, неявно генерируемый компилятором для реализации языковых возможностей (например, при преобразовании переменной к другому типу), определён в стандарте;

Также строго определены места программы, в которых этот код выполняется. Это даёт возможность замерять или рассчитывать время реакции программы на внешнее событие;

Автоматический вызов деструкторов объектов при их уничтожении, причём в порядке, обратном вызову конструкторов;

Это упрощает (достаточно объявить переменную) и делает более надёжным освобождение ресурсов (память, файлы, семафоры и т. п.), а также позволяет гарантированно выполнять переходы состояний программы, не обязательно связанные с освобождением ресурсов (например, запись в журнал);

Пользовательские функции-операторы позволяют кратко и ёмко записывать выражения над пользовательскими типами в естественной алгебраической форме;

Язык поддерживает понятия физической (const) и логической (mutable) константности.

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

4. Блок-схема работы программы

Блок-схема программы представлена ниже на рисунке 2.

Рисунок 2- Блок-схема работы программы

5. Работа программы

С клавиатуры вводятся следующие значения:

Число вершин в графе: 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

0 0 0 0 0 0

На рисунке 3 и рисунке 4 представлена работа программы.

Рисунок 3- Работа программы



Рисунок 4- Работа программы

6. Руководство пользователя

1 Ixanov.exe - исполняемый файл программы. При запуске появится главное окно программы с названием и фамилией автора.

2 Нажмите «Enter» чтобы перейти к началу решения.

3 Введите число вершин в графе.

4 Введите значения истока и стока (через пробел).

5 Ведите матрицу (через пробел)

Список используемой литературы

1 М.О. Осанов, В.А. Баранский, В.В. Расин, Дискретная математика: графы, матроиды, алгоритмы - Ижевск, НИЦ «Регулярная и хаотическая динамика»; 2010.

2 А.И. Белоусов, С.Б. Ткачев, Дискретная математика: учебник для вузов - Изд - во МГТУ им. Н.Э. Баумана;2011.

3 В.Н. Нефедов, В.А. Осипова «Курс дискретной математики» М. 2011.

4 С.В. Судоплатов, Е.В. Овчинникова «Элементы дискретной математики» М. 2012. "Алгоритмы. Построение и анализ" Т. Кормен, Ч. Лейзерсон, Р. Ривест ("Introduction to Algorithms" Thomas Cormen, Charles Leiserson, Roland Rivest), стр. 536 - 573.

5 http://pismoref.ru

6 http://algolist.ru/maths/graphs/maxflows/

7 http://urban-sanjoo.narod.ru/ford-fulkerson.html

Приложение

Программа написана на языке C++ и откомпилирована в Visual Studio 2015.

#include <iostream>

#include <memory.h>

#include <stdio.h>

#include <conio.h>

#include <Windows.h>

char* rus(char* st)//функция подключения вывода символов на кириллице

{

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()

{

SetConsoleCP(1251);

SetConsoleOutputCP(1251);

printf(rus("\n Нахождение максималтного потока в графе \n"));

printf(rus("\n Алгоритм Форда-Фалкерсона \n\n"));

printf(rus("\n Курсовая работа\n"));

printf(rus("\n Vipolnil : Иксанов С.А. \n\n"));

printf(rus("\n URTiSI Екатеринбург 2015г\n\n"));

printf(rus("\n\n Нажминте любую клавишу для продолжения...."));

getch();

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;

}

Размещено на Allbest.ru