Московський Державний Інститут Ділового Адміністрування
В В В В В В В В В
Курсова робота
На тему: В«Транспортні мережі. Задача про максимальний потік в мережі В»
В В В В В В В
Роботу виконала: Болотіна Юлія
Роботу перевірив: Аллавердіев А.М
В В В В В В В
Москва 2003
Зміст
Теоретична частина ......................................................... 4стор
Теорема Форда-Фалкерсона .................................................
Алгоритм рішення ............................................................. 5стор
Потік у транспортній мережі .................................................. 7стор
Орграф збільшень ......................................................... 10стр
Алгоритм побудови максимального потоку
У транспортній мережі ...................................................... 10стор
Практична частина ..................................................... .... 12стор
Етап 1 ........................................................................... 12стор
Етап 2 ........................................................................... 13стор
Етап 3 ............................................................................ 13стор
Етап 4 ............................................................................ 14стор
Етап 5 ........................................................................... 14стор
Список використаної літератури ........................................ 17стор
Введення.
В В
У своїй роботі я розглядаю тему В«Транспортні мережіВ». Моя курсова робота складається з наступних розділів:
• Транспортні мережі;
• Потік у транспортній мережі;
• Орграф збільшень;
• Алгоритм побудови максимального потоку в транспортній мережі і т.д.
У задачі, яку я розглядаю, та і взагалі в задачах на дану тему фундаментальну роль відіграє вивчення поперечних перерізів мережі (тобто множин дуг, які з'єднують вершини двох не перетинаються множин вершин) і знаходження обмеженого поперечного перерізу, яке є найвужчим місцем. Ці вузькі місця визначають пропускну здатність системи в цілому.
В В В В В В В В В В В В В В В В В В
ТЕОРЕТИЧНА ЧАСТИНА:
В
Транспортної мережею називається кінцевий Зв'язний орграф G (V, E) без петель, кожній дузі якого поставлено у відповідність деяке невід'ємне число c (), зване пропускною здатністю дуги, і існує:
1) рівно одна вершина, у якому не заходить жодна дуга, звана джерелом або початком мережі ;
2) рівно...
