1. Що таке дерево і ліс?

дерево

• У теорії графів а дерево є неорієнтований, зв'язний і ациклічний граф . Іншими словами, зв'язний граф, який не містить жодного циклу, називається деревом.
• Дерево представляє ієрархічну структуру в графічній формі.
• Елементи дерев називають їх вузлами, а ребра дерева — гілками.
• Дерево з n вершинами має (n-1) ребер.
• Дерева пропонують багато корисних програм, як простих, як генеалогічне дерево, так і складних, як дерева в структурах даних інформатики.
• А листок у дереві є вершина ступеня 1 або будь-яка вершина, що не має дітей, називається листом.

приклад

У наведеному вище прикладі всі дерева мають менше ніж 6 вершин.

Ліс

У теорії графів а ліс є неорієнтований, роз’єднаний, ациклічний граф . Іншими словами, непересічна сукупність дерев називається лісом. Кожен компонент лісу є деревом.

приклад

Наведений вище графік виглядає як два підграфи, але це один відключений граф. На наведеному вище графіку немає циклів. Тому це ліс.

2. Властивості дерев

1. Кожне дерево, яке має хоча б дві вершини, повинно мати хоча б два листки.
2. Дерева мають багато властивостей:
   Нехай T — граф із n вершинами, тоді наступні твердження еквівалентні:
   • Т — дерево.
   • T не містить циклів і має n-1 ребер.
   • T зв'язний і має (n -1) ребро.
   • T зв'язний граф, і кожне ребро є зрізом.
   • Будь-які дві вершини графа T з'єднані рівно одним шляхом.
   • T не містить циклів, і для будь-якого нового ребра e граф T+ e має рівно один цикл.
3. Кожен край дерева обрізаний.
4. Додавання одного ребра до дерева визначає рівно один цикл.
5. Кожен зв'язний граф містить остовне дерево.
6. Кожне дерево має принаймні дві вершини другого ступеня.

3. Остовне дерево

А остовне дерево у зв’язному графі G є підграфом H графа G, який включає всі вершини G і також є деревом.

приклад

Розглянемо наступний графік G:

З наведеного вище графа G ми можемо реалізувати наступні три остовні дерева H:

Методи пошуку остовного дерева

Ми можемо знайти остовне дерево систематично, використовуючи один із двох методів:

1. Метод вирубки
2. Метод нарощування

1. Метод вирубки

• Почніть вибирати будь-який цикл на графіку G.
• Видалити одне з ребер циклу.
• Повторюйте цей процес, доки циклів не залишиться.

приклад

• Розглянемо граф G,

• Якщо ми видалимо ребро ac, яке руйнує цикл a-d-c-a у наведеному вище графіку, то отримаємо такий графік:

• Видаляємо ребро cb, яке руйнує цикл a-d-c-b-a з наведеного вище графіка, тоді ми отримуємо наступний графік:

• Якщо ми видалимо ребро ec, яке руйнує цикл d-e-c-d із наведеного вище графіка, то отримаємо наступне остовне дерево:

2. Метод нарощування

• Виділіть ребра графа G по одному. Таким чином, щоб не було створених циклів.
• Повторюйте цей процес, доки всі вершини не будуть включені.

приклад

Розглянемо наступний графік G,

• Виберіть край аб ,

• Виберіть край з ,

• Після цього виберіть край ек ,

• Далі виберіть край cb , то нарешті ми отримаємо наступне остовне дерево:

Ранг ланцюга

Кількість ребер, які нам потрібно видалити з G, щоб отримати остовне дерево.

Остовне дерево G = m- (n-1) , який називається ранг ланцюга Г.

 Where, m = No. of edges. n = No. of vertices. 

приклад

У наведеному вище графіку ребер m = 7 і вершин n = 5

Тоді ранг схеми:

 G = m - (n - 1) = 7 - (5 - 1) = 3