Задача про максимальний потік у транспортній мережі

Транспортною мережею (s/t-мережі) назвемо зв`язний орієнтований граф без петель, у якого є дві особливі вершини s (джерело) та t (стік). Причому:

з вершини s дуги тільки виходять, а у вершину t – тільки заходять;

кожній дузі транспортної мережі приписана невід`ємна величина, яка називається пропускною спроможністю дуги і позначається c_ij.

Зафіксуємо деяку вершину s/t-мережі х_к. Для поняття потоку транспортної мережі розглянемо дві множини А-множина всіх вершин s/t-мережі, з яких виходить дуга та заходить у вершину х_к, та В – множина всіх вершин s/t-мережі, які безпосередньо слідують за вершиною х_к. Тоді потоком в s/t-мережі будемо називати невід`ємну величину j_ij (для деякої дуги u_ij)=v, якщо виконуються наступні умови:

j_ij £ c_ij , для будь-якої дуги графа;

Перша умова говорить, що для будь-якої дуги транспортної мережі потік не перевищує пропускну спроможність транспортної мережі, а друга про те, що для будь –якої вершини транспортної мережі сумарний потік, що входить у вершину, рівний сумарному потоку, що виходить з вершини, тобто потік неподільний.

Нехай Х – множина всіх вершин s/t-мережі. Розіб`ємо її на дві підмножини Х₁ та Х₂ таким чином, щоб:

Тоді розтином s/t-мережі назвемо множину всіх дуг, що слідують з множини вершин Х₁ до множини вершин Х₂, позначимо (Х₁, Х₂). Величина розтину рівна сумі пропускних спроможностей дуг, що створюють розтин, та позначається v(X₁, X₂).

Задача про визначення максимального потоку в транспортній мережі є основною задачею оптимізації на графах. Її рішення базується на наступній теоремі Форда-Фалкерсона: максимальний потік у транспортній мережі дорівнює величині найменшого розтину в ній.

Задача 4. Транспортну мережу задано графічно. Необхідно знайти максимальний потік в s/t-мережі.

Розв`язок. Кожній дузі графа припишемо пару чисел c<sub>ij</sub>, j<sub>ij</sub>. На початку в s/t-мережі розподілимо нульовий потік, тобто j<sub>ij</sub>=0. Далі для розмітки будь-якої к-ї вершини будемо використовувати позначення к(і<sup>+</sup>, e(к)) або к(і<sup>-</sup>, e(к)), де і- номер вершини, з якої ми потрапили до вершини к, ‘+’ - по прямій дузі, ‘-‘ - по зворотній дузі, e(к) – невід`ємна величина, на яку можна збільшити потік (для прямої дуги) або зменшити (для зворотної дуги). Вершина s завжди має особливу помітку (s⁺, ¥). Помічати вершини по прямих дугах можна, якщо на цих дугах потік можливо збільшити ( c_ij-j_ij >0), а по зворотніх – якщо потік можливо зменшити (j_ij >0). Для вершини к(і⁺, e(к)) e(к)=min(e(i), c_ik-j_ik), а для вершини к(і^-, e(к)) e(к)=min(e(i), j_ik). Перший крок будь-якого етапу полягає у розставленні поміток вершин мережі, доки або не буде помічено вершину t , тоді переходимо на другий крок, або переконаємося, що вершину t помітити неможливо (задачу вирішено).

1-й єтап.

1-й крок. S(s⁺,¥). Далі помічаємо вершини суміжні з s. 1(s⁺, min(¥,10-0) , тобто 1(s⁺,10). Аналогічно 2(s⁺,15), 3(s⁺,15). Тепер вершина s розглянута. Для подальшого розгляду вибираємо будь-яку із суміжних помічених вершин. Наприклад, вершину 3. Помічаємо вершини, суміжні з третьою: 2(3⁺, min(15, 10-0)=10), t(3⁺, min(15,8-0)=8) Помітили вершину t – переходимо до друго кроку 1-го етапу.

2-й крок. За допомогою поміток вершин будуємо ланцюг, який приводить з вершини s у вершину t: t3s. На прямих дугах ланцюга потік збільшуємо на величину e(t), а на зворотній – зменшуємо на цю саму величину. На малюнку показано розподіл потоку після виконання першого етапу. Переходимо до другого етапу, який виконуємо аналогічно першому.

2-й етап.

S(s+,¥)

1(s+,10) 2(s+,15) 3(s+,7)

t(2+,15) t2s e(t)=15

3-й етап.

S(s+,¥)

1(s+,10) 3(s+,7)

4(1+,7) t(1+,7) t1s e(t)=7

Після 2-го та 3-го етапів розподіл потоку у мережі показано на малюнку.

4-й етап.

S(s+,¥)

1(s+,3) 3(s+,7)

2(3+,7)

t(2+,5) t23s e(t)=5

5-й етап.

S(s+,¥)

1(s+,3) 3(s+,2)

4(1+,3)

t(4+,3) t41s e(t)=3

6-й етап.

S(s+,¥)

3(s+,2)

2(3+,2)

S(2-,2)

На 1-му кроці 6-го етапу прийшли до побудови контуру навколо вершини s, а в вершину t так і не потрапили. Це свідчить про те, що потік у мережі збільшити неможливо. Будуємо розтин мережі: віднесемо до множини Х₁ усі вершини, що помічені на 6-му кроці, а до множини Х₂ – ті, що не помічені. Х₁={s, 2, 3}, X₂={1, 4, t}, (X₁, X₂)={u_s1, u_2t, u_3t}, v(X₁, X₂)=c_s1+c_2t+c_3t=10+20+8=38. Перевірка: якщо просумувати всі значення e(t): 8+15+7+5+3=38, то отримаємо те саме значення величини розрізу.

Результуючій розподіл потоку в мережі має вигляд

На малюнку також показано розріз найменшої величини, який побудовано у розглянутому прикладі.

Контрольна робота №3.

Завдання №1

Задано граф G. Представити граф у виді матриць суміжності й суміжності ваг. Знайти найкоротший шлях і його довжину між двома зазначеними вершинами графа (варіант із номером, який кратний 2, - методом Дейкстри, інші варіанти - методом Форда, за необхідності розставивши напрямок дуг від вершини з меншим індексом до вершини з більшим індексом). Варіанти завдань знаходяться у додатку.

Завдання №2

Орієнтований граф G=(X,U) заданий у видгляді матриці суміжності ваг С. Потрібно:

1) представити граф графічно й у видгляді матриці інциденцій;

