Головна

дерева

  1. " Ліоте "- збулася мрія, або Коли дерева стали великими
  2.  великі дерева
  3.  У фруктовому саду стоїть храм Шиви зі статуєю благословенного вчителя Лахірі махас. В саду під манговими деревами кожен день займаються молитвами і вивченням Святих Писань.
  4.  Горює про минулої. Жовтіють на деревах листя, і зриває їх осінній вітер;
  5.  Дерева її саду
  6.  ДЕРЕВА, прославлений НЕ ЗА КРАСУ СВОЇХ КВІТІВ ...

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. Жадібний алгоритм |  Б. Дерев'яний алгоритм |  в. Метод гілок і меж |

© 2016-2022  um.co.ua - учбові матеріали та реферати