1. Сформулювати визначення графа.
2. Перерахувати види графів.
3. Перерахувати способи завдання неорграфа.
4. Пояснити поняття: инцидентность і суміжність.
5. Що називається компонентою зв'язності неорграфа?
6. Що таке ступінь вершини? Сформулювати теорему про суму ступенів вершин.
7. Сформулювати визначення маршруту в графі.
8. Який маршрут в неорграфе називається мінімальним?
9. Перерахувати види маршрутів.
ТЕМА: ЗАВДАННЯ НА неорієнтовані графів
1. Пошук маршруту з мінімальним числом ребер
2. Метричні характеристики неориентированного графа
3. Мінімальні маршрути в навантажених графах
4. Завдання на деревах
5. Цикловий ранг графа. Цикломатичне число
При вирішенні деяких прикладних задач нерідко виникає необхідність знайти маршрут, який з'єднує задані вершини в графі G (V, X). Причому маршрут повинен бути найкоротшим.
Маршрут в графі G (V, X) з вершини v у вершину w, де v ¹ w, називається мінімальним, якщо він має мінімальну довжину серед всіх маршрутів з v в w.
Нагадаємо, що довжина маршруту - це число ребер в ньому.
Властивість мінімального маршруту: Будь-який мінімальний маршрут є простим ланцюгом.
Розглянемо задачу пошуку мінімального маршруту. Введемо деякі позначення: нехай G (V, X) - граф, v Î V, V1 Í V; позначимо G (v) = Î X> - образ вершини v; G (V1) = - образ безлічі вершин V1; G -1 (v) =
Нехай G (V, X) - граф з n ³ 2 вершинами і v і w - задані вершини з даного графа. Причому v ¹ w. Наведемо алгоритм пошуку мінімального маршруту в графі G (алгоритм фронту хвилі).
Крок 1. Помічаємо вершину v індексом 0. потім помічаємо вершини, що належать образу вершини v. індексом 1. безліч вершин з індексом 1 позначимо FW1 (v). Вважаємо к = 1.
Крок 2. Якщо FWk (v) = Æ або виконується к = n -1, wÏ FWk (v), то вершина w не досяжна з v, і робота алгоритму на цьому закінчується. В іншому випадку переходимо до кроку 3.
Крок 3. Якщо wÏ FWk (v), то переходимо до кроку 4. в пртивном випадку існує маршрут з v в w довжини до, і цей шлях є мінімальним. Послідовність вершин vw1 w2 ... wk-1 w. де
і є шуканий мінімальний шлях з v в w.
Крок 4. Позначаємо індексом до + 1 все непомічені вершини, які належать образу безлічі вершин з індексом к. Безліч вершин з індексом до + 1 позначимо FWk + 1 (v). Надаємо до: = до + 1 і переходимо до кроку 2.
Безліч FWk (v) називають фронтом хвилі до- го рівня.
Зауваження: Вершини w1. w2, ... w k-1 можуть бути виділені неоднозначно, в разі, якщо існує кілька мінімальних маршрутів з v в w.
1. Використовуючи описаний алгоритм знайти мінімальний маршрут з v1 у v10 в графі, заданому діаграмою:
Вершині v1 присвоюємо індекс 0 і послідовно визначаємо
Значить, існує маршрут з v1 у v10 довжиною l = 3. і він є мінімальним.
Знайдемо послідовність вершин в цьому маршруті:
Отримали мінімальний маршрут: v1 v6 v7 v10. Дане завдання має кілька рішень.
2. Побудувати мінімальний маршрут з v1 у v6 в графі, заданому матрицею суміжності:
Вершині v1 присвоюємо індекс 0 і послідовно визначаємо безлічі, переглядаючи рядки:
Маршрут існує і дорівнює l = 3. Знайдемо послідовність вершин в цьому маршруті, переглядаючи стовпці:
Отримали мінімальний маршрут v1 v2 v3 v6. Завдання має єдине рішення.