КДМ ЛК 7.5

1. Розділ 5. Теорія графів

2. 5.12. Мережі

⚫ дослідження перерізів і циклів у графі
⚫ течії у мережах
⚫ мережі з багатьма джерелами і
стоками

3. Дослідження перерізів і циклів у графі

В орієнтованому графі G=(X,Y,f) кожному циклу q
(тобто замкненому ланцюгу) можна поставити у
відповідність вектор-цикл q за таким правилом:
компонента qi рядку дорівнює нулю, якщо дуга уi
не входить до циклу q; якщо ж уi q, то qi=1 або
qi=-1 залежно від того, співпадає чи ні напрямок
дуги уi з обраним додатним напрямком обходу
циклу.

4.

Циклу q={у1, у2, у4, у6} у графі відповідає векторцикл
у1 у2 у3 у4 у5 у6 у7
q = (-1 1 0 1 0 -1 0)

5.

➢ Будь-яка максимальна лінійно незалежна множина
вектор-циклів, об'єднаних за рядками у матрицю
Q, називається матрицею циклів графа (іноді Q
називається «базисною матрицею циклів», а
матрицею циклів — сукупність всіх векторівциклів, взагалі кажучи, лінійно залежних).
➢ Перерізом (розрізом) s графа G називається певна
підмножина дуг, видалення якої збільшує число
компонент
зв'язності,
тому
підграф
G\s
складається з двох диз'юнктних частин G1 і G2,
зв'язок між якими у графі G здійснюється тільки
дугами перерізу s.

6.

Переріз графа
Переріз навколо вершини

7.

Для перерізу (як і для циклу) довільно вводиться
орієнтація — напрямок від одного боку перерізу
до іншого. Вектор-переріз s — це рядок s, у
якого компонента si=0, коли дуга уi не входить у
переріз s. Якщо дуга уi належить перерізу
узгоджено з обраною орієнтацією перерізу, то si=1;
якщо не узгоджено, то si=-1. Для перерізу s={у3, у4,
у6} у графі вектор-переріз дорівнює:
у1 у2 у3 у4 у5 у6 у7
s = (0 0 -1 1 0 1 0)

8.

➢ Матриця S, рядки якої утворюють максимальний
лінійно-незалежний
набір
вектор-перерізів,
називається матрицею перерізів (або «базисною
матрицею перерізів», на відміну від матриці всіх
перерізів графа) графа G. Стовпці матриць
перерізів і циклів нумеруються однаково —
дугами графа, а число їх рядків у загальному
випадку різне.
Теорема Пуанкаре. В графі G з m дугами кожний
вектор-цикл ортогональний будь-якому векторуперерізу.
T
q s = (q , s ) R m = 0

9.

➢ Каркас
Т зв'язного графа G=(X,Y,f) є, очевидно,
деревом Т = (X, YT, fT), що містить всі вершини
графа. Дуги графу, що не ввійшли до каркасу,
називають хордами.
Наприклад, один з каркасів графа G зображений
товстими лініями (каркас «великої ведмедиці») і
відповідно хорди {y7, y8, y9, y10} — тонкими
лініями.

10.

➢ Переріз
s називається фундаментальним (за
деревом Т), якщо він містить точно одну дугу уk
дерева Т, а орієнтація перерізу s узгоджена з
орієнтацією дуги уk. Здання дуги дерева повністю
визначає відповідний фундаментальний переріз.
На графі пунктирами зображено фундаментальні
перерізи s1, s2, ..., s6 за деревом Т «велика
ведмедиця».

11.

➢ Фундаментальною
матрицею перерізів ST (за
деревом Т) називається матриця, рядками якої є
вектор-перерізи, фундаментальні за деревом Т.
Виділеному дереву Т на графі відповідає
фундаментальна матриця перерізів, стовпці якої
позначені номерами дуг всього графа, рядки —
номерами дуг дерева, точніше, номерами
відповідних фундаментальних перерізів:

12.

➢ Фундаментальним циклом графа G (за деревом
Т) називається будь-який цикл, що містить точно
одну хорду уi і орієнтований узгоджено з її
напрямком.
Зрозуміло,
що
кожна
хорда
однозначно задає фундаментальний цикл qy, який
дуга уi замикає на дереві Т.
➢ Фундаментальною матрицею циклів QT (за
деревом T) називається матриця, рядки якої є всі
фундаментальні вектор-цикли за деревом Т.
Зауваження. Величина rang Q співпадає з
цикломатичним числом v=m-n+1 — числом
комірок плоского графа.

