Дерева та ліси: основні поняття

📌 Про що ця тема

Дерева — це особливий вид графа, який описує ієрархічні звʼязки без циклів (файлова система, родовід, структура організації). На іспиті перевіряють уміння розпізнати дерево, порахувати його параметри (вершини, ребра, висоту) та відрізнити дерево від звичайного графа чи лісу. Ключове поняття — звʼязний граф без циклів.

📖 Головне

• Дерево — це звʼязний неорієнтований граф без циклів. «Звʼязний» означає, що між будь-якими двома вершинами існує шлях; «без циклів» — не можна повернутися у вершину, не проходячи ребро двічі.

• Якщо дерево має n вершин, то воно має рівно n−1 ребро. Це головна формула теми.

• Між будь-якими двома вершинами дерева існує єдиний шлях. Якби шляхів було два — зʼявився б цикл.

• Ліс — це граф, усі компоненти звʼязності якого є деревами (тобто кілька окремих дерев разом). Дерево — окремий випадок лісу з одного компонента.

• Якщо ліс має n вершин і k дерев (компонентів), то ребер у ньому n−k.

• Корінь — виділена вершина, від якої будується ієрархія (кореневе дерево).

• Лист (листок) — вершина, що не має нащадків (у кореневому дереві). Внутрішня вершина — має хоча б одного нащадка.

• Батько і нащадок (син): вершина, яка стоїть вище за ієрархією, — батько; нижче — нащадок. Корінь не має батька.

• Степінь вершини — кількість ребер, що з неї виходять.

• Висота дерева — довжина найдовшого шляху від кореня до листа (кількість ребер). Глибина вершини — відстань від кореня до неї.

• Двійкове (бінарне) дерево — кожна вершина має не більше двох нащадків (лівий і правий).

• Додавання будь-якого ребра до дерева створює цикл; видалення будь-якого ребра робить граф незвʼязним (розбиває на ліс).

🔢 Як це працює на прикладі

Приклад 1. Граф має 7 вершин і 6 ребер, звʼязний. Чи це дерево? Перевіряємо: ребер = n−1 = 7−1 = 6. Так, умова виконується, і граф звʼязний без циклів — отже, це дерево.

Приклад 2. Ліс складається з 3 дерев і має загалом 10 вершин. Скільки ребер? Формула: n−k = 10−3 = 7 ребер.

⚠️ Типові помилки

• Плутають дерево і ліс: дерево завжди звʼязне (один компонент), ліс може мати кілька окремих дерев.

• Рахують ребра як n, а не n−1 — забувають, що цикл у дереві заборонений.

• Вважають, що будь-який граф без циклів — дерево. Ні: без циклів, але незвʼязний — це ліс, а не дерево.

• Плутають висоту (у ребрах) і кількість рівнів (у вершинах): висота на 1 менша за число рівнів.

• Думають, що в бінарному дереві кожна вершина має рівно 2 нащадки — насправді не більше двох (0, 1 або 2).

🎯 Що завчити напамʼять

• Дерево з n вершинами має n−1 ребро.

• Ліс з n вершин і k дерев має n−k ребер.

• Дерево = звʼязний граф без циклів.

• Ліс = граф без циклів (кілька дерев).

• Між двома вершинами дерева — єдиний шлях.

🧠 Перевір себе

1. Скільки ребер у дереві з 15 вершинами?

2. Граф без циклів із 3 компонентів, 12 вершин. Скільки ребер?

3. Чим дерево відрізняється від лісу?

4. Що станеться, якщо додати ребро до дерева?

Відповіді: 1 — 14 (n−1); 2 — 9 (n−k = 12−3); 3 — дерево звʼязне (один компонент), ліс може складатися з кількох дерев; 4 — утвориться цикл.