Графы. Задачи на оптимизацию.

Содержание

Введение        .2

Глава 1. Основные понятия        4

1.1.Теория графов и оптимизация        

1.2. Путь, цепь, контур, цикл. Связность графа        8

1.3. Эйлеровы и Гамильтоновы графы………………………………………....12

1.4.Основные понятия максимального потока        .........................18

1.5.Деревья………………………………………....…………………................20

Глава 2. Оптимизационные задачи на графах        22

2.1. Задача о кратчайшем пути        22

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

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

Заключение        33

Список использованной литературы…………………………………………...34

Введение

Начало теории графов. Издревле среди местных жителей Кёнигсберга была распространена такая увлекательная загадка: как пройти по всем мостам, а в городе их было 7, не проходя ни по одному из них дважды? Многие пытались решить эту задачу во время прогулок. Но никому это не удавалось. В 1736 году это задача заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера. Он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них более одного раза. Взаимное расположение мостов натолкнуло математика Леонарда Эйлера на размышления, приведшие к возникновению теории графов.

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

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

Целью исследования является описание задач на оптимизацию на графах.

Задачи:

- описать теорию графов и оптимизацию;

- определить такие понятия, как путь, цепь, контур, цикл, связность графа;

- рассмотреть задачу о кратчайшем пути;

- изучить задачу о максимальном потоке.

Объект – дискретная математика.

Предмет – оптимизационные задачи на графах.

Структура. Работа состоит из введения, двух глав, заключения, списка использованной литературы.

Глава 1. Основные понятия

1.1. Теория графов

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

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

Рис. 1. Примеры графов

На  введенное выше понятие графа «навешиваются» новые свойства.В ориентированном графе (орграфе) вершины соединяются ребрами, каждому из которых при помощи стрелки задается ориентация. Примеры ориентированных графов изображены на рис. 2.

Рис. 2. Примеры ориентированных графов

Ориентированный граф  полезен: для иллюстрации организации перевозок в транспортной задаче. В экономике дугам ориентированного или обычного графа приписывают числа, например, стоимость проезда или перевозки груза из пункта  А(начальная вершина дуги) в пункт Б (конечная вершина дуги).

Граф называется неориентированным (неорграфом), если каждое его ребро не ориентировано.

Петлей называется ребро (), у которого инцидентна одной и той же вершине. Граф, полученный из орграфа заменой каждой дуги на ребро, называется основанием графа.

Если пара вершин графа соединяется несколькими различными ребрами, то ребра называются кратными, а их количество – кратностью ребра. Граф с кратными ребрами без петель называется мультиграфом. Граф с петлями и кратными ребрами называется псевдографом. Граф без петель и кратных ребер называется простым графом.

Рис. 3.

На рис. 3:а и в) изображены неограф и смешанный граф соответственно, у которых кратность ребра равна трем; б) изображен орграф, у которого кратность ребра равна двум; г) приведен пример петли (считается неориентированной).

Рис. 4.

На рис. 4: а) – псевдограф, б) – мультиграф, в) – простой граф.

Две вершины простого графа называются смежными, если они соединены точно одним ребром.

Два ребра смежны, если они имеют общую вершину.

Вершина и ребро называются инцидентными, если ребро выходит из этой вершины

Вершина, для которой не существует идентичных ей ребер, называется изолированной. Вершина называется висячей, если степень ее равна единице.

Вершина называется четной, если из нее выходит четное число ребер. Если из вершины выходит нечетное число ребер, то вершина называется нечетной. Число ребер, выходящих из вершины называется степенью вершины.

Рис. 5.Рис. 6.

На рис. 5. Изображен неориентированный граф, имеющий 4 вершины, 5 ребер. Из них: Смежные вершины,х1 и х2, х1 и х4; смежные ребра (х1, х4) и (х4, х2); ребро (х1, х2) инцидентно вершинам х2, х1; а вершина х3 инцидентна ребрам (х3, х2) и (х4, х3).

