Алгоритмы поиска максимального потока

Задача про максимальний потік у мережі вивчається вже більше 60 років. Інтерес до неї викликаний величезною практичною значимістю цієї проблеми. Методи розв'язання задачі застосовуються на транспортних, комунікаційних, електричних мережах, при моделюванні різних процесів фізики й хімії, у деяких операціях над матрицями, для розв'язку споріднених задач теорії графів, і навіть для пошуку Web-Груп в WWW. Дослідження даного задачі проводяться в багатьох найкрупніших університетів світу.
В середині XX століття, задача про максимальний потік розв’язувалася симплексним методом лінійного програмування, що було вкрай не ефективно.

Вступ3
1. Основні поняття теорії графів4
1.1 Графи. Види графів. Степінь вершини графа4
1.2 Представлення графів в пам’яті ЕОМ10
2. Задача про максимальний потік у мережі15
2.1. Поняття потоку у мережі. Розрізи15
2.2. Задача про максимальний потік в мережі22
2.2.1. Алгоритм Форда знаходження максимального потоку26
2.2.2. Алгоритм Едмондса– Карпа29
2.2.3. Алгоритм Дініца32
3. Практична частина35
3.1. Опис інтерфейсу програми та програмного коду35
3.2. Інструкція користувача36
3.3. Програмна реалізація алгоритмів36
3.4. Тестові приклади47
Висновки51
Список використаної літератури53