Практичне заняття 1. Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда (стр. 3 )

Сформований найкоротший шлях між вершиною 4 і іншими вершинами графа подані в табл. 2.3.9 (в дужках вказані протяжності відповідних шляхів чи їх частин)

Таблица 2.9

4 (0) – 3 (2) – 1 (3)

4 (0) – 3 (2) – 1 (3) – 2 (7)

4 (0) – 3 (2)

4 (0) – 6 (4) – 8 (6) – 5 (9)

4 (0) – 6 (4)

4 (0) – 7 (3)

4 (0) – 6 (4) – 8 (6)

Практичне заняття 3

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

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

Ключові положення

Метод. Керівництво: “Застосування методів теорії графів для розв’язування типових задач поштового зв’язку” -, , Одеса 2000.

, , Беркман зв¢язок. – К.: Техніка, 2003

Кріль С. С., Ящук і та системи поштового зв’язку. – Одеса: ОНАЗ, 2008

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

1 1 2

 

4

5 3

1 6

4 1 5

Рисунок 3. 1

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

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

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

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

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

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

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

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

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

Шаг 1 R (00001)=(11110)=

Шаг 2 R (00010)=(11101)=

Шаг 3 R (00011)=(11100)=

Шаг 4 R (00100)=(11011)=

Шаг 5 R (00101)=(11010)=

Шаг 6 R (00110)=(11001)=

Шаг 7 R (00111)=(11000)=

Шаг 8 R (01000)=(10111)=

Шаг 9 R (01001)=(10110)=

Шаг 10 R (01010)=(10101)=

Шаг 11 R (01011)=(10100)=

Шаг 12 R (01100)=(10011)=

Шаг 13 R (01101)=(10010)=

Шаг 14 R (01110)=(10001)=

Шаг 15 R (01111)=(10000)=

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

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

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

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

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

Таблица 3.1 Таблица 3.2

Шаг 0: начальный		Шаг 1: R(00001) = R(11110) = 7
Вершина	1	2	3	4	5	Вершина	1	2	3	4	5
1	-	999	999	999	999	1	-	999	999	999	7
2	999	-	999	999	999	2	999	-	999	999	7
3	999	999	-	999	999	3	999	999	-	999	7
4	999	999	999	-	999	4	999	999	999	-	7
5	999	999	999	999	-	5	7	7	7	7	-

Таблица 3.3 Таблица 3.4

Шаг 2: R(00010) = R(11101) = 7		Шаг 4: R(00100) = R(11011) = 11
Вершина	1	2	3	4	5	Вершина	1	2	3	4	5
1	-	999	999	7	7	1	-	999	11	7	7
2	999	-	999	7	7	2	999	-	11	7	7
3	999	999	-	7	7	3	11	11	-	7	7
4	7	7	7	-	7	4	7	7	7	-	7
5	7	7	7	7	-	5	7	7	7	7	-

Таблица 3.5 Таблица 3.6