Файл: Курсач ебаный.docx

Министерство образования РФ.

Московский Государственный Университет Машиностроения (МАМИ)

Курсовая работа

по дисциплине «Дискретная математика»

на тему: «Потоки в сетях».

Выполнил студент II курса, Механико-технологического факультета (бакалавр, 010400.62) Вагайцев Д.С. 1912146 Руководитель: Нефедова И. В.

Москва 2013

Содержание:

1. Основополагающие понятия теории сетей:

• ориентированный граф

• сеть

• поток в сети

• разрез в сети

2. Теорема Форда-Фалкерсона и ее доказательство

3. Дополнительные леммы и их доказательство

4. Алгоритм решения задач

5. Решение задач

6. Источники информации

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

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

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

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

Для сетей можно обобщить понятие полустепени исхода и полустепени захода вершины. Пусть N=(G, a) – сеть, v – вершина этой сети (т.е. вершина графа G). Полустепенью исхода r^–(v) вершины v назовем сумму a(е) по всем дугам, исходящим из v, полустепенью захода r⁺(v) вершины v – сумму a(е) по всем дугам, заходящим в v. Например, для сети на рис. 6.12 выполняется равенство r^–(v₀)=5, r⁺(v₀)=0, r^–(v₂)=8, r⁺(v₂)=4. Для сетей, так же как и для орграфов справедливо утверждение о том, что сумма полустепеней исхода и сумма полустепеней захода всех вершин совпадают.

Как и в случае орграфов, вершину сети v, для которой r^–(v)>0 и r⁺(v)=0 будем называть источником, а вершину w, для которой r⁺(w)>0 и r^–(w)=0 – стоком.

Введем длину пути как сумму длин дуг, составляющих путь.

Определение. Расстоянием d(u,v) от вершины u до вершины v называется длина кратчайшего (u,v)–пути. Если (u,v)–пути не существует, то полагаем d(u,v)=¥. Расстояние от u до u равно нулю.

Так для сети, изображенной на рис. 6.12, имеем равенства d(v₀,v₅)=3, d(v₁,v₀)=¥, d(v₁,v₂)=4, d(v₂,v₁)=2.

Для сети N возникает задача нахождения расстояния d(u,v) для данных вершин u и v и соответствующего кратчайшего пути. Известно несколько способов решения этой задачи. Мы рассмотрим один из них, основой которого является алгоритм Дейкстры, названный в честь известного скандинавского специалиста по компьютерным наукам Дейкстры.

Алгоритм Дейкстры вычисляет расстояние от фиксированной вершины v₀ до всех остальных вершин сети. Прежде, чем привести описание алгоритма, введем необходимые обозначения. Пусть N=(G,a) – сеть, v₀ – фиксированная вершина этой сети, v₁,…,v_k – остальные вершины. Для i=1,…,k расстояние d(v₀,v_i) обозначим через d(v_i). На множестве вершин введем двухместную функцию a(v,v’) следующим образом:

Описание алгоритма, кроме того, еще использует подмножество S множества вершин V.

Алгоритм Дейкстры.

Шаг 1. Полагаем S=V\{v₀}, d(v_i)=a(v₀,v_i) для всех i=1,…,k.

Шаг 2. Если ½S½=1, то выполнить шаг 4. Выбрать в S элемент v’, для которого величина d(v’) является наименьшей (среди всех элементов из S).

Шаг 3. Положить S=S\{v’}, d(v)=min{d(v), d(v’)+a(v’,v)} для всех vÎS и перейти к шагу 2.

Шаг 4. Выдать d(v₁),…,d(v_k). Конец работы алгоритма.

Алгоритм осуществляет «итеративный» процесс нахождения расстояния d(v_i) для i=1,…,k. Проследим, как это делается для сети N, изображенной на рис. 6.12. Работа алгоритма будет иллюстрироваться заполнением таблицы 6.1.

