17.4 Контрольні запитання та завдання
1. Назвіть властивості відстані між вершинами у графі з одиничними довжинами ребер.
2. Як визначити відстань між вершинами у графі з числовими характеристиками ребер?
3. Дайте визначення діаметра, діаметрально простого ланцюга, центра, дисперсії, центра дисперсії.
4. Дайте визначення найкоротшого шляху та наведіть приклали.
5. Для
графа
А1=((1,2,15),
(1,8,1), (2,3,4), (2,9,7), (3,4,7), (3,9,11), (3,10,15), (4,5,5),
(5,6,3), (5,7,13), (6,7,2), (7,8,2), (7,9,3), (7,10,17), (8,9,12)) з
числовими характеристиками ребер
визначіть найкоротший ланцюг між
вершинами 4 та 8.
17.5 Приклади аудиторних і домашніх задач
1. Використовуючи алгоритм Дейкстри знайдіть найкоротші шляхи, які ведуть з вершини 1 в усі інші вершини, на графі, зображеному на рис. 17.3.
Рисунок 17.3
2. Припустимо, що після виконання вправи 1 ви виявляєте, що при розрахунках вважали відсутньою дугу (4,3) довжини 1. Чи можна при цьому скористатися вже отриманими результатами або необхідно знов у повному обсязі провести обчислення за алгоритмом Дейкстри?
3. Використовуючи алгоритм Флойда-Уоршалла, знайдіть найкоротші шляхи між усіма вершинами графа, зображеного на рис. 17.3.
4. Використовуючи алгоритм Данцига, знайдіть найкоротші шляхи між усіма вершинами графа, зображеного на рис. 17.3. Порівняйте отримані результати з результатами виконання попередньої вправи.
5. Припустимо, що перед вами стоїть завдання знайти найкоротші марш-рути польотів між різними парами аеропортів Європи. При цьому необхідно врахувати, що через відсутність можливості одержання в'їзної візи аеропорти деяких країн можуть бути закриті для тих чи інших пасажирів. Виберіть найбільш ефективний спосіб вирішення даної задачі.
6. Нехай швидкості перекачки нафти між різними ємностями нафто-переробного заводу задаються такою таблицею:
Ємність |
А |
Б |
В |
Г |
А |
0,00 |
0,13 |
0,14 |
0,15 |
Б |
0,08 |
0,00 |
0,13 |
0,08 |
В |
0,17 |
0,12 |
0,00 |
0,18 |
Г |
0,10 |
0,06 |
0,13 |
0,00 |
Знайдіть два найкращі способи перекачування нафти з ємності А в інші ємності.
18 Практичне заняття № 16. Дерева
18.1 Мета заняття
Отримати уявлення про дерева, зокрема, бінарні дерева, і закріпити практичні навички застосування різних алгоритмів розділу теорії графів «Дерева».
18.2 Методичні рекомендації до самостійної роботи студентів
Під час підготовки до практичного заняття необхідно вивчити відповідний розділ конспекту лекцій і підручників [1, c. 269-286; 2, c. 269-286; 8, c. 219-224; 9, c. 181-196; 12, c. 309-312; 14, c. 77-100; 17, c. 64-128].
При повторенні матеріалу слід звернути увагу на такі питання:
дерево, ліс;
властивості дерев;
бінарне дерево;
остовне дерево, підрахунок кількості дерев у графі;
алгоритми кодування та декодування;
алгоритм Борувки знаходження дерева мінімальної вартості;
правила обходу бінарних дерев;
еквівалентні бінарні дерева;