а) б або не буде позначення стовпець (мережі). Це означає, что вдалось віділіті шлях з пропускними здатністю больше нуля з в;
б) або переконаємося в тому, что Неможливо помітіті Нові зтовпці (в розглядуваніх рядках НЕ виявило додатних ЕЛЕМЕНТІВ, что містяться в непоміченіх стовпцях). У цьом випадка відсутній шлях з в, что проходити по дугах з пропускними здатністю больше нуля.
У випадка а) Шуканов шлях ц з в знаходимо, вікорістовуючі Мітки. Нехай остання вершина шляху, позначені номером k. За Цій помітці знаходимо попередня вершину (переглядаємо рядок, тут були помічені стовпець, и дуга () - остання в Шуканов шляху). Елемент, Який знаходится на перетіні-го рядка і-го стовпця, відмічаємо знаком мінус, а симетричний Йому елемент - знаком плюс. Мі розглядалі-ий рядок,-й стовпець поміченій, номером. Тому, рухаємося від елемента по-му стовпцю до r-го рядка. Продовжуємо цею процес до тих ПІР, пока не дійдемо до-го рядка и НЕ позначімо знаком мінус елемент цього рядка и знаком плюс симетричний Йому елемент. Нові зміни до Дії 2.
У випадка б) стовпчік, Який відповідає стоку, помітіті Неможливо. З цього віпліває, что НЕ існує больше шляху з пропускними здатністю больше нуля з в, і Основний етап, что повтроюється, завершено. Вершини, что знаходяться в постаченіх стовпцях, утворюють підмножіну R (ЦІ вершини досяжні по Деяк шляху Із джерела). Інші вершини входять в підмножіну). Дуги, Які Прокуратура: з вершин и входять в вершини и утворюють Розріз з мінімальною Пропускна здатністю.
. Знаходимо пропускну здатність в знайдення шляху. Під Пропускна здатністю Розуміємо максимальну кількість Речовини, яка может перемістітіся з в по шляху за Одиниця годині. Пропускна здатність шляху рівна найменшій Із пропускних здатностей дуг, Які належати до цього шляху.
. Візначаємо Залишкова пропускну здатність дуг знайдення шляху и симетричних до них. Для цього від ЕЛЕМЕНТІВ табліці віднімаємо, а до ЕЛЕМЕНТІВ додаємо. У результаті Виконання цієї Операції отрімаємо нову таблицю, аналогічну початковій, альо з іншімі Пропускна здатностямі.
После Отримання Нової табліці повертаємося до Дії 1 основного етапу, Який віконується до тихий ПІР, пока не отрімаємо кінцеву таблицю, яка НЕ ??містіть жодних шляху з в з пропускними здатністю больше нуля.
заключний етап. Від ЕЛЕМЕНТІВ початкової табліці віднімаємо відповідні елєменти табліці, якові мі отримай на последнего кроці. У результаті отрімаємо таблицю, додатні елєменти Якої Рівні величинам потоків по відповідніх дугах (). А Максимальний Потік в мережі - сумі ЕЛЕМЕНТІВ-го рядка або-го стовпця.
4. Завдання максімізації кількості призначеня у завданнях розподілу як завдання для найбільш Потік
4.1 Зведення задачі до задачі про Максимальний Потік
Задачу максімізації кількості призначеня у завданнях розподілу можна звесті до задачі Теорії графів. Для цього Кожній Із Вакансій и шкірному Із працівніків ставімие у відповідність вершину графа. Если Деяка Вакансія может буди зайнятості Деяк працівніком, то, відповідно, з вершини, что відає вакансії проводимо дугу до вершини, что відповідає даним працівнику. Додатково запроваджувані вершину, З якої Прокуратура: дуги до кожної Із вершин, что представляються вакансії. Ця вершина відіграє роль джерела. Такоже додатково що вводяться вершину, до Якої проводимо дуги з кожної Із верші, что пре...
