Задача визначення максимальних потоків між вузлами мережі перевезень пошти

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

Якщо таке перевищення короткострокове, зазначена ситуація призводить лише до уповільнення термінів оброблення посилок та деяких незручностей, якщо ж воно більш-менш тривале – відбувається нагромадження посилок, вони заповнюють складські, виробничі площі і допоміжні приміщення, закривають проходи, викликають так звані завали вузлів. Вузли практично перестають функціонувати.

Розбирання завалів, особливо крупних вузлів, – складний і тривалий процес. Для розбирання завалів приймаються відповідні заходи: припинення прийому посилок у відділеннях зв’язку та від підприємств і організацій; припинення обмінювань з поштовим транспортом; перевезення посилок у тимчасові складські приміщення; залучення до роботи військовослужбовців, студентів, пенсіонерів та інші.

Ефективним заходом розбирання завалів є перевезення необроблених посилок у ті вузли, де існують можливості їх оброблення. При цьому виникає задача визначення максимальних поштових потоків, які можливо спрямувати між вузлами мережі перевезень пошти.

Розглянемо граф G (X, Y), вершини якого відповідають вузлам мережі перевезень пошти, ребра – поштовим маршрутам, що з’єднують вузли мережі, а ваги ребер – їх пропускним спроможностям.

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

На рис. 2.13 наведений граф G (X, Y), в якому n = 5, m = 6. Біля ребер графа зазначені їх пропускні спроможності.

 

1 1 2

4

5 3

1 6

4 1 5

 

Рисунок 2.13. Граф мережі

У мережі поштового зв’язку, яку відбиває граф, для перевезень пошти використовуються маршрути:

М1: 1 – 2 – 3 – 4 – 5, М2: 5 – 4 – 3 – 2 – 1

пропускною спроможністю R (M1) = R (M2) = R (M1/M2) = 1;

M3: 1 – 4, M4: 4 – 1

пропускною спроможністю R (M3) = R (M4) = R (M3/M4) = 5;

М5: 2 – 3 – 5, М6: 5 – 3 – 2

пропускною спроможністю R (M5) = R (M6) = R (M5/M6) = 3;

М7: 3 – 5, М8: 5 – 3

пропускною спроможністю R (M7) = R (M8) = R (M7/M8) = 3.

Пропускні спроможності ребер визначаються як:

Р (1,2) = R (M1/M2) = 1,

Р (1,4) = R (M3/M4) = 5,

Р (2,3) = R (M1/M2) + R (M5/M6) = 4,

Р (3,4) = R (M1/M2) = 1,

Р (3,5) = R (M5/M6) + R (M7/M8) = 6,

Р (4,5) = R (M1/M2) = 1.

Пропускні спроможності ребер зручно подавати у виді матриці, наведеної у табл. 2.25.

Таблиця 2.25. Загальний вид матриці пропускних спроможностей ребер графа

Вершина
	Р (1,1)	Р (1,2)	Р (1,3)	Р (1,4)	Р (1,5)
	Р (2,1)	Р (2,2)	Р (2,3)	Р (2,4)	Р (2,5)
	Р (3,1)	Р (3,2)	Р (3,3)	Р (3,4)	Р (3,5)
	Р (4,1)	Р (4,2)	Р (4,3)	Р (4,4)	Р (4,5)
	Р (5,1)	Р (5,2)	Р (5,3)	Р (5,4)	Р (5,5)

 

Вершини, подані в лівій колонці, вважаються витоками, а вершини, подані в верхньому рядку, – стоками, наприклад, Р (2,4) – це пропускна спроможність дуги (2,4), а Р (4,2) – пропускна спроможність дуги (4,2). Пропускні спроможності ребер (2,4) і (4,2) співпадають. Відсутнім дугам або ребрам приписуються пропускні спроможності, що дорівнюють нулю.

У табл. 2.26 подана матриця пропускних спроможностей графа рис. 2.13 (пропускні спроможності елементів головної діагоналі матриці вважаються невизначеними).

 

Таблиця 2.26. Матриця пропускних спроможностей графа

Вершина
	-
		-
			-
				-
					-

 

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

Для визначення значень максимальних потоків між вузлами мережі перевезень пошти використовуються значення так званих перетинів графа.

Перетином зв’язного графа G (X, Y) називається ненадмірна множина його дуг (ребер), вилучення яких розділяє зазначений граф на два незв’язаних між собою графа G ₁ (X ₁, Y ₁) і G ₂ (X ₂, Y ₂).

Пропускна спроможність перетину дорівнює сумі пропускних спроможностей дуг (ребер), що його створюють.

Відповідно до однієї з основних теорем теорії графів величина максимального потоку між вершинами і та j графа дорівнює мінімальній величині пропускної спроможності перетину, що розділяє зазначені вершини.

З розгляду матриць табл. 2.25, 2.26 видно, що у перетин, який розділяє, наприклад, вершини 1, 3, 5 і вершини 2, 4 входять дуги (ребра), які подані елементами, розташованими на перехрестях 1, 3, 5 рядків з 2, 4 стовпчиками зазначених матриць, тобто елементи (1,2), (1,4), (3,2), (3,4), (5,2), (5,4), сума пропускних спроможностей яких дорівнює 1 + 5 + 4 + 1 + 0 + 1 = 12.