При выполнении первого шага алгоритма величины d(v_i) примут значения, которые указаны в нулевой строке таблицы. Из них точным является только d(v₂), значения остальных величин завышены. На шаге 2 в качестве v’ выбирается вершина v₂ (в таблице соответствующее значение набрано жирным шрифтом) и удаляется из S на шаге 3. На том же шаге уточняются предыдущие значения d(v) для vÎS (см. первую строку таблицы 6.1). На этом первый проход алгоритма заканчивается. На втором проходе в качестве v’ берется v₅, удаляется из S и значения d(v) для vÎS снова уточняются. Результат уточнения отражен во второй строке таблицы. Когда множество S будет содержать только вершину

Рис. 6.12

Таблица 6.1

V₃ алгоритм заканчивает работу. Результат: d(v₁)=3, d(v₂)=1, d(v₃)=4, d(v₄)=4, d(v₅)=3.

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

Пусть N=(G,a) – сеть, имеющая один источник a и один сток b. Предположим, что сеть N представляет собой схему линий связи, где вершинам соответствуют узлы связи, дугам – линии связи с указанным направлением передачи информации. Если е – дуга сети N, то величина a(е) означает ограничение количества информации, передаваемой по дуге е за некоторый промежуток времени. Возникает следующий вопрос. Какое наибольшее количество информации можно передать из а в b и как это сделать? Ответу на поставленный вопрос и посвящен этот параграф.

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

Центральным понятием параграфа является понятие потока в сети.

Определение. Пусть N=(G,a) – сеть, а – источник и b – сток этой сети. Потоком через сеть N называется функция

j:Е®R⁺È{0},

удовлетворяющая двум условиям:

1) J(е)£a(е) для любой дуги еÎе,

2) В сети (g,j) у любой вершины, кроме источника и стока, полустепень исхода равна полустепени захода. Число j(е) называется значением потока через дугу е.

На рис. 6.16 приведен пример потока через сеть, изображенную на рис. 6.15. Значения функции j указаны в скобках.

Предложение. Пусть j - поток через сеть N=(G, a). Тогда сумма потоков через дуги, инцидентные источнику, равна сумме потоков через дуги, инцидентные стоку.

Доказательство. Пусть V={v₁,v₂,…,v_n}, причем v₁ – источник, v₂ - сток. Рассмотрим сеть N’=(G,j). В сети N’ сумма полустепеней исхода всех вершин равна сумме полустепеней захода всех вершин

r^–(v₁) + r^–(v₂) + r^–(v₃) +… + r^–(v_n) = r⁺(v₁) + r⁺(v₂) + r⁺(v₃) + … + r⁺(v_n),

поскольку для любой дуги е число j(е) участвует ровно один раз, как в левой, так и в правой сумме. Так как j - поток, то r^–(v_i) = r⁺(v_i) для i=3,…,n. Это означает, что r^–(v₁) +r^–(v₂) = r⁺(v₁) + r⁺(v₂). Из последнего равенства получаем равенство r^–(v₁) = r⁺(v₂), потому что

r^–(v₂) = 0 и r⁺(v₁) = 0.

Предложение доказано.

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

Величину потока j будем обозначать через ½j½. Поток, приведенный на рис. 6.16, имеет величину 5. Этот поток является максимальным, поскольку его значение на дугах, инцидентных стоку, равно сумме пропускных способностей этих дуг. Сеть может иметь несколько максимальных потоков, как показывает пример, приведенный на рис. 6.17

При изучении максимальных потоков в сети используется понятие разреза.

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

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

Так, например, для сети на рис. 6.18 примерами разрезов будут множества S₁={(a,y), (a,x), (a,z)}, S₂={(a,z), (x,z), (y,z), (y,b)}, S₃={(y,b), z,b)}. Эти разрезы имеют пропускные способности соответственно 7,6 и 6. Разрезы S₂ и S₃ являются минимальными. Мы видим, что минимальных разрезов может быть несколько.

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