2) визначити хроматичне число графа;

3) використовуючи метод Шимбела, визначити найкоротші відстані між будь-якими двома вершинами графа.

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

11. 12.

13. 14.

15. 16.

17. 18.

19. 20.

21. 22.

23. 24.

25. 26.

27. 28.

29. 30.

Завдання №3

У розподільній системі опрацювання даних у деякий момент часу є n ресурсів готових до виконання завдань. У систему надходить n завдань. Відома якість виконання завдань кожним ресурсом (коефіцієнти матриці С). Потрібно призначити кожному ресурсу своє завдання таким чином, щоб якість виконання всіх завдань була максимальною.

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

11. 12.

13. 14.

15. 16.

17. 18.

19. 20.

21. 22.

23. 24.

25. 26.

27. 28.

29. 30.

Завдання №4

Транспортна мережа задана за допомогою таблиці, де зазначені дуги мережі і пропускна спроможність цих дуг. Необхідно представити граф графічно і, використовуючи теорему Форда-Фалкерсона, визначити найбільший потік у мережі (s - джерело, t - стік). Перелік дуг мережі у вигляді

1. u_s1=13, u_s2=17, u_s3=1, u_1t=7, u₁₃=5, u₂₃=2, u₂₄=17, u₃₄=1, u_3t=2, u_4t=12

2. u_s1=16, u_s2=14, u₁₃=9, u₂₁=10, u₂₃=5, u₂₄=8, u₃₅=6, u_3t=9, u₄₅=1, u_4t=6, u_5t=6.

3. u_s1=6, u_s2=10, u_s3=3, u₁₂=3, u₁₄=2, u₁₃=2, u₂₄=1, u_2t=8, u₃₂=4, u₃₄=5, u_4t=9

4. u_s1=3, u_s2=5, u_s3=4, u_s4=1, u_1t=7, u₂₁=2, u₂₄=1, u_2t=1, u₃₂=3, u₃₄=2, u_4t=3

5. u_s1=25, u_s2=18, u₁₂=4, u₁₄=10, u₂₄=10, u_2t=15, u_3t=5, u₄₃=10, u_4t=10

6. u_s1=5, u_s2=4, u_s3=6, u_1t=4, u₁₄=1, u₁₃=1, u₂₃=3, u₂₄=2, u₃₄=2, u_3t=3, u_4t=7

7. u_s1=12, u_s2=20, u_s3=5, u_1t=10, u₁₃=8, u₂₃=5, u₂₄=10, u₃₄=4, u_3t=8, u_4t=12

8. u_s1=8, u_s3=4, u_s4=6, u₁₂=4, u₂₄=2, u_2t=10, u₃₁=3, u₃₂=2, u₃₄=5, u_4t=7

9. u_s1=10, u_s2=10, u_s3=15, u₁₄=7, u₁₂=4, u₂₄=6, u₃₂=5, u_3t=20, u_4t=10

10. u_s1=6, u_s2=7, u_s3=5, u₁₂=3, u₁₄=2, u₁₃=1, u₂₃=4, u₂₄=2, u_2t=3, u_3t=7, u_4t=8

11. u_s1=5, u_s2=6, u_s3=8, u₁₂=2, u₁₄=3, u₁₃=1, u₂₄=1, u_2t=4, u_3t=5, u_4t=6

12. u_s1=10, u_s2=3, u_s3=15, u_1t=5, u₁₂=8, u₂₃=16, u₂₄=4, u_2t=15, u₃₄=5, u_4t=20

13. u_s1=7, u_s4=15, u_st=5, u_1t=3, u₁₃=5, u₂₁=10, u₃₄=3, u₄₂=20, u_4t=6

