графа дорівнює мінімальній велічіні пропускної спроможності Перетин, что розділяє зазначені вершини.
Розглядаючі послідовно всі перетин, что розділяють вершини и та j, можна візначіті з них ті, Пожалуйста має мінімальну пропускну спроможність, и, тім самим, візначіті величину максимального потоку между зазначену вершинами.
Будемо вважаті, что КОЖЕН перетин завдань n-розрядно двійковім кодом, в якому вершин-виток відповідають одиниці, а вершин-стокам - нулі. Например, перетин, что розділяє вершини 1, 3, 5 і 2, 4 має код 10101.
Оскількі загальне число n-розрядно двійковіх кодів складає 2n, а коди 00 ... 0 и 11 ... 1 цієї статті не є кодами перетінів, існує 2n - 2 перетінів орієнтованого и 2n - 1 - 1 перетінів неорієнтованого графа. Таким чином, послідовність кодів перетінів відповідає послідовності звічайна двійковіх кодів.
Крок 1 R (00001)=(11110)=
Крок 2 R (00010)=(11101)=
Крок 3 R (00011)=(11100)=
Крок 4 R (00100)=(11011)=
Крок 5 R (00101)=(11010)=
Крок 6 R (00110)=(11001)=
Крок 7 R (00111)=(11000)=
Крок 8 R (01000)=(10111)=
Крок 9 R (01001)=(10110)=
Крок 10 R (01010)=(10101)=
Крок 11 R (01011)=(10100)=
Крок 12 R (01100)=(10011)=
Крок 13 R (01101)=(10010)=
Крок 14 R (01110)=(10001)=
Крок 15 R (01111)=(10000)=
Початкові величини максимального потоків между усіма парами вершин графа подаються у виде матриці и пріймаються НЕОБМЕЖЕНИЙ.
Створюється код Чергова Перетин и обчіслюється величина его пропускної здатності, яка порівнюється з Ранее отриманий величинами всех потоків, что розділяються зазначену Перетин.
Если Обчислено величина пропускної здатності Перетин менше, чем величина відповідного потоку, остання замінюється Першів.
После розгляданих всех перетінів графа автоматично створюється матриця величин максимальних потоків между усіма парами вершин графа, тобто, между усіма парами вузлів мережі перевезень Пошто.
Приклад
Крок 0: початковійКрок 1: R (00001)=R (11110)=7Вершина12345Вершина123451-9999999999991-99999999972999-9999999992999-99999973999999-9999993999999-99974999999999-9994999999999-75999999999999-57777-поштовий зв'язок мережа перевезення
Крок 5: R (00101)=R (11010)=6Крок 8: R (01000)=R (10111)=5Вершина12345Вершина123451-9996761-56762999-67625-555366-67365-674776-64756-656676-56576-
Крок 13: R (01101)=R (10010)=3Крок 15: R (01111)=R (10000)=6Вершина12345Вершина123451-33731-336323-53523-535335-37335-374733-34633-353573-53573-
При візначенні Шляхів передачі максимальних потоків между Вузли мережі перевезень Пошто нужно враховуваті, что наявність прямого маршрутом между Вузли и та j НЕ означає его обов'язкового использование.
Так, у відповідності до Розглянуто прикладові, максимальний потік между Вузли 1 і 5 ставити 3. У перетин з мінімальною пропускна здатністю, что розділяє Вузли 1 і 5, входять ребра (1,2), (3 , 4), (4,5).
Если для передачі максимального потоку вікорістаті прямий маршрут М1: 1 - 2 - 3 - 4 - 5 Із пропускна здатністю 1, ВІН позику всі зазначені ребра І, тім самим, перекріє Інші шляхи его передачі.
Передача максимального потоку буде забезпечен, если для цього вікорістаті комбіновані маршрути: М1, М5: 1 - 2 - 3 - 5 з пропускними здатністю1; М3, М2, М5: 1 - 4 - 3 - 5 з пропускними здатністю 1; М3, М1 1 - 4 - 5 з пропускними здатністю 1.
2.3 Варіанти виконан розрахунково-графічної роботи
) вікорістовуючі алгоритм Флойда, візначіті найкоротші маршрути между Вузли перевезень ПОШТА, если відомі місця Розташування вузлів поштового зв язку та відстані между ними;
) візначіті максимальний потік в мережі поштового зв язку, если відома структура мережі та максимальна пропускна здатність Шляхів, что існують между відділеннямі поштового зв язку;
) на Основі АНАЛІЗУ найкоротшіх маршрутів та Шляхів Із Максимальний потік поштовий відправлень между Вузли перевезень Пошто Скласти оптимальний маршрут перевезень поштовий відправлень від вихідного пункту маршруту (у відповідності до Завдання) до найбільш віддаленого відділення поштового зв язку (найбільш віддаленого за кількістю проміжніх вузлів та відстанню). План винен містіті мінімальну Кількість транзитних вузлів (алгоритм Літла).
Таблиця 1. Ви...