13. Течії у мережах

➢ Мережею будемо називати зважений орієнтований
зв'язний граф без петель і паралельних ребер.
Мережа є зручною моделлю при дослідженні
цілого ряду задач у транспорті, зв'язку та інших
областях, зв'язаних з дійсним або уявним рухом
товарів, інформації або людей. Введемо визначення
і позначення, типові для цього кола питань.
Розглянемо мережу G=(X,Y), |Х|=n, |Y|=m. Нехай
кожній дузі уj Y поставлено у відповідність
невід'ємне дійсне число cj, що інтерпретується як
пропускна здатність (місткість) дуги уj.
Позначимо через хi→X множину дуг, що виходять з
вершини хi, через X→хi — множина дуг, що
заходять до вершини хi.

14.

➢ Течією
у мережі G з вершини хs до вершини хt
величини v називається невід'ємна, визначена на
дугах уj функція : Y→R+ {0}, така, що
v, x = xs
( y ) − ( y ) = 0, x xs , xt
y x→ X
y X → x
− v, x = x
t
(yj) cj, j = 1, …, m
➢ Вершина хs називається джерелом, вершина хt —
стоком, а решта вершин — проміжними вузлами.
➢ Число
Q( xi ) = ( y ) − ( y )
y x → X
y X → x
називається чистою течією з вершини хi відносно
. Число (у) називається течією за дугою у.

15.

Приклад мережі, що складається з п'яти вузлів і
восьми дуг, в якій розглядається течія з х1 до х5.
Кожній дузі приписані два числа: перше —
величина течії за дугою, друга — пропускна
здатність дуги.
Величина течії з х1 до х5 дорівнює 3.
Q(х1) = 5 - 2 = 3,
Q(х2) = 7 - (5 + 2) = 0,
Q(х3) = -4 - 0 + 2 + 2 = 0,
Q(х4) = -4 + 4 = 0,
Q(х5) = 4 + 0 - 7 = -3.

16. Задача про максимальну течію

Задача полягає у знаходженні такої множини течій
за дугами, щоб величина Q(хs) була максимальною.
Введемо необхідні визначення.
➢ Переріз S відокремлює хs від хt, якщо вершини хs, хt
належать різним бокам перерізу: хs Xs, хt Xt,
X=Xs Xt.
➢ Пропускною
здатністю
c(S)
перерізу
S
називається сума пропускних здатностей дуг
перерізу, що починаються з Xs і закінчуються в Xt:
c( S ) =
c
j
y j ( X s → X t )

17.

Теорема про максимальну течію і мінімальний
переріз. Для будь якої мережі максимальна
величина течії з хs до хt дорівнює мінімальній
пропускній здатності перерізу, що відокремлює хs
від хt.
В розглянутому вище прикладі течія не є
максимальною. Мінімальну пропускну здатність
має переріз, що складається з дуг у1, у2: c(Xs, Xt)=6.
При цьому Xs={хs}, Xt={х2, х3, х4, хt}, Xs→Xt={у1},
Xt→Xs ={у2}.
Алгоритм для побудови мінімального перерізу (Xs,
Xt), що відокремлює хs від хt, і знаходження
максимальної течії від хs до хt запропоновано
Л.Фордом і Д.Фалкерсоном.

18. Алгоритм Форда — Фалкерсона визначення величини максимальної течії

Алгоритм починає роботу з відомої припустимої течії
(наприклад, з нульової). Потім обчислення
розвиваються у вигляді послідовності «розміщення
позначок» (операція А), кожна з яких або призводить
до течії з більшою величиною (операція Б), або ж
закінчується висновком, що розглянута течія
максимальна.
Будемо припускати, що пропускні здатності сj дуг
мережі цілочислові.

19.

Операція А (розміщення позначок).
Кожна вершина може знаходитися в одному з трьох
станів: вершині приписана позначка і вершина
переглянута (тобто вона має позначку і всі суміжні з
нею вершини «оброблені»), вершина позначена, але
не переглянута, вершина не позначена. Позначка
вершини хi має один з двох видів: (+хj, l) або (-хj, l).
Частина +хj позначки першого типу означає, що течія
припускає збільшення вздовж дуги (хj, хi) на
величину l. Частина -хj позначки другого типу
означає, що течія припускає зменшення вздовж дуги
(хi, хj) на величину l. Спочатку всі вершини не мають
позначок.