14. u_s1=20, u_s4=5, u₁₂=17, u₁₃=6, u₂₄=10, u_2t=3, u₃₂=10, u_3t=5, u_4t=20

15. u_s1=25, u_s3=40, u₁₄=20, u₁₃=15, u_2t=40, u₃₂=20, u_3t=15, u_4t=7

16. u_s1=6, u_s2=14, u_1t=10, u₁₄=3, u₂₃=3, u₂₁=10, u₂₄=2, u₃₄=5, u_4t=8

17. u_s1=5, u_s2=18, u_s5=7, u₁₄=15, u₂₃=25, u₃₅=10, u_3t=4, u₄₃=10, u_4t=10, u_5t=2

18. u_s1=20, u_s2=10, u_s3=15, u₁₂=15, u₂₃=20, u₂₅=15,u₃₄=4,u₃₅=8, u_3t=1,u_4t=20,u_5t=4

19. u_s1=10, u_s2=5, u_s4=10, u₁₂=1, u₁₃=5, u₁₄=8, u₃₄=4, u_3t=4, u₄₂=5, u_2t=20

20. u_s1=15, u_s2=20, u_s3=5, u_1t=15, u₁₂=8, u₂₃=16, u₂₄=4, u_2t=10, u₃₄=5, u_4t=3

21. u_s1=10, u_s3=15, u₁₄=8, u_1t=13, u₂₄=15, u₃₁=6, u₃₂=3, u_3t=5, u_4t=12

22. u_s3=10, u_s4=15, u_1t=13, u_2t=20, u₃₁=8, u₃₄=5, u₄₁=2, u₄₂=8, u_4t=12

23. u_s1=15, u_s2=12, u_s3=11, u_1t=9, u₁₄=7, u₁₃=6, u₂₃=7, u₂₁=10, u₃₄=8, u_3t=8, u_4t=17

24. u_s1=13, u_s2=17, u_s3=1, u_1t=7, u₁₃=5, u₂₃=2, u₂₄=17, u₃₄=1, u_3t=2, u_4t=12

25. u_s1=9, u_s2=7, u_s3=10, u_s4=12, u₁₃=6, u₁₄=8, u₂₃=6, u₂₄=6, u_3t=14, u₄₃=8, u_4t=10

26. u_s1=8, u_s2=7, u_s4=16, u_1t=7, u₁₂=5, u₂₃=10, u_3t=12, u₄₃=6, u₄₅=10, u₅₃=7, u_5t=9

27. u_s1=11, u_s2=19, u_1t=15, u₁₄=8, u₂₃=8, u₂₁=15, u₂₄=7, u₃₄=10, u_4t=13, u_2t=2

28. u_s1=10, u_s2=3, u_s3=15, u_1t=5, u₁₂=8, u₂₃=16, u₂₄=4, u_2t=15, u₃₄=5, u_4t=20

29. u_s1=5, u_s2=18, u_s5=7, u₁₄=15, u₂₃=25, u₃₅=10, u_3t=4, u₄₃=10, u_4t=10, u_5t=2

30. u_s1=25, u_s2=18, u₁₂=4, u₁₄=10, u₂₄=10, u_2t=15, u_3t=5, u₄₃=10, u_4t=10

31. u_s1=6, u_s2=10, u_s3=3, u₁₂=3, u₁₄=2, u₁₃=2, u₂₄=1, u_2t=8, u₃₂=4, u₃₄=5, u_4t=9

СПИСОК ЛІТЕРАТУРИ

1. Бардачов Ю.М., Соколова Н. А., Ходаков В.Є. Дискретна математика. – К. Вища школа , 2002. – 288 с.

2. Бондаренко М.Ф., Білоус Н.В., Руткас А.Г.Комп’ютерна дискретна математика. – Харків: Компанія СМІТ, 2004. – 480 с.

3. Капітонова Ю.В., Кривий С. Л., Летичевський о.А., Луцький Г.М., Печурін М. К. Основи дискретної математики: Підручник. – К.: ЛіфтСофт, 2000. –Т.2 – 380 с.

4. Новіков А.Ф. Дискретная математика. – СПб. Питер, 2004. – 302 с.

5. Тевяшев А.Д., Гусарова І.Г. Основи дискретної математики в прикладах і задачах.-Харків: ХНУРЕ, 2003.-272 с.

6. Андерсон Д.А. Дискретная математика и комбинаторика. – М. 2003, –960 с.

Методичні вказівки щодо практичних занять з навчальної дисципліни «Дискретна математика» до теми “теорія графів” для студентів денної форми навчання за напрямом 6.040302 – “Інформатика” (у тому числі скорочений термін навчання)

Укладачі к.т.н., доц. .А,І.Дерієнко

асист. І.І. Киба

Відповідальний за випуск: зав. кафедри інформатики та вищої математики проф. В.П. Ляшенко

Підп. до др. _________. Формат 60х84 1/16. Папір тип. Друк ризографія.

Ум. друк. арк. ____. Наклад _______ прим. Зам. №_______. Безкоштовно.

Видавничий відділ КрНУ

39614,м.Кременчук, вул. Першотравнева, 20