загрузка...
загрузка...
На головну

ПРАКТИЧНА РОБОТА

  1. Cedil; Паралельна робота свердловинних насосів
  2. I. Самостійна робота з інформаційними джерелами
  3. II. САМОСТІЙНА РОБОТА СТУДЕНТІВ
  4. II. САМОСТІЙНА РОБОТА СТУДЕНТІВ
  5. II. САМОСТІЙНА РОБОТА СТУДЕНТІВ
  6. III. Метод визначення платоспроможності фізичних осіб, розроблена Ощадбанком Росії.
  7. III. Робота над новою темою

Максимальний потік в мережі дорівнює мінімальній пропускній здатності розрізу:

.

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

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

Етап 1. Насичення потоку.

Крок 1. Сформувати довільний початковий потік.

Крок 2. Знайти залишилися можливі шляхи з витоку  в стік  , Що мають тільки ненасичені дуги. Якщо такий шлях знайдений, то переходимо до кроку 3. Якщо шлях не знайдений, то переходимо до кроку 4.

Крок 3. Збільшити потік по знайденому шляху таким чином, щоб, принаймні, одна з дуг стала насиченою.

Крок 4. Одержаний потік насичений.

Етап 2. Позначка вершин мережі (перерозподіл потоку).

Крок 5. Вершину  позначити .

Крок 6. Нехай  - Будь-яка з уже помічених вершин,  - Довільна Непомічені вершина, суміжна з вершиною  . вершину  помічаємо  , Якщо дані вершини з'єднані ненасиченої дугою  , І помічаємо  , Якщо сполучені не порожній дугою .

Після позначки вершин можливі два випадки: вершина  виявилася або поміченої, або непомічених.

Крок 7. Вершина  виявилася поміченою. Значить, існує послідовність помічених вершин від витоку  до стоку  . У цій послідовності кожна наступна вершина позначена буквою попередньої вершини. На дугах послідовності визначаємо новий потік. збільшуємо на  одиниць потік на дугах, що мають напрямок від к  і зменшуємо на  одиниць потік на дугах, що мають зворотний напрямок. число  одно найменшою різниці між пропускною спроможністю і потоком дуг, що входять в послідовність. Зауважимо, що потік можна збільшувати (зменшувати) на прямих (зворотних) дугах до тих пір, поки одна з дуг не стане насиченою (порожній). Далі знову переходимо до позначки вершин (крок 5). Перерозподіл потоку зберігає всі його властивості та збільшує потік на  одиниць в вершину .

Етап 3. Визначення максимального потоку.

Крок 8. Вершина  залишилася непоміченими. нехай  - Безліч всіх помічених вершин,  - Безліч всіх непомічених вершин. Тоді дуги, що зв'язують два підмножини вершин и  , Визначають розріз  . Таким чином, знайдений потік  і розріз  , Для якого виконується умова .

Приклад 5.2. На мережі з прикладу 5.1. сформувати максимальний за величиною потік, спрямований з витоку  в стік  . Виписати ребра, що утворюють на мережі розріз мінімальної пропускної здатності.

Рішення.

Етап 1.

Крок 1. Скористаємося тим, що в прикладі 5.1 вже був сформований певний потік на мережі, рис. 5.2.

Крок 2. Шлях  містить насичену дугу  . Додати потоку цим шляхом більше не можна. шляхи , и  містять насичені дуги.

але шлях  має дві дуги, які ще ненасичені.

Крок 3. Збільшимо потік по знайденому шляху на величину:  , Тобто на 1 одиницю. В результаті - дуга  стала насиченою, рис. 5.3.

Крок 4. Таким чином, отримуємо насичений потік, оскільки кожен розглянутий шлях містить хоча б одну насичену дугу.

Мал. 5.3

Етап 2.

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

Крок 5, 6. Вершину  пометим  . На кроці 6 передбачається позначка вершин, суміжних з вершиною  , З'єднаних ненасиченими дугами. Але на побудованої мережі таких вершин немає.

В результаті вершина  виявилася непоміченими, рис. 5.4.

Мал. 5.4

Етап 3.