20.

Крок 1. Джерелу хs привласнюється позначка (+, ).
Вершина хs, позначена, але «не переглянута».
Крок 2. Візьмемо будь-яку позначену, але не
переглянуту вершину. Нехай вона має позначку (±хk,
l(хi)). «Переглянемо» її, тобто переглянемо всі
вершини, що суміжні з нею, і позначимо ті з них, які
ще непозначені. Всім непозначеним вершинам хj, в
які йдуть дуги уr з хi і для яких (уr)<сr, приписуємо
позначку (+хi, l(хj)), де l(хj)=min{l(хi),сr- (уr)}.
Всім непозначеним вершинам хj, з яких йдуть дуги уr
до хi і для яких (уr)>0, приписуємо позначку (-хi,
l(хj)), де l(хj)=min{l(хi), (уr)}.
Тепер вершина хi і позначена, і переглянута, а
вершина хj позначена, але не переглянута.

21.

Крок 3. Повторювати крок 2 доти, доки або стік —
вершина хt — буде позначена, або вершина хt буде не
позначена і ніяких інших позначок не можна буде
розмістити. В першому випадку переходимо до
операції Б, а в другому випадку алгоритм закінчує
роботу з максимальною течією . У другому випадку
множина
позначених
вершин
і
множина
непозначених вершин утворюють два боки
мінімального перерізу (Xs, Xt).

22.

Операція Б (збільшення течії).
Крок 4. Покласти х = хt і перейти до кроку 5.
Крок 5. Якщо позначка у вершині х має вигляд
(+z,l(х)), то змінити течію вздовж дуги (z,х) з (z,х) на
(z,х)+l(х).
Якщо позначка у вершині x має вигляд (-z,l(х)), то
змінити течію вздовж дуги (х,z) з (х,z) на (х,z)-l(х).
Крок 6. Якщо z=хs, то стерти всі позначки і
повернутися до кроку 1, щоб знов почати
розміщувати позначки, але використовуючи вже
поліпшену течію, що знайдена на кроці 5. Якщо z хs,
то взяти х=z і повернутися до кроку 5.

23.

Алгоритм розміщення позначок (операція А)
зображує пошук шляху від джерела хs до стоку хt
вздовж якого можна збільшити течію, не
перевершуючи пропускних здатностей на дугах і
зберігаючи течію у проміжних вершинах. Якщо стік
виявився позначеним, то такий шлях (відповідно —
аугментальний ланцюг) знайдений і вздовж нього
легко збільшити течію. Якщо ж операція А
закінчилася, а стік виявився непозначеним, то течія
була максимальною — її не можна збільшити.
Множина дуг, що ведуть з позначених вершин до
непозначених,
утворює
мінімальний
переріз,
оскільки позначені вершини саме складають
множину Xs.

24.

Приклад. Знайти максимальну течію у мережі.

25.

1. Візьмемо течію, що зображена на рисунку як
початкова припустима течія. Вона має величину 3.
2. Привласнимо джерелу, вершині х1, позначку (+, ).
Вершина х1 позначена, але не переглянута.
3. Переглянемо вершини, суміжні з вершиною х1.
Вершині х2 привласнимо позначку (+х1,1), а вершині
х3 — позначку (-х1,2) ( (х1,х2)=5<6=c1, (х3,х1)=2>0).
Вершина х1 позначена і переглянута, а вершини х2 і х3
позначені, але не переглянуті.
4. Переглянемо вершини, суміжні з вершиною х3. Із
вершин, суміжних з вершиною х3, не позначені
вершини х4 і х5. Вершині х4 привласнимо позначку (х3,2), оскільки (х4,х3)=4>0 і min(2,4)=2. Вершину х5
не позначаємо, оскільки (х5, х3) = 0.

26.

5. Переглянемо вершини, суміжні з вершиною х2.
Вершині х5 привласнимо позначку (+х2,1), оскільки
(х2,х5)=7<8=c5. Стік позначений. Переходимо до
операції Б — збільшення течії.
6. Стік має позначку (+х2,1). Тому збільшуємо течію
вздовж дуги (х2, х5) на 1.
7. Вершина х2 має позначку (+х1,1). Тому
збільшуємо течію вздовж дуги (х1,х2) на 1. Ми
одержали нову течію величини 4.
8. Стираємо всі позначки.

27.

