Geum.ru

Поиск максимальных потоков в сетях

Дипломная работа - Математика и статистика

Другие дипломы по предмету Математика и статистика

/i>6) на 1.

22. Вершина v4 имеет пометку (+v2, 1). Поэтому увеличиваем поток по дуге (v2, v4) на 1.

23. Вершина v2 имеет пометку (-v3, 1). Поэтому уменьшаем поток по дуге (v2, v3) на 1.

24. Вершина v3 имеет пометку (+v1, 1). Поэтому увеличиваем поток по дуге (v1, v3) на 1. Получили новый поток величины 5 (рис. 3.10).

 

Рис. 3.10. Поток величины 5

 

25. Стираем все пометки.

26. Присваиваем вершине v1 пометку (+, ?).

27. Вершины, смежные вершине v1, нельзя пометить, поскольку дуга (v1, v2) насыщена ?(v1, v2) = ?(е1) = с(е1) = 3, и дуга (v1, v3) тоже насыщена ?(v1, v3) = ?(е2) = с(е2) = 2. Сток остался непомеченным. Значит, полученный поток максимален.

А теперь найдём максимальный поток с помощью программы. Для этого введём матрицу пропускных способностей в соответствующие поля программы. Матрица имеет следующий вид:

 

Результат вычислений оказался тем же. Мы получили максимальный поток величины 5 (рис. 3.11).

Рис. 3.11.

 

3.4. Описание программного кода

 

Прикладная программа Max_potоk написана языком Object Pascal в интегрированной среде Delphi7.

Окно программы (Form1: TForm) содержит такие компоненты:

  1. текстовые поля (Eij: TEdit ; Inij: TEdit (i,j = 1..10));

компоненты (STy: TStaticText (y = 1..10), OSTx: TStaticText (x = 1..10), VSTz: TStaticText (z = 1..10), OVSTe: TStaticText (e = 1..10), StaticTextij: TStaticText (i = 4, j = 1..4));

  1. надписи (Label1, Label2, Label3: TLabel);
  2. панель группировки компонентов (GB1: TGroupBox);
  3. кнопки (Buttonk: TButton (k = 1..5)).

В программе отслеживается 7 действий (табл. 6).

 

Таблица 6

Название действияНазначениеTButton1.ClickРассчитывает максимальный потокTButton2.ClickСоздаёт таблицы матриц пропускных способностей и потока заданной размерностиTButton3.ClickСчитает одну итерациюTButton4.Click Выводит пометкиTButton5.ClickНачинает итерацию зановоTForm1.Create Задаёт высоту и ширину окна программыTForm1.CloseСовершает затухание формы при её закрытии

Предназначение текстовых полей приведено в таблице 7.

Метка поляНазвание поляПредназначениеКоличествоColЗадаётся количество вершин сетиs=SSSЗадаётся источник сетиt=TTTЗадаётся сток сетиВершинар1Задаётся вершина, пометки которой будут рассчитыватьсяПредыдущая вершинар2Выводятся пометки вершиныЗнакр3р4Максимальный потокmaxВыводится максимальный поток сетиXijInijЗадаётся матрица пропускных способностей сетиXijEijВыводится матрица потока в сетиТаблица 7

 

ВЫВОДЫ

 

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

В данной работе изучалась эта проблема, была рассмотрена теория, которая изучает методы поиска максимальных потоков в сетях, изучен алгоритм поиска максимального потока (алгоритм Форда-Фалкерсона), в интегрированной среде Delphi было разработано дополнение, которое позволяет в удобной для пользователя форме найти максимальный поток в заданной сети.

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

ЛИТЕРАТУРА

 

  1. Алгоритмы и программы решения задач на графах и сетях. Отв. ред. М.И. Нечепуренко. Новосибирск: Наука. Сиб. отделение, 1990. 513 с.
  2. АндрійчукВ.І., КомарницькийМ.Я., Іщук Ю.Б. Вступ до дискретної математики: Навчальний посібник. Київ: Центр навчальної літератури, 2004. 254 с.
  3. АрхангельскийА.Я. Приемы программирования в Delphi. Версии 57. М.: ЗАО Издательство БИНОМ, 2003.
  4. Дискретна математика: Підручник/ Ю.М.Бардачов, Н.А.Соколова, В.Є.Ходаков; за ред. В.Є.Ходакова. К.: Вища шк., 2002. 287 с.: іл.
  5. Дискретная математика: логика, группы, графы/ О.Е. Акимов. 2-е изд., доп. М.: Лаборатория Базовых Знаний, 2003. 376 с.: ил.
  6. Зыков А.А. Основы теории графов. М.: Наука, 1987. 381 с.
  7. КлимоваЛ.М. Delphi 7. Основы программирования. Решение типовых задач. Самоучитель М.: КУДИЦ-ОБРАЗ, 2004. 480 с.
  8. КрістофідесР. “Теория графов”. Переклад на російську мову “Мир” 1978.
  9. Лекции по дискретной математике/ Ю.В. Капитонова, С.Л. Кривой, А.А. Летичевский и др. СПб.: БХВ-Петербург, 2004. 624 с.
  10. Лекции по теории графов/ Емеличев В.А., Мельниченков О.И., Сарванов В.И., Тышкевич Р.И. М.: Наука, Гл. ред. физ.-мат. лит., 1990. 384 с.
  11. Лекции по теории графов: Учебн. пособие. М.: Наука, 1990. 384 с.
  12. ЛипскийВ. Комбинаторика для программистов: Пер. с польск. М.: Мир, 1988. 213 с.: ил.
  13. Магрупов Т.М. Графы, сети, алгоритмы и их приложения/ Под ред. Ф.Б. Абуталиева; АН УсССР, Ин-т кибернетики с ВЦ УзНПО “Кибернетика”: Ташкент: Фан, 1990. 120 с.
  14. Математическое программирование (с элементами информационных технологий): Учеб. пособие для студ. нематемат. спец. вузов/ В.Р.Кулян, Е.А.Юнькова, А.Б.Жильцов. К.: МАУП, 2000. 124 с.: ил.
  15. Мiхайленко В.М. Дискретна математика. К.: Європейський ун-т, 2003. 319.
  16. НовиковФ.А. Дискретная математика для программистов. СПб.: Питер, 2004. 302 с.: ил.
  17. СеджвікД. “Програмирование на С++. Часть 5. Алгоритмы на графах”. Київ, 2003.
  18. Теория графов и её применение: сборник научных трудов/ Институт математики им. С.Л. Соболева. Новосибирск, 1996. 106 с.
  19. Яблонский С.В. Введение в дискретную митематику. М.: Наука, 1986. 384 с.