Этап 3.

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

Строим разрез на сети. Разбиваем множество вершин на два подмножества: A и B. Помеченные вершины образуют множество , непомеченные – множество .

Проводим разрез , который состоит из дуг , , , :

.

Определяем величину максимального потока :

(ед.)

Заключение

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

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

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

1. Алгоритмы и программы решения задач на графах и сетях. Отв. ред. М.И. Нечепуренко. – Новосибирск: Наука. Сиб. отделение, 1990. – 513 с.

2. Андрійчук В.І., Комарницький М.Я., Іщук Ю.Б. Вступ до дискретної математики: Навчальний посібник. – Київ: Центр навчальної літератури, 2004. – 254 с.

3. Архангельский А.Я. Приемы программирования в Delphi. Версии 5 – 7. М.: ЗАО «Издательство БИНОМ», 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 с.

---

Дата добавления: 2015-08-09