На рис. 6. изображен ориентированный граф, имеющий 4 вершины, 6 дуг. Смежные вершины, х1 и х2, х2 и х3; смежные дуги (х4, х3) и (х3, х2); дуга (х4, х3) инцидентна вершинам х3, х4; а вершина х4 инцидента ребрам (х3, х4), (х4, х3) и (х4, х1).

Граф называется полным, если в нем каждые две различные вершины соединены точно одним ребром. Полный орграф называется турниром. Этот термин получил свое значение от соревнований по круговой системе,графическое представление которых имеет структуру полного ориентированного графа.

Граф называется плоским, если он изображен на плоскости так, что его ребра пересекаются только в вершинах.

Всякий граф , изоморфный плоскому называется планарным.

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

Рис. 7.

На рис. 7.: а) – полный неорграф, б) - полный орграф, в) – планарный граф.

В графе можно выделить части – подграфы, обладающие некоторыми свойствами. Рассмотрим граф G=(X, U).

Граф, называется подграфом графа G, если

Рис. 8.

На рис. 8: а) – данный граф, б) – остовной подграф, в) – порожденный подграф, г) – подграф.

Если , то такой подграф называется остовным.

Порожденным подграфом графа Gна множестве вершин  называется подграф , такой, что  содержит все те ребра из , которые соединяют вершины из .

1.2. Путь, цепь, контур, цикл. Связность графа

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

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

Если каждой дуге (ребру) приписано некоторое число, называемое весом, то граф называется взвешенным

В случае взвешенного графа, длина пути (цепи) – это сумма весов дуг (ребер), входящих в этот путь.

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

Путь называется элементарным, если в нем ни одна вершина не встречается дважды.

Циклом называется замкнутая цепь.  Цикл, у которого все вершины различны, называется простым.

Рис. 9. а) неограф, б) оргаф

Неориентированный граф называется связным, если все его вершины связаны межу собой, иначе граф называется несвязным.

Для орграфов понятие связности является более содержательным. Можно выделить три типа связности орграфа: 1)слабый – когда его основание есть связный граф;

2)односторонне связный – если для любых двух различных вершин  существует,  по крайней мере, один путь из;

3)сильно связным, если для любых двух вершин существует соединяющий их путь из и обратно.

При большом числе вершин и дуг изображение графа теряет наглядность. В этих случаях для задания графов и работы с ними используют матрицы.

1. Граф без петель, имеющий n вершин и m дуг можно задать матрицей инциденций, строки которой соответствуют вершинам, а столбцы – дугам. Элементы матрицы, размерности nm, определяются по формуле

     Для неориентированного графа вместо ”-1” ставится 1.

2. Матрица соседства вершин- квадратной матрицей  размера , в которой равно числу ребер, идущих из вершины в вершину .

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

Основные операции над графами

Рассмотрим несколько основных операций над графами.

 1. Добавление вершины: .

,

 2. Добавление ребра: .

, . Операция применима, если

3. Удаление ребра:

 Операция применима, если.

4. Удаление вершины:

5. Объединение графов

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

6. Произведение графов:

Пример произведения графов можно увидеть на рисунке 10.

Рис.10

  Дополнение графа

Дополнением графаназывается граф G, такой что  и . То есть множество ребер E() — дополнение множества E(G) до множества ребер полного графа с тем же множеством вершин.

Граф, изоморфный своему дополнению, называется самодополнительным. Несложно показать и следующие свойства дополнения графа:

 1) двойное дополнение равно исходному графу: ,

• 2) если графы изоморфны, то изоморфны и их дополнения:  

Теорема 1. Для любого графа G верно, что хотя бы один из графов G и — связный граф.

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

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

Рассмотрим два варианта.

1. Пусть  Тогда вершины  и  одновременно лежат или в множестве  или в множестве. Пусть, не умаляя общности, , ∈.

