Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Флешка / МіП / Звіт .doc
Скачиваний:
35
Добавлен:
23.02.2016
Размер:
1.22 Mб
Скачать

Васильченко Є.В. гр. ЗПЗ-111

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ

Кафедра програмного забезпечення автоматизованих систем

ЗВІТ

про виконання лабораторних робіт

з дисципліни

«МЕРЕЖІ І ПОТОКИ»

Черкаси 2015

Лабораторна робота № 1

Тема: максимізація потоку в мережі

Мета: ознайомлення з методами максимізації потоку даних в обчислювальній мережі

ТЕОРЕТИЧНІ ВІДОМОСТІ

Потоки в мережах

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

Наведемо необхідні визначення, що формалізують відповідні предметні області.

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

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

Приклади дуг мережі: дороги, труби, телефонні та залізничні лінії і т.д.

Мережа, у якої існує рівно один витік (вершина, в яку не входить жодна дуга) і один стік (вершина, з якої не виходить жодна дуга), називається транспортною мережею.

Приклад транспортної мережі:

Потоком в транспортній мережі називається невід’ємна функція, визначена на множині дуг мережі, яка задовольняє дві умови:

1) величина потоку по кожній дузі не перевершує її пропускної здатності;

2) сума потоків, що входять в кожну вершину мережі, за винятком витоку і стоку, дорівнює сумі потоків, що виходять з вершини.

Величина потоку є сума потоків, що виходять з витоку, або сума потоків, що входять в стік мережі.

Приклад потоку в транспортній мережі:

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

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

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

Приклад. Транспортна мережа

має два розрізи: і . Пропускна здатність першого розрізу дорівнює 11 (7 +4), а другого - 9 (4 +5), тому максимальний потік в цій транспортної мережі дорівнює 9 = min (11, 9). Цей максимальний потік вказаний в круглих дужках.

Алгоритм побудови максимального потоку в транспортній мережі

Ланцюгом, що з'єднує витік A0 зі стоком An, (або просто ланцюгом) у транспортній мережі називається послідовність дуг A0A1, ..., An+1 An, в якій вершина Ai є початком i-ої дуги, а вершина Ai+1 - її кінцем (або, навпаки, Ai є кінцем i-ої дуги, а вершина Ai+1 - її початком).

Наприклад, у такій мережі із заданим в дужках потоком

ланцюгами є послідовності AB, BC, CD та AC, CB, BD, причому в першому ланцюзі напрямок дуги BC збігається з напрямком потоку, а в другому ланцюзі напрямок дуги CB протилежний напрямку потоку.

Визначення. Дуга ланцюга називається допустимою дугою, якщо:

1) напрям дуги збігається з напрямком потоку і потік по цій дузі менший її пропускної здатності;

2) напрямок дуги протилежний напрямку потоку і потік по цій дузі більше нуля.

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

Алгоритм побудови максимального потоку в мережі з заданими пропускними здатностями

1. Якщо потік в мережі не заданий, то вважати потік нульовим.

2. Поки в мережі є збільшувальні ланцюги, повторювати:

• взяти будь-який збільшувальний ланцюг,

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

• потоки по дугах, напрям яких співпадає з напрямом потоку, збільшити на ,

• потоки по дугах, напрямок яких протилежний напрямку потоку, зменшити на ;

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

Завдання

Варіант 9.

Побудувати максимальний потік для заданого транспортного ланцюга.

Дана мережа: Мережа з нульовим потоком:

Дана мережа:

Мережа з нульовим потоком:

Розв’язок.

1. Потік в мережі не заданий, вважаємо його нульовим.

2. Поки в мережі є збільшувальні ланцюги, повторюємо:

Збільшувальний ланцюг: AB, BD, DF;

напрямок дуг збігається з напрямком потоку,

 = min(9 – 0, 6 – 0, 10 – 0) = 6.

Нові потоки по дугах ланцюга:

AB: 0 +6 = 6, BD: 0 +6 = 6, DF: 0+6=6:

Збільшувальний ланцюг: AB, BE, EF;

напрямок дуг збігається з напрямком потоку,

 = min(9 – 6,3 – 0,7 – 0) =3.

Нові потоки по дугах ланцюга:

AB: 6 + 3 = 9, BE: 0 + 3 = 3,

EF: 0 + 3 = 3:

Збільшувальний ланцюг: AC, CE, ED,DF;

напрямок дуг збігається з напрямком потоку,

 = min(8 – 0,4 – 0,4-0,10 – 6) =4.

Нові потоки по дугах ланцюга:

AC:0+4=4,CE0+4=4,

ED: 0 + 4 = 4, DF=6+4=10:

Збільшувальних ланцюгів у мережі немає, тому максимальний потік побудований і він дорівнює 13 = 9 + 4 = 10 + 3.

Висновок: ознайомились з методами максимізації потоку даних в обчислювальній мережі.