Головна |
1. Зв'язковий граф G (V, E), що не має циклів, називається деревом. Наступна теорема перераховує деякі основні властивості дерев.
Теорема 1. Нехай граф G (V, E) має п вершин. Тоді наступні твердження еквіваленти.
G є деревом;
G не містить циклів і має n -1 ребер;
G зв'язний і має n - 1ребер;
G зв'язний, але видалення будь-якого ребра порушує зв'язність;
будь-які дві вершини графа G з'єднані рівно одним шляхом;
G не має циклів, але додавання будь-якого ребра породжує рівно один цикл.
При n = 1 твердження очевидне, тому вважаємо n 2. 1) => 2). За визначенням G не має циклів. Розглянемо деякий ребро = (v1, v2) І видалимо його. Отримаємо граф G '. У графі G 'немає шляху з v1 в v2 , Тому що якби такий шлях був, то в графі G був би цикл. Значить G "не зв'язний і не має циклів. Значить він складається з двох компонент, що є деревами з числом вершин n1 і n2 відповідно (n1 + n2 = N). За індуктивному припущенню G 'має n1 -1 + N2 -1 Ребер. Отже, граф G має n -1 ребер.
=> 3). Якби G був незв'язний, то кожна його компонента представляла б собою зв'язний граф без циклів. З попереднього маємо, що число ребер в кожній компоненті менше на одінo число її вершин. Значить, загальне число ребер менше числа вершин принаймні на два, що суперечить тому, що G має п - 1ребер.
=> 4). Видалення будь-якого ребра призводить до графу з n вершинами і n-2 ребрами, який не може бути зв'язковим.
=> 5). В силу зв'язності G, кожна пара вершин з'єднана шляхом. Якби ця пара була з'єднана більш, ніж одним шляхом, то вони утворювали б цикл. Але тоді видалення будь-якого ребра в циклі чи не порушує зв'язності графа.
=> 6). Якби G містив цикл, то будь-які дві вершини на циклі з'єднувалися б принаймні двома шляхами. Додамо тепер до графу G ребро = (v1, v2).
Тоді утворюється цикл, тому що вершини v1 і v2 вже з'єднані шляхом. Ясно, що цикл єдиний.
6) => 1). Якби G був незв'язний, то додавання ребер, що з'єднують вершини з різних компонент, не призводить до утворення циклу.
Слідство. Дерево з більш ніж однією вершиною має принаймні дві вершини ступеня 1.
Дійсно, нехай v1, ..., Vn - Безліч вершин, тоді маємо
В силу зв'язності d (vi) 1, звідси і випливає твердження. ¦
2. Для графа G (V, E) визначимо два корисні поняття.
верховий підграф G (V ', E') - це граф на безлічі вершин Е ' E ребрами Е ' Е, такими, що обидва кінці ребра е ' Е 'належать V.
реберний підграф G (V, E ') - це граф, який визначається підмножиною ребер Е' E безліччю вершин V V, що складається з кінцевих вершин ребер з Е '. Остовним (покриває) деревом графа G (V, E) називається його реберний підграф з безліччю вершин V, що є деревом.
Факт 2. Граф G (V, E) має кістяк тоді і тільки тоді, коли він зв'язний.
Запропонуємо процедуру побудови остовного дерева. Ясно, що якщо граф G не зв'язний, то він не може мати остовного дерева.
Нехай граф зв'язний. Якщо в графі немає ребра, видалення якого зберігає зв'язність графа, то G - дерево.
Якщо таке ребро є, видалимо його і продовжимо процедуру. Коли процедура не може бути продовжена, отриманий граф є деревом.
Розглянемо тепер відому проблему знаходження мінімального остовного дерева. Нехай G (V, E) неорієнтовані граф і нехай кожному ребру е Е поставлено у відповідність позитивне число (Е), зване його вагою. Потрібно знайти зв'язний реберний підграф G '(V', E '), такий, що V' = V, причому сума є мінімальною.
Ясно, що граф G (V, E ') повинен бути деревом. Дійсно, якщо G (V ', E') містить цикл, то тоді будь-ребро циклу можна видалити з графа і тим самим зменшити сумарна вага ребер графа G (V ', E').
найкоротші шляхи | Загальний опис
Вступ | A. Жадібний алгоритм | Б. Дерев'яний алгоритм | в. Метод гілок і меж |