Нахождение максимального потока в сети

Краткая выдержка из текста работы (Аннотация)

Введение

Бурное развитие дискретной математики обусловлено прогрессом компьютерной техники, необходимостью создания средств обработки и передачи информации, а также представления различных моделей на компьютерах, являющихся по своей природе конечными структурами. Задача о максимальном потоке в сети изучается уже более 60 лет. Интерес к ней подогревается огромной практической значимостью этой проблемы. Методы решения задачи применяются на транспортных, коммуникационных, электрических сетях, при моделировании различных процессов физики и химии, в некоторых операциях над матрицами, для решения родственных задач теории графов, и даже для поиска Web-групп в WWW. Исследования данной задачи проводятся во множестве крупнейших университетов мира. 60 лет назад, задача о максимальном потоке решалась simplex методом линейного программирования, что было крайне не эффективно. Форд и Фалкресон предложили рассматривать для решения этой задачи ориентированную сеть и искать решение с помощью итерационного алгоритма. В течение 20 лет, все передовые достижения в исследовании данной задачи базировались на их методе. В 1970г. наш соотечественник, Диниц, предложил решать задачу с использованием вспомогательных бесконтурных сетей и псевдомаксимальных потоков, что намного увеличило быстродействие разрабатываемых алгоритмов. А в 1974 Карзанов улучшил метод Диница, введя такое понятие как предпоток. Алгоритмы Диница и Карзанова, как и исследования Форда и Фалкерсона, внесли огромный вклад в решение данной проблемы. На основе их методов 15 лет достигались наилучшие оценки быстродействия алгоритмов. В 1986г. появился третий метод, который также без раздумий можно отнести к фундаментальным. Этот метод был разработан Голдбергом и Таряном, и получил название Push-Relabel метода. Для нахождения максимального потока, он использует предпотоки и метки, изменяемые во время работы алгоритма. Push-Relabel алгоритмы очень эффективны, и исследуются до сих пор. И, наконец, в 1997г. Голдберг и Рао предложили алгоритм, присваивающий дугам неединичную длину. Это самый современный из всех известных мне алгоритмов.

Содержание работы

Содержание

Введение 3

1. Теория и основные понятия 4

2. Поток в транспортной сети 6

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

4. Сети, потоки в сетях. Теорема Форда – Фалкерсона 10

5. Реализация 14

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

Заключение 18

Список литературы 19

Использованная литература

1. М.О. Осанов, В.А. Баранский, В.В. Расин, Дискретная математика: графы, матроиды, алгоритмы – Ижевск, НИЦ «Регулярная и хаотическая динамика»; 2001.
2. А.И. Белоусов, С.Б. Ткачев, Дискретная математика: учебник для вузов – Изд – во МГТУ им. Н.Э. Баумана;2004.
3. В.Н. Нефедов, В.А. Осипова «Курс дискретной математики» М. 1992
4. С.В. Судоплатов, Е.В. Овчинникова «Элементы дискретной математики» М. 2002
5. \"Алгоритмы. Построение и анализ\" Т. Кормен, Ч. Лейзерсон, Р. Ривест (\"Introduction to Algorithms\" Thomas Cormen, Charles Leiserson, Roland Rivest) , стр. 536 - 573.
6. Методическое пособие - Элементы теории множеств и теории графов. Сборник задач и упражнений по курсу Дискретная математика, М. 1992

Другие похожие работы

• Контрольная - Контрольная работа №1 и №2 по линейной алгебре, вариант 8
• Контрольная - Контрольная работа по математическим методам в управлении
• Контрольная - Методичка Е.С. Мироненко, контрольные работы 5,6 Вариант 12
• Контрольная - Практические задания по высшей математике и математическому анализу выполненные в системе MATHCAD 11 и DERIVE 5
• Контрольная - Контрольная работа по высшей математике
• Шпаргалка - Ряды
• Курсовая - Математические основы дискретных систем. Решение 6 заданий.
• Контрольная - Даны уравнения двух сторон треугольника 5х–4y+15=0 и 4х+y–9=0. Его медианы пересекаются в точке (0;2). Составить уравнение третьей стороны треугольника.
• Курсовая - Тема по алгебре:Корни многочлена от одного неизвестного
• Контрольная - Методы решения систем линейных уравнений