Рассмотрим произвольную вершину Тогда (u, )  E(G) и (u, )  E(G). Следовательно, (u, ) ∈ E() и (u, ) ∈ E(). То есть между вершинами  и  нашелся маршрут длины 2: , u, .

2. ПустьТогда по определению дополнения То есть между вершинами  нашелся маршрут длины 1.

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

1.3. Эйлеровыи Гамильтоновы графы

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

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

Примеры.

Рис.11

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

Рис.12

Теорема 2. Если граф G обладает эйлеровым циклом, то он является связным, а все его вершины — четными.

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

 Верно и обратное утверждение.

Теорема 3. Если граф G связный и все его вершины четные, то он обладает эйлеровым циклом.

Доказательство Если начать путь из произвольной вершины графа G , то найдется цикл, содержащий все ребра графа.

Пример.

Рис.13

Пусть  — произвольная вершина графа G. Из   начнем путь  по одному из ребер и продолжим его, проходя каждый раз по новому ребру.

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

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

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

Если остались не пройденные ребра, то должна существовать вершина  , принадлежащая  и ребру, не вошедшему в

Так как  — четная, то число ребер, которым принадлежит и которые не вошли в путь, тоже четно. Начнем новый путь S изи используем только ребра, не принадлежащие . Этот путь кончится в . На рисунке путь S обозначен прямыми линиями со стрелками. Объединим теперь оба цикла: из  пройдем по пути  к  , затем по циклу S  и, вернувшись в , пройдем по оставшейся части пути обратно в .

Если снова найдутся ребра, которые не вошли в путь, то найдем новые циклы. Число ребер и вершин конечно, процесс закончится.

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

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

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

 Теорема 4. Если граф G обладает эйлеровым путем с концами и  (не совпадает с , то граф G является связным, и и — единственные нечетные его вершины.

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

Верно и обратное.

 Теорема 5. Если граф G связный ии единственные нечетные вершины его, то граф G обладает эйлеровым путем с концами  и  .

Доказательство Вершины  и  могут быть соединены ребрами в графе.

Пример.

Рис.14

А могут быть и не соединены.

Рис.15

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

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

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

Теорема 6. Если связный граф G имеет  нечетных вершин, то найдется семейство изk путей , которые в совокупности содержат все ребра графа в точности по одному разу.

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

Половину нечетных вершин обозначим  , , …,а другую половину — , …  .

Пример.

Рис.16

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

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

Граф, в котором число нечетных вершин превышает 2, не является эйлеровым и не является полуэйлеровым.

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

Гамильтонова цепь имеет разные вершины: начальную и конечную.

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

Рис.17

На рис. 17изображены: а)Негамильтонов граф, б)полугамильтонов граф, в)гамильтонов граф.

Ирландский математик и астроном Уильям Гамильтон (1805 − 1865) занимался исследованием существования таких циклов в графе, соответствующем додекаэдру,в связи с темвозниклоназвание «гамильтонов цикл».

Рис.18

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

Необходимое и достаточное условие гамильтоновости графа до сих пор не получено. Поиск такого критерия остаётся одной из главных нерешённых задач теории графов. Разработаны лишь достаточные условия, одно из которых сформулировал Габриэль Дирак (1925 – 1984).

Теорема (Дирака). Если в связном графе G, имеющем  ≥ 3 вершин, степень каждой вершины больше или равна n /2 , то граф G является гамильтоновым графом.

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

1.4.Основные понятия максимального потока.

Задача о максимальном потоке формулируется относительно транспортной сети. Под последней понимается взвешенный ациклический орграфG=(V,E,C), чьи базы истока и стока состоят из единственных вершин: , а веса всех дуг неотрицательны:. Вершина как исток сети часто обозначается черезs (source), а вершинaкак сток- черезt (target) . Весc(e) графаG в этой задаче интерпретируется пропускной способностью дугиe.

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

1)

2) для любой промежуточной вершины

