Поиск максимальных потоков в сетях
Министерство образования и науки Украины
Луганский национальный педагогический ниверситет имени Тараса Шевченко
Кафедра алгебры и дискретной математики
Киршта Александр Михайлович
Поиск максимальных потоков в сетях
Магистерская работ по специальности 8.080101
Математика
Научный руководитель Ц
к.ф.-м.н., доцент
Михайлова И.А.
Луганск - 2006 г.
Содержание/p>
Введени.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
Раздел. Автоматизация поиска максимальных потоков в сетях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. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕОРИИ
Пусть 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 - множество вершин, А - множество ориентированных рёбер, которые называются дугами, А
align="left">1.2. Графическое представление графов
Графы добно изображать в виде рисунков, состоящих из точек и линий, соединяющих некоторые из этих точек. При этом точки соответствуют вершинам графа, соединяющие пары точек линии (прямолинейные либо криволинейные) - рёбрам (табл.1).
Таблица 1
|
Элементы графов |
Геометрические элементы |
|
1. v Î VЦ вершина |
1. Х - точка в пространстве. |
|
2. {u,v} Ц ребро неориентированного графа |
2. uХ−Хv - отрезок./p> |
|
3. (v1,v2) - дуги в ориентированном графе |
3. v1Х→v2 - направленный отрезок./p> |
|
4. {v,v} Ц петля |
4. align="left">1.3. Виды графовМножество рёбер Е аможет быть пустым (рис. 1.1). Такой граф называется нуль-графом и обозначается Ø. align="left">1.4. Элементы графовПуть - это последовательность рёбер e1, e2, Е, em, такая, что рёбра ei, ei+1 имеют общую вершину. Число рёбер называется длинной пути. Если ни одна из вершин не появляется больше одного раза, то путь называется простым. Понятно, что в простом пути ни одно ребро не используется дважды. Путь называется циклом, если его начальная вершина совпадает с конечной; простым циклом, если это не выполняется для других вершин. Чередующаяся последовательность v1, e1, v2, e2, Е, el,vl+1 вершин и рёбер графа, такая, что ei = vivi+1 (i = 1, l), называется маршрутом. Если v1 =а vl+1, то маршрут замкнутый, иначе открытый. Маршрут называется цепью,
если все его рёбра различны, и простой цепью,
если все вершины, кроме, возможно, крайних, различны. В цепи align="left">1.5. Представление графов с помощью матриц1.5.1. Матрицы инцидентности и списки рёбер Задать граф, значит,
задать множество его вершин и рёбер, также отношение инцидентности. Когда граф G - конечный, для описания его вершин и рёбер достаточно их занумеровать. Пускай v1, v2,Е,
vn - вершины графа G; e1,
e2,Е, em - его рёбра. Отношение инцидентности можно обозначить матрицей img src="images/picture-022-113.gif.zip" title="Скачать документ бесплатно"> align="left">2. ПОТОКИ В СЕТЯХСетью будем называть ориентированный связный граф без петель и параллельных рёбер. Потоки в неориентированных графах можно изобразить в виде потоков в соответствующих ориентированных. Поток в петле не влияет на распределение потока между вершинами. Рассмотрим сеть G = (V, E), |V |
= n, |E| = m. Пускай каждой дуге еj align="left">2.2. Задача о максимальном потоке /h1>На практике часто возникает проблема определения максимальной проводимости некоторой реальной сети: сети транспортной, сети ЭВМ, других. Иногда нужно определить самый дешёвый поток и т.д. Все эти и многие другие задачи решаются с помощью алгоритмов, которые работают на сетях. Так, алгоритм о максимальном потоке ищет максимально возможную пропускную способность сети, алгоритм минимальной стоимости - самый дешёвый поток. В данном разделе будем рассматривать задачу о максимальном потоке. Задача заключается в нахождении такого множества потоков по дугам, чтобы величина Q(vs) была максимальной. Разрез S отделяет vs от vt,
если вершины vs, vt
принадлежат разным сторонам разреза: vs align="left">2.3. Алгоритм размещения пометок для задачи о максимальном потокелгоритм размещения пометок основан на следующей теореме. Теорема 1.Теорема про максимальный поток и минимальный разрез. Для произвольной сети максимальная величина потока из vs в vt равняется минимальной пропускной способности разреза, который отделяет vs от vt. Доказательство Покажем, что величина w произвольного потока φ не превышает пропускной способности разреза (Vs,Vt), который отделяет vs от vt. Поскольку функция φ поток, то она довлетворяет равнению (1) сохранении потока:
align="left">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 присваивается пометка (+,
img src="images/picture-130-23.gif.zip" title="Скачать документ бесплатно"> align="left">2.5. Графы со многими источниками и стокамилгоритм Форда-Фалкерсона примененный и для определения величины максимального потока между множеством вершин - источников и множествома вершин - стоков. Разобьем множество вершин на множество источников V+ = {v align="left">2.6. Задача о многополюсном максимальном потокеРассмотрим задачу нахождения максимального потока для всех пар злов в неориентированной сети. Эту задачу можно рассматривать как обобщение задачи с одним источником и одним стоком, которую можно решить, применяя алгоритм Форда-Фалкерсона для каждой пары вершин. Однако более эффективным является алгоритм, предложенный Р. Гомори и Т. Ху. лгоритм Гомори-Ху 1. Выберем некоторые две вершины графа. Обозначим одну из них через vs, а другую через vt. 2. Применим алгоритм Форда-Фалкерсона и найдём максимальный поток из источника vs в сток vt. При этом множество помеченных вершин и множество непомеченных вершин образуют две стороны минимального разреза Vs и Vt. 3. Выберем две вершины графа vi и vj align="left">3.1.
Описание интерфейса программы
|
