18.4 Контрольні запитання

1. Який граф називають деревом?

2. Який граф називають лісом?

3. Які властивості має дерево?

4. Які дерева називають бінарними?

5. Що таке n-арне дерево?

6. Чому дорівнює порядок бінарного дерева?

7. Що таке обхід дерева? Які обходи бувають?

18.5 Приклади аудиторних і домашніх задач

1. Побудуйте n-арне дерево, якщо n дорівнює:

а) 1;

б) 4.

2. Яка глибина, висота, а також який порядок дерева Т, зображеного на рис. 18.13? Чи є це дерево повним?

Рисунок 18.13

3. Перелічіть нащадків вершин V₁ та V₆ дерева Т, яке зображено на рис. 18.13.

4. Обійдіть у префіксному, інфіксному та постфіксному порядку дерева, зображені на рис. 18.13 – 18.15. Визначіть порядок відвідування всіх вершин.

5. Напишіть код заданих дерев (рис. 18.14 і 18.15):

6. Побудуйте дерево за заданим кодом:

a) 1 2 2 2 1 1;

б) 2 3 1 2 3 4 5;

в) 2 4 3 2 3 3 2;

г) 1 2 3 2 1 2.

Рисунок 18.14

Рисунок 18.15

7. Задано такі символи та їх коди:

символ	код
c	111
d	101
e	01
i	11001
s	0010
u	1101

а) закодуйте слово discuss;

б) закодуйте слово suede;

в) декодуйте слово 101011111100110101101;

г) декодуйте слово 11001001000101101010010.

19 Практичне заняття № 17. Транспортні мережі

19.1 Мета заняття

Вивчити основні поняття теорії транспортних мереж, одержати практичні навички з реалізації алгоритму Форда-Фалкерсона для знаходження максимальної течії (потоку) і мінімального розрізу в транспортній мережі.

19.2 Методичні рекомендації до самостійної роботи студентів

Під час підготовки до практичного заняття необхідно вивчити розділ "Алгоритм Форда-Фалкерсона" конспекту лекцій та підручників [1, c. 322-338; 2, c. 322-338; 9, c. 231-261; 17, c. 64-128].

При вивченні і повторенні матеріалу слід звернути увагу на такі питання:

• транспортна мережа;

• насичена і ненасичена дуги, пропускна здатність;

• розріз мережі;

• потік у мережі та у дузі; задача про знаходження повного потоку;

• задача про максимальний потік і мінімальний розріз мережі.

19.3 Приклади розв’язання типових завдань

1. Знайдіть максимальний потік для мережі, зображеної на рис. 19.1.

Величина начального потоку у мережі .

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

Для кожної дуги u_i зворотного шляху додаємо до знаменника мінімальну отриману різницю . Після цієї дії хоча б одна дуга шляху стає насиченою. Після цього вибираємо наступний шлях. Повторюємо ці дії доти, доки не отримаємо повний потік у мережі. (рис. 19.2). Величина, що збільшує потік , дорівнює 4. Отже, . Дуга стала насиченою (рис. 19.3). .

Величина, що збільшує потік , дорівнює 7. Отже, . Дуга стала насиченою (рис. 19.4). .

Величина, що збільшує потік , дорівнює 1. Отже, . Дуга стала насиченою (рис. 19.5). Всі існуючі та розглянуті шляхи від х_s до x_t містять насичені дуги. Отже, знайдено повний потік .

Рисунок 19.1		Рисунок 19.2
Рисунок 19.3	Рисунок 19.4

Перевіримо, чи є повний потік максимальним, використовуючи алгоритм розмітки вершин (рис. 19.5). Маємо шлях , яким можливе збільшення потоку: .Збільшимо потік на 3 по дугах , , , та зменшимо на 3 по дузі .

Величина, що збільшує потік , дорівнює 3. Отже, . Дуга стала насиченою. При подальшій розмітці позначки отримують тільки вершини x_s, x₁, x₂, x₃, x₄ (рис. 19.6).

Рисунок 19.5

Рисунок 19.6

Оскільки розмітка не досягає вершини x_t, то потік – максимальний. Для знаходження мінімального розрізу використовують позначки, які передаються від входу всіма можливими способами. Вершини, які при цьому не одержують позначок, утворюють множину вершин розрізу A. Позначені вершини утворюють множину .

Всі дуги, які належать множині , утворюють мінімальний розріз. У даному прикладі: , . Розріз утворює дуги ={ , }.

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