Это уравнение характеризует сохранение потока для всех промежуточных вершин: поток, втекающий в вершину, равен потоку, вытекающему из нее.

Величиной потока в транспортной сети Gназывается величина Ф(G), равная сумме потоков по всем дугам, исходящим из  вершиныs, либо величина, равная сумме потоков по всем дугам, заходящим в вершинуt:

Дуга eназывается насыщенной, если поток по ней равен ее пропускной способности, т.е

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

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

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

1.5. Деревья

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

 Если неориентированный граф связный и не имеет циклов, тоназывается неориентированным деревом

  Если Ориентированный граф G=связный, в нем существует точно одна вершина , в которую не входят никакие дуги, и в каждую вершинувходит ровно одна дуганазывается ориентированным деревом. При этом вершинаназывается корнемдерева.

  Давайте рассмотрим более основательно сначала неориентированные деревья.

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

Будем рассматривать дерево   G=.

1. В дереве для всяких двух вершин естьтолько одинмаршрут, соединяющий эти вершины.

2. Количество ребер |E| ровно на 1 меньше количества вершин  |V|.

3. Если у дерева удалить всякое ребро, то этот граф станет несвязным.

4. При добавлении нового ребра в дерево, это дерево станет графом, имеющим единственный цикл.

Вершина в неориентированном графе называется висячей, если

у нее есть единственное ребро. Если из дерева убрать одну висячую

вершину и ребро, которое имеет эта вершина, то мы снова получим

неориентированное дерево.

  В Больших приложенияхесть ориентированные деревья, в которых

есть собственная терминология. Вершина называется листом, если из нее не выходит ни одна дуга. Лист является корнем только тогда, когда дерево состоит из единственной вершины. Ветвью дерева называется путь из корня до любого листа. Высота дерева это максимальная длина ветви. Глубиной вершины называется длина пути из корня до этой вершины. Если из вершины  идет дуга в, вершина  называется родительской по соотношению к , а вершина  называется дочерней по соотношению к .

Ориентированное дерево делаетотдельный порядок на множестве

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

Также так, если в неориентированном дереве удалить вершину, являющуюся листом ( имеется в виду, что это вершина не является корнем), и дугу, входящую в эту вершину, мы получим снова ориентированное дерево.

Глава 2. Оптимизационные задачи на графах

1. Задача о кратчайшем пути

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

Найдем кратчайший путь от до . Граф задан элементами стоимостной матрицы:

r[0;1]=12;r[4;7]=54; r[6;3]=13; r[5;7]=43;

r[0;2]=63; r[4;2]=18; r[6;7]=35; r[5;4]=26;

r[0;3]=92; r[2;5]=21; r[2;1]=59; r[6;5]=11;

r[1;4]=35; r[2;6]=15; r[3;2]=32;
Построим этот граф на рис.19.

Рис.19.

На (рис.20.) Начнем с вершины и присвоим ему метку 0.Рассмотрим всех его соседей, т.к. там еще нет пометок, и присвоим им соответствующие длины:

Рис.20.
Все соседи рассмотрены, помечаем ее и переходим к вершине . Ее соседи , .  помечена, не рассматриваем ее. Для :, оставляем метку.

Для : , заменяем метку. Все соседи вершины  рассмотрены, помечаем ее на рис.21.
Рис.21.

переходим к вершине . Ее соседи , , , , но , помечены, не рассматриваем их.
Для :, оставляем метку.
Для :, заменяем метку .
Для : , оставляем метку .
Для : , заменяем метку .
Все соседи вершины  рассмотрены, помечаем ее на рис.22.
Рис.22.

переходим к вершине .Ее соседи , , но , помечены, не рассматриваем их.
Для:, , оставляем метку.
Все соседи вершины  рассмотрены, помечаем ее на рис.23.
Рис.23

