Максимальний потік та мінімальний розріз у мережі

Ця сторінка призначена для студентів, що вивчають курс дискретної математики та (або) теорії графів. Безпосередньо з неї ви можете виконати своє ІДЗ, навіть якщо у вас немає на комп’ютері MATLAB. Якщо ж у вас є MATLAB, перейдіть на цю сторінку: там у вас є можливість втрутитися у сценарій (програму) обчислень. А на цій сторінці задача про максимальний потік розв’язується шляхом зведення до задачі лінійного програмування.

Введемо позначення:

Тоді задача про максимальний потік у мережі може бути сформульована як задача лінійного програмування:

Максимізується загальний потік, що виходить із джерела (1). При цьому в будь-якій проміжній вершині вхідний потік дорівнює вихідному (2), а пропускні здатності дуг обмежені (3). Докладніше див. тут, стор. 115.

Задача, двоїста до задачі про максимальний потік − це задача про мінімальний розріз. Для побудови мінімального розрізу можна скористатися теоремами двоїстості. Треба:

Для виродженої задачі на цій сторінці будується перший, найближчий до джерела мінімальний розріз.

Для правильної роботи з цією сторінкою ваш браузер повинен підтримувати сценарії Java Script. Увімкніть їх.

Введіть вхідні дані в області введення нижче. У першій області треба (точніше, можна) ввести координати вершин для малювання орграфа мережі. Вони задаються у вигляді матриці n×2: у першому стовпці − x координати, у другому − y-і. Числа можна задавати цілі, з десятичною точкою або в експоненційній формі. Числа розділяйте пробілами. Загальна кількість рядків у цій області введення визначає розмір орграфа n − кількість вершин. Ці вхідні дані (координати вершин) не є обов’язковими: якщо їх не задати, то орграф буде малюватися у вигляді правильного n-кутника, а кількість вершин буде визначатися максимальним номером вершини у наступній області введення.

В наступній області введення ліва частина є обов’язковою для заповнення. В ній визначається структура орграфа мережі. Кожна дуга в орграфі поєднує дві вершини. Номери цих вершин задаються у вигляді матриці m×2 у лівій частині другої області введення. В кожному рядку спочатку записується номер першої вершини дуги (хвоста, джерела), а потім номер другої вершини (вістря, приймача). У цих стовпцях повинні бути натуральні числа від 1 до n включно. Числа розділяйте пробілами. У правій частині цієї області введення задаються пропускні здатності дуг − додатні дійсні числа. Якщо цей стовпчик не заданий, то всі ваги вважаються одинаковими (одиничними). Загальна кількість чисел у кожному з цих стовпців визначає потужність орграфа мережі m − кількість дуг.

Координати вершин
x   (пробіл)   y

Дуги та їхні пропускні здатності
v1  (пробіл)  v2 Пропускна здатність