28.

9. Привласнюємо вершині х1 позначку (+, ).
10. Переглянемо вершини, суміжні з вершиною х1.
Вершині х3 привласнимо позначку (-х1,2). Вершину х2
не позначаємо, оскільки (х1,х2)=6=c(y1).
11. Переглянемо вершини, суміжні з вершиною х3.
Вершині х4 привласнимо позначку (-х3,2), оскільки
(х4,х3)=4>0, l(х3)=2 i min(2,4)=2.
12. Переглянемо вершини, суміжні з вершиною х4.
Вершині х5 привласнимо позначку (-х4,2), оскільки
(х5,х4)=4>0, l(х4)=2 і min(2,4)=2. Стік позначений.
Переходимо до операції Б — збільшення течії.

29.

13. Стік має позначку (-х4,2). Тому зменшуємо течію
вздовж дуги (х5,х4) на 2.
14. Вершина х4 має позначку (-х3,2). Тому зменшуємо
течію вздовж дуги (х4,х3) на 2.
15. Вершина х3 має позначку (-х1,2). Тому зменшуємо
течію вздовж дуги (х3, х1) на 2. Ми одержали нову
течію величини 6. Ця течія є максимальною.
Перевіримо це.

30.

31.

16. Стираємо всі позначки.
17. Привласнимо вершині х1 позначку (+, ).
18. Вершини, суміжні вершині х1, не можна
позначити, оскільки дуга (х1,х2) насичена—
(х1,х2)= (y1)=c(y1)=6, а через дугу (х3,х1) течія не
передається. Стік залишився непозначеним. Отже,
одержана течія є максимальною. Дуги (х1,х2) і (х3,х1)
утворюють мінімальний переріз. Множина
позначених вершин утворює той його бік, який
містить джерело: Xs={х1}. Непозначені вершині
утворюють інший бік перерізу, що містить стік:
Xt={х2,х3,х4,х5}. Побудована течія має вигляд (y1)=6,
(y5)=8, (y6)=2, (y4)=2, (y3)=2, (y2)= (y7)=0.

32. Мережі з багатьма джерелами і стоками

Алгоритм Форда — Фалкерсона застосовний і для
визначення величини максимальної течії між
множиною вершин-джерел і множиною вершинстоків.
Розіб'ємо множину вершин на множину джерел
Х+={х X: Q(x)>0}, що створюють течію, множину
стоків
Х-={х X: Q(x)<0}, що споживають течію і
множину проміжних вершин Х0={х X: Q(x)=0}, що
зберігають течію : X=Х+ Х- Х0. Перетворимо течію
у течію, яка має тільки одне джерело та один стік,
збільшивши кількість вершин у мережі. Для цього
додамо дві нові вершини — «фіктивне» джерело xs і
«фіктивний» стік xt.

33.

З'єднаємо вершину xs зі всіма дійсними джерелами.
Цим дугам припишемо течію, що утворена
відповідним джерелом. А від кожного дійсного стоку
спрямуємо дугу до «фіктивного» стоку xt. Цим дугам
припишемо течію, що споживається відповідним
стоком. При цьому пропускні здатності доданих дуг
вважаємо нескінченними. В результаті одержуємо
мережу з одним джерелом і одним стоком.
Застосовуючи до неї алгоритм Форда — Фалкерсона,
знаходимо максимальну течію, яка є максимальною і
для вихідної мережі.
2

34.

Задачу знаходження максимальної течії для всіх пар
вузлів у неорієнтованій мережі можна розглядати як
узагальнення задачі з одним джерелом і одним стоком
і її можна розв'язати, застосовуючи алгоритм Форда
— Фалкерсона для кожної пари вершин. Але більш
ефективним є алгоритм, що запропонований Р.Гоморі
і Т.Ху.
Алгоритм Гоморі — Ху
1. Оберемо деякі дві вершини графа. Позначимо одну з
них через xs, а іншу через xt.
2. Застосуємо алгоритм Форда — Фалкерсона і
знайдемо максимальну течію з джерела xs у стік xt.
При цьому множина позначених вершин і множина
непозначених вершин утворюють два боки
мінімального перерізу Xs і Xt.
3. Оберемо дві вершини графа xi і xj що лежать з одного
боку від перерізу. Наприклад, нехай xi, xj Xs.

35.