Це означає, що значення потоків між вершинами 1 і 2, 1 і 4, 3 і 2, 3 і 4, 5 і 2, 5 і 4 не перевищують 12.

Розглядаючи послідовно всі перетини, що розділяють вершини і та j, можна визначити з них те, яке має мінімальну пропускну спроможність, і, тим самим, визначити величину максимального потоку між зазначеними вершинами.

Будемо вважати, що кожний перетин заданий n -розрядним двійковим кодом, в якому вершинам-витокам відповідають одиниці, а вершинам-стокам – нулі. Наприклад, згаданий перетин, що розділяє вершини 1, 3, 5 і 2, 4 має код 10101.

Оскільки загальне число n -розрядних двійкових кодів складає 2 ⁿ, а коди 00 … 0 і 11 … 1 не є кодами перетинів, існує 2 ⁿ - 2 перетинів орієнтованого і

2 ^{n -1} - 1 перетинів неорієнтованого графа. Таким чином, послідовність кодів перетинів відповідає послідовності звичайних двійкових кодів.

Визначення величин максимальних потоків між вершинами графа полягає в наступному.

Початкові величини максимальних потоків між усіма парами вершин графа подаються у виді матриці табл. 2.25 і приймаються необмеженими.

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

Якщо обчислена величина пропускної спроможності перетину менше, ніж величина відповідного потоку, остання замінюється першою.

Після розглядання всіх перетинів графа автоматично створюється матриця величин максимальних потоків між усіма парами вершин графа, тобто, між усіма парами вузлів мережі перевезень пошти.

Алгоритм визначення величин максимальних потоків між вершинами графа G (X, Y) поданий на рис. 2.14.

Алгоритм містить 10 блоків.

У блоці 1 провадиться уведення матриці пропускних спроможностей ребер графа.

У блоці 2 усім елементам матриці максимальних потоків, крім розташованих на головній діагоналі, надаються необмежені значення, які подаються у виді надмірних чисел 999.

У блоці 3 коду перетину надається початкове значення K = 00 …0.

У блоці 4 код перетину збільшується на одиницю.

У блоці 5 виконується розрахунок пропускної спроможності перетину R (K).

У блоці 6 провадиться визначення значення чергового потоку P (i, j) між вершинами i, j, що розділяються зазначеним перетином.

У блоці 7 величина потоку P (i, j) порівнюється з величиною пропускної спроможності перетину R (K). При P (i, j) > R (K) – перехід до блоку 8, при P (i, j) £ R (K) – до блоку 9.

У блоці 8 величина P (i, j) замінюється величиною R (K).

У блоці 9 перевіряється, чи всі потоки P (i, j) між вершинами i, j, що розділяються перетином, перевірені. Якщо так – перехід до блоку 10, якщо ні – повернення до блоку 6.

У блоці 10 перевіряється значення коду перетину. Якщо він менше

11 …1 для орієнтованого графа або 10 …0 для неорієнтованого – повернення до блоку 4, в протилежному випадку робота алгоритму закінчується.

 

 

Початок

1. Уведення матриці пропускних

спроможностей дуг (ребер)

графа

2. Надання елементам матриці величин

максимальних потоків надмірних значень

P (i, j) = 999 (i, j = 1 n, i ¹ j)

3. Надання коду перетину значення

К = 00 … 0

 

4. К = К + 1

 

 

5. Розрахунок величини пропускної

спроможності перетину R (K)

6. Визначення значення чергового потоку

P (i, j) між вершинами, що розділяються

перетином

Ні

7. P (i, j) > R (K)

 

 

Так

8. P (i, j) = R (K)

 

9. Всі потоки

Ні P (i, j) між вершинами i, j, що

розділяються перетином,

перевірені

 

Так

ні 10. Коди всіх

перетинів перевірені

 

Так

Кінець

 

Рисунок 2.14. Алгоритм визначення величин максимальних потоків між вершинами графа

У табл. 2.27 … 2.34 наведена послідовність кроків формування матриці максимальних потоків для графа рис. 2.13. Кроки, що не змінюють значень потоків, випущені.

	Таблиця 2.27. Формування матриці максимальних потоків		Таблиця 2.28. Формування матриці максимальних потоків

 

 

Крок 0: початковий		Крок 1: R (00001) = R (11110) = 7
Вершина						Вершина
	-						-
		-						-
			-						-
				-						-
					-						-

Таблиця 2.30. Формування матриці максимальних потоків

Таблиця 2.29. Формування матриці максимальних потоків

 

 

Крок 2: R (00010) = R (11101) = 7		Крок 4: R (00100) = R (11011) = 11
Вершина						Вершина
	-						-
		-						-
			-						-
				-						-
					-						-

Таблиця 2.32. Формування матриці максимальних потоків

Таблиця 2.31. Формування матриці максимальних потоків

 

 

Крок 5: R (00101) = R (11010) = 6		Крок 8: R (01000) = R (10111) = 5
Вершина						Вершина
	-						-
		-						-
			-						-
				-						-
					-						-

 

	Таблиця 2.33. Формування матриці максимальних потоків		Таблиця 2.34. Формування матриці максимальних потоків

 

 

Крок 13: R (01101) = R (10010) = 3		Крок 15: R (01111) = R (10000) = 6
Вершина						Вершина
	-						-
		-						-
			-						-
				-						-
					-						-

 

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

Так, згідно з табл. 2.34, максимальний потік між вузлами 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.