Крок 8. Так як вершина  непомічених, то потік, сформований на мережі, вийшов максимальним.

Будуємо розріз на мережі. Розбиваємо безліч вершин на дві підмножини: и  . Так як тільки одна вершина виявилася поміченою, то безліч  складається з однієї вершини - початку  , А решта вершини утворюють безліч :

.

проводимо розріз  , Який складається з дуг и  , Мал. 6.5:

.

Мал. 5.5

Визначимо величину максимального потоку :

 (Од.),

Приклад 5.3. На заданій мережі в дужках вказані пропускні спроможності дуг, рис. 5.6. Потрібно сформувати на мережі максимальний потік, спрямований з витоку  в стік  , І виписати ребра, що утворюють на мережі розріз мінімальної пропускної здатності.

Мал. 5.6

Рішення.

Етап 1.

Сформуємо на мережі початковий потік. Розглянемо шлях  . оскільки  , Цим ??шляхом пропускаємо потік в 2 одиниці. На мережі значення потоку позначимо числами без дужок. По дорозі  пропускаємо потік в 4 одиниці, так як  . По дорозі  пропускаємо потік в 3 одиниці, так як  . Таким чином, початковий потік має вигляд:

,

,

.

Початковий потік зображений на рис. 5.7.
 
 


Мал. 5.7

Кожен з розглянутих шляхів містить насичену дугу, тому ці шляхи насичені. На мережі є ще шляхи, які містять ненасичені дуги, а саме: , и  . Для першого шляху додатково збільшимо потік на 2 одиниці, так як  . Другий і третій шляху містять одну і ту ж дугу  з мінімальною для них залишилася різницею  . Тому для збільшення потоку на 1 одиницю виберемо, наприклад, шлях .

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

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

Мал. 5.9

Згідно рис. 5.9 на мережі витік  і стік  пов'язані дугами. Значить, можна додати якусь кількість потоку по ненасиченим дуг, при цьому доведеться перерозподілити потік.

Етап 2.

На побудованій мережі позначаємо вершини. вершину  пометим  . Суміжну їй вершину  пометим  , Так як ці вершини з'єднує ненасичена дуга  . вершину  помічаємо  , Так як вершини и  з'єднує ненасичена дуга  . вершину  помічаємо  , Так як вершини и  з'єднує непорожній дуга  . вершини и  помічаємо  , Так як вони пов'язані з вершиною  ненасиченими дугами и  . вершина  суміжна вершині  , І ці вершини з'єднані ненасиченої дугою  , Тому вершину  помічаємо  . вершина  суміжна вершині  , І ці вершини з'єднані ненасиченої дугою  , Тому вершину  помічаємо .

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

.

Збільшимо на 1 одиницю потік на дугах, що мають напрямок від к : , ,  . Зменшимо на 1 одиницю потік на дугах, що мають зворотний напрямок:  . Отримаємо наступну мережу з новим сформованим потоком, який зображений на малюнку 5.10.

Мал. 5.10

Перевіримо, чи буде побудований потік максимальним. Зобразимо мережу, на якій відзначимо все вершини і ненасичені дуги, рис. 5.11.

Знову пометим вершини. вершину  пометим  . Суміжну їй вершину  пометим  , Так як ці вершини з'єднує ненасичена дуга  . Всі інші вершини, в тому числі і вершина  , Залишаються непоміченими. Значить, потік на мережі максимальний.

Етап 3.

Згідно рис. 5.11, на останній мережі витік  і стік  НЕ зв'язні дугами. Значить потік, зображений на рис. 5.10, є максимальним.

Будуємо розріз на мережі. Розбиваємо безліч вершин на дві підмножини: и  . Помічені вершини утворюють безліч  , Непомічені - безліч  . проводимо розріз  , Який складається з дуг , , , :

.

Визначимо величину максимального потоку :

 (Од.).

Відповідь: потужність максимального потоку складає 13 од., Розріз мінімальної пропускної здатності утворюють ребра .

,

ПРАКТИЧНА РОБОТА



1   2
загрузка...
© um.co.ua - учбові матеріали та реферати