переходим к вершине .Ее соседи , ,,  но ,  помечены, не рассматриваем их.
Для :, заменяем метку.
Для,:, заменяем метку .
Все соседи вершины  рассмотрены, помечаем ее на рис.24.

Рис.24.

переходим к вершине .Ее соседи , ,,  но ,  помечены, не рассматриваем их.
Для : , оставляем метку.
Для : , оставляем метку .
Все соседи вершины  рассмотрены, помечаем ее на рис.25.
                        Рис.25.

переходим к вершине.Ее соседи , ,,  но ,  помечены, не рассматриваем их.
Для : , оставляем метку.
Все соседи вершины  рассмотрены, помечаем ее. И помечаем оставшуюся, все вершины рассмотрены.(Рис.26.)

Рис.26.

Вывод: Кратчайший путь их  в  имеет длину 101, этот путь: ---.

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

Конечный взвешенный связный орграф без контуров и петель, ориентированный в одном общем направлении от вершины I (исток, вход) к вершине S (сток, выход) называется сетью.

Задача о максимальном потоке является оптимальным и имеет много применений. Дан взвешенный ориентированный граф с неотрицательными весами (пропускными способностями). Выделены две вершины: исток S и сток I такие, что любая другая вершина лежит на пути из S в I. Потоком назовем функцию  с такими свойствами:

1)Ограничение пропускной способности. Поток по ребру не может быть больше его (ребра) пропускной способности.

2)Антисимметричность. Для каждого ребра

Сохранение потока. Для каждой вершины (кроме S и I), количество входящего потока (отрицательного) равен количеству исходящего потока (положительного). Другими словами, алгебраическая сумма потоков для каждой вершины (кроме S и I) равна нулю.

Задачу о максимальном потоке можно сформулировать следующим образом: найти совокупность потоков x*ij по всем рёбрам сети, которая удовлетворяет условиям и максимизирует линейную функцию.

Метод решения задачи о максимальном потоке (от к) предложен Фордом и Фалкерсоном, и их «техника пометок» составляет основу других алгоритмов решения многочисленных задач, являющимися простыми обобщениями или расширениями указанной задачи. Рассмотрим задачи:

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

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

Задача о потоках с выигрышами. В каждом израссмотренных выше случаях неявно допускалось, что поток на входе дуги такой же, как и на выходе. Если рассмотреть граф, в котором выходной поток дуги равен ее входному потоку, умноженному на некоторое неотрицательное число, то задачу о максимальном потоке называют задачей о потоках с выигрышами. В такой задаче потоки могут «порождаться» и «поглощаться» самим графом, так что поток, входящий в S, и поток, покидающийt, могут изменяться совершенно независимо.

Граф, некоторые вершины которого выделены, называется сетью. Выделенные вершины называются полюсами сети. Например, дерево с корнем можно рассматривать как однополюсную сеть.

Вершины, отличные от полюсов, называются внутренними вершинами сети. Ребро, инцидентное хотя бы одному полюсу, называется полюсным ребром. Остальные ребра называются внутренними.

 -полюсником называется сеть с ) полюсами, разбитыми на два класса: kвходных иlвыходных полюсов. (1,1)-полюсник называется двухполюсной сетью.

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

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

Можно дать различные интерпретации транспортной сети. Пусть, например, в полюсе Sимеется неограниченный запас некоторого продукта и нужно организовать доставку этого продукта в полюсtпо сети путей сообщения с некоторыми промежуточными вершинами. В этом случае пропускная способность дуги – количество груза, которое можно перевезти в единицу времени по данной дуге. Тогда возникает задача: организовать перевозки по сети таким образом, чтобы, не превышая пропускных способностей дуг, перевозить из Sвtмаксимальное количество груза в единицу времени.

Для каждой вершины xсетиsобозначим через  множество всех дуг, входящих вx, а через– выходящих из x. Для источникаsи стокаtимеем.

Потоком в сети Sназывается целочисленная функция j(u), определенная на дугах сети и удовлетворяющая условиям:

1. ₤ c(u), ; (1)
2. , . (2)

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

На рис. 23 приведен пример сети , в которой каждой дугеприписана двойка.

8,8 7,6

2,2 2,0

5,5

9,7

Рис. 23. Пример транспортной сети

Если сложить уравнения сохранения для всех вершин, то останутся только члены, соответствующие дугам и:

.

Таким образом, для любого потока величина груза, выходящего из источника Sравна величине груза, прибывающего в стокt. Эту величину обозначаютFи называют величиной потока:

.

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

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

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

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

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

Дана определенная сеть. Разделим множество вершин сети на два непересекающихся множества А и В. Чтобы в множество А попал исток I, а в множество В попал сток S. Тогда на сети задан разрез. Разрезом сети (А/B) называется совокупность ребер (i,j), которые начальные вершины принадлежат А, а конечные – В.

Сумму пропускных способностей всех рёбер разреза называют            пропускной способностью разреза:

R (A/B) = rij.

Потоком через разрез называется  сумма всех потоков xij по всем рёбрам разреза:

X(A/B) =xij.

 Теорема Форда-Фалкерсона:величина максимального потока в графе путей равна величине пропускной способности его минимального разреза.

Теорема Форда-Фалкерсона позволяет определить максимальный поток для относительно простых сетей.

 2.2.2.  Алгоритм решения задачи о максимальном потоке.

1. Давайте построим начальный поток  (величина выбранного потокачем больше, тем быстрее решаем задачу).
2. На основе заданной сети построим новую сеть:

1) каждая дуга, для которой  остаётся в новой сети с первоначальной rij;

2) каждая дуга для которой  заменяется на две:

 - первая дуга того же направления с пропускной способностью

 -  вторая дуга противоположенного направления с пропускной способностью .

 3) Допустим в новой сети можно найти ненулевой поток из I в S, то этот поток прибавляется к начальному. В результате получается новый поток и переходят к п. 2.Если в новой сети нет ненулевые потоки из I в S, то максимальный поток сети построен.

Заключение

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

Различные прикладные задачи оптимизации могут быть сформулированы в форме некоторой задачи оптимизации на графах. Вместе с этим в теории графов многие увлекательные задачи связаны с решением задач оптимизации. Из достаточно многого числа типовых задач оптимизации на графах можно подчеркнуть основные и в определенном понимании ставшие лучшими для данного класса:

- задача нахождения кратчайшего пути в графе;

- задача нахождения критического пути в сетевом графе;

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

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

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

1. Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. — М.: Высш. школа, 1976. — С. 392.
2. Берж К. Теория графов и ее приложения. М.: ИЛ, 1962. 320c.
3. Быкова В. В. Комбинаторные алгоритмы : множества, графы, коды: учебное пособие
4. Издательство: Сибирский федеральный университет, 2015
5. Д. В. Карпов. Дерево разбиения двусвязного графа. Записки научных семинаров ПОМИ, том 417 (2013 г.), стр. 86-105.
6. Гладких О. Б., Белых О. Н. Основные понятия теории графов: учебное пособие Издательство: Елецкий государственный университет им. И. А. Бунина, 2011
7. Д. В. Карпов. Связность графов. http://logic.pdmi.ras.ru/∼dvk/connectivity.pdf.
8. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)
9. T. Кормен, Ч. Лейзерсон, P. Ривест. Алгоритмы: Построение и анализ. М.: МЦНМО, 2001. - 960 с
10. Ф. Харари. Теория графов. // Москва, “Мир”, 1973. (Перевод с английского. F.Harary, Graph theory, Addison-Wesley, 1969.)
11.  Ю. В. Матиясевич. Один критерий раскрашиваемости вершин графа, формулируемый в терминах ориентаций ребер. Дискретный анализ, т.26 (1974) стр.65-71. Английский перевод: https://arxiv.org/abs/0712.1884.