скачать Московский Государственный Институт Делового Администрирования КУРСОВАЯ РАБОТА На тему: «Транспортные сети. Задача о максимальном потоке в сети» Работу выполнила: Болотина Юлия Работу проверил: Аллавердиев А.М Москва 2003 СодержаниеВведение………………………………………………………………3стр Теоретическая часть………………………………………..………. 4стр Теорема Форда-Фалкерсона…………………………………………. Алгоритм решения……………………………………………...…….5стр Поток в транспортной сети…………………………………………..7стр Орграф приращений…………………………………………………10стр Алгоритм построения максимального потока В транспортной сети………………………………………………10стр Практическая часть…………………………………………….. .…12стр Этап 1…………………………………………………………………12стр Этап 2………………………………………………………………... 13стр Этап 3………………………………………………………………....13стр Этап 4……………………………………………………………...….14стр Этап 5…………………………………………………………………14стр Заключение…………………………………………………………..16стр Список используемой литературы……………………………..…..17стр Введение. В своей курсовой работе я рассматриваю тему «Транспортные сети». ^ • Транспортные сети; • Поток в транспортной сети; • Орграф приращений; • Алгоритм построения максимального потока в транспортной сети и т.д. В задаче, которую я рассматриваю, да и вообще в задачах на данную тему фундаментальную роль играет изучение поперечных сечений сети (то есть множеств дуг, которые соединяют вершины двух не пересекающихся множеств вершин) и нахождение ограниченного поперечного сечения, которое является самым узким местом. Эти узкие места определяют пропускную способность системы в целом. ^ Транспортной сетью называется конечный Связный орграф G(V, E) без петель, каждой дуге которого поставлено в соответствие некоторое неотрицательное число c( ![]()
Потоком сети называется неотрицательная функция f(1) такая, что f(e) меньше или равно c(e). (Поток не может превышать пропускную способность дуги.) Дуга ![]() ![]() Разрезом L сети G(V,E) называется множество насыщенных дуг, отделяющих источник s от стока t. Теорема Форда-Фалкерсона. Пусть D – транспортная сеть, ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Пусть ![]() ![]() ![]() ![]() Если ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Следствие 1. Используя теорему Форда-Фалкерсона получаем, что величина максимального потока в транспортной сети равна пропускной способности минимального разреза. Следствие 2. Пусть ![]() ![]() ![]() Алгоритм решения. Сначала будем строить полный поток, затем проверим, можно ли его увеличить. Если нет, то этот поток является максимальным. Если же его можно увеличить, то будем строить другой полный поток и т.д. Решать задачу будем с помощью метода расстановки пометок. ^ операция расстановки пометок; операция изменения потока. Рассмотрим первую процедуру. Для каждой вершины данной сети нужно приписать пометку, которая имеет следующий вид: ![]() ![]() ![]() ![]()
Расставлять пометки начнем с источника S. Он получит пометку ![]() Вершина ![]() ![]() ![]() Теперь все вершины ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() процедуре 2. Рассмотрим процедуру изменения потока. Если вершина ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Переходим к следующей вершине и так до тех пор, пока не достигнем источника S. Здесь изменение потока прекращается. Далее переходим к процедуре 1 и так до тех пор, пока величину потока уже нельзя изменить. Рассмотрим конкретную задачу о нахождении максимального потока в сети. Дана сеть G(V,E) (рис. 11) с источником S и стоком t. Пропускные способности дуг указаны. Найти максимальный поток из S в t. Поток в транспортной сети. Функция ![]() •для любой дуги ![]() ![]() ![]() ![]() •для любой промежуточной вершины v выполняется равенство ![]() т.е. сумма потоков по дугам, заходящим в v, равна сумме потоков по дугам, исходящим из v. ![]() ![]() ![]() ![]() ![]() ![]() Пример. На рисунке показан допустимый поток в транспортной сети. При каждой дуге указана величина потока по ней. Очевидно, что выполняются все условия, перечисленные в определении допустимого потока (проверяем выполнение второго условия для промежуточных вершин ![]() Для любого допустимого потока ![]() ![]() По определению допустимого потока ![]() ![]() ![]() Заметим, что для каждой дуги ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Величиной потока ![]() ![]() ![]() ![]() ![]() Пусть ![]() ![]() ![]() ![]() ![]() Поток ![]() ![]() Очевидно, что максимальный поток ![]() ![]() ![]() ![]() Орграф приращений. Введем для заданной транспортной сети D и допустимого потока ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() т.е. орграф ![]() ![]() ![]() ![]() Алгоритм построения максимального потока в транспортной сети. Важным следствием теоремы Форда-Фалкерсона является Алгоритм построения максимального потока в транспортной сети. Алгоритм: Шаг 1. Полагаем i=0. Пусть ![]() ![]() Шаг 2. По сети D и потоку ![]() ![]() Шаг 3. Находим простую цепь ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ^ Задача о максимальном потоке. Для заданной транспортной сети определить величину максимального потока грузов, которые можно доставить в течение заданного времени из города S в город t. Пропускные способности всех участков дорог считаются известными. Этап 1. Начнём с процедуры расстановки пометок. Пометка источника S ![]() ![]() Просмотрим вершину S, для этого пометим вершиныV , V , V . Просмотрим вершину V , ставим метки ![]() ![]() ![]() ![]() Изменение потока: ![]() Поэтому заменим величину первоначального потока: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Этап 2. Просмотрим вершину V1, вершины V4 и V2 получают метки ![]() ![]() Изменение потока: ![]() Вносим изменения потока. Дуга (V2, t) стала насыщенной. ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Этап 3. Просмотрим вершину V1. Вершины V4 и V2 получают метки Просмотрим V3, V2 уже помечена, Просмотрим V2, V4 уже помечена, Просмотрим V4, Изменение потока: ![]() Вносим изменения потока. Дуга (V3,V2) стала насыщенной. ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Этап 4. Просмотрим вершину V3. Вершины V2 и V3 получают метки Просмотрим V2. Вершины V4, V5 и t получают метки Изменение потока: Вносим изменения потока. Дуга (V3, V2) стала насыщенной. ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Этап 5. Просмотрим вершину V3. Вершина V6 получает метку Просмотрим V6 Изменение потока: ![]() Вносим изменения потока. Дуга (S,V3) стала насыщенной. ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Поток f=21 является максимальным, а множество дуг ![]() Заключение. Бурное развитие дискретной математики обусловлено прогрессом компьютерной техники, необходимостью создания средств обработки и передачи информации, а также представления различных моделей на компьютерах, являющихся по своей природе конечными структурами. ^ называется конечный Связный орграф G(V, E) без петель, каждой дуге которого поставлено в соответствие некоторое неотрицательное число c( ![]() 1) ровно одна вершина ![]()
Список используемой литературы1. А.М. Аллавердиев, И.В. Платонова «Прикладная математика. Элементы теории графов» М.2000 2. Лекции по прикладной математике И.В. Платоновой 3. В.Н. Нефедов, В.А. Осипова «Курс дискретной математики» М. 1992 4. С.В. Судоплатов, Е.В. Овчинникова «Элементы дискретной математики» М. 2002
|