4. Замінимо дуги з мінімального перерізу (Xs,Xt)
однією дугою, а вершини боку перерізу, в якому не
лежать вершини xi, xj (наприклад, Xt), — однією
вершиною. Пропускну здатність у так визначеній дузі
покладемо рівній пропускній здатності перерізу
(Xs,Xt).
5. Покладемо: xi=xs, xj=xt, і повернемося до другого
кроку.
Можна показати, що після того, як буде обрано n-1
пара вершин, ми визначимо всі n(n-1)/2 величин
максимальної течії для вихідної мережі. Основна ідея
алгоритму
полягає
в
ітеративній
побудові
максимального остовного дерева, гілки якого
відповідають перерізам, а пропускні здатності гілок
дорівнюють пропускним здатностям цих перерізів.

36.

Приклад реалізації алгоритму Гоморі — Ху. Числа,
приписані дугам, відповідають їх пропускним
здатностям. Треба для кожної пари вузлів мережі
визначити величину максимальної течії між ними.

37.

1. Оберемо вершини s=x1 і t=х2. Мінімальну
пропускну здатність відносно джерела s=x1 і стоку
t=х2 має переріз (Xs,Xt) з боками Xs={x1, x3, x4, x5, x6}
і Xt={x2}. За теоремою величина максимальної течії
між вершинами x1 і x2 дорівнює пропускній
здатності перерізу (Xs,Xt):
v12=v21=c(Xs,Xt)=2+3=5.
Об'єднаємо вершини з Xs в одну вершину і
з'єднаємо її з вершиною x2 гілкою з пропускною
здатністю 5.

38.

2. Оберемо вершини s=x1 і t=х3. Мінімальну
пропускну здатність відносно джерела s=x1 і стоку
t=х3 має переріз з боками Xs={x1} і Xt={x2, x3, x4, x5,
x6}. За теоремою величина максимальної течії між
вершинами x1 і x3 дорівнює пропускній здатності
перерізу (Xs,Xt):
v13=v31=c(Xs,Xt)=2+4+2=8.
Об'єднаємо вершини x3, x4, x5, x6 в одну вершину і
з'єднаємо її з вершиною x1 гілкою з пропускною
здатністю 8.

39.

3. Оберемо вершини s=x4 і t=х3. Мінімальну
пропускну здатність відносно джерела s=x4 і стоку
t=х3 має переріз з боками Xs={x4} і Xt={x1, x2, x3, x5,
x6}. За теоремою величина максимальної течії між
вершинами x4 і x3 дорівнює пропускній здатності
перерізу (Xs,Xt):
v43=v34=c(Xs,Xt)=2+5+4=11.
Об'єднаємо вершини x3, x5, x6 в одну вершину і
з'єднаємо її з вершиною x4 гілкою з пропускною
здатністю 11.

40.

4. Оберемо вершини s=x5 і t=х3. Мінімальну
пропускну здатність відносно джерела s=x5 і стоку
t=х3 має переріз з боками Xs={x5} і Xt={x1, x2, x3, x4,
x6}. Величина максимальної течії між вершинами x5
і x3 дорівнює пропускній здатності перерізу (Xs,Xt):
v53=v35=c(Xs,Xt)=5+4=9.
Об'єднаємо вершини x3, x6 в одну вершину і
з'єднаємо її з вершиною x5 гілкою з пропускною
здатністю 9.

41.

5. Оберемо вершини s=x6 і t=х3. Мінімальну
пропускну здатність відносно джерела s=x6 і стоку
t=х3 має переріз з боками Xs={x6} і Xt={x1, x2, x3, x4,
x5}. Величина максимальної течії між вершинами x6
і x3 дорівнює пропускній здатності перерізу (Xs,Xt):
v63=v36=c(Xs,Xt)=5+2+4=11.
З'єднаємо вершину x3 з вершиною x6 гілкою з
пропускною здатністю 11.

42.

За останнім деревом перерізів легко знайти решту
величин максимальних течій. Наприклад, v16=v61=8,
оскільки у ланцюгу дерева перерізів, що з'єднує
вершини x1 і x6, мінімальна пропускна здатність гілок
дорівнює 8. Запишемо величини максимальних течій
у вигляді матриці:
-
5
8
8
8
8
5
-
5
5
5
5
V= 8
5
- 11 9 11
8
5 11 -
9 11
8
5
-
9
8
5 11 11 9
-
9
9
Тут на перетині і-рядка і j-стовпця стоїть величина
максимальної течії між вершинами xi і xj.