1.8. Дерева і ліс

Нехай множина V містить р вершин, які пронумеровані порядковими числами від 1 до р, тобто V = {1, 2, ..., р}. Зв'язавши ці вершини ребрами так, щоб були відсутні цикли, отримаємо деякий граф, що покриває дану множину р вершин.

Визначення. Дерево – це зв'язний ациклічний граф.

Дерево на множині р вершин завжди містить q = р – 1 ребро, тобто мінімальну кількість ребер, необхідну для того, щоб граф був зв'язним. Дійсно, дві вершини зв'язуються одним ребром, і для зв'язку кожної подальшої вершини з попередніми потрібне ребро, отже, для зв'язку р вершин необхідно і достатньо р – 1 ребро. При р = 2 дерево одне і воно складається з однієї гілки.

При додаванні в дерево ребра утворюється цикл, а при видаленні хоч би одного ребра дерево розпадається на компоненти, кожна з яких є також деревом або ізольованою вершиною.

Визначення. Незв'язний граф, компоненти якого є деревами, називається лісом.

Ліс з k дерев, що містить р вершин, має в точності р – k ребер. Дерева вважаються істотно різними, якщо вони не ізоморфні. Зі збільшенням числа вершин кількість різних дерев різко зростає (наприклад, при р = 20 їх налічується близько мільйона). Серед різних дерев виділяються два важливі окремі випадки: послідовне дерево, що є простим ланцюгом, і зіркове дерево, в якому одна з вершин (центр) суміжна з рештою всіх вершин.

Розглядаються також дерева з орієнтованими ребрами (дугами). Орієнтоване дерево називається прадеревом з коренем v₀, якщо існує шлях між вершиною v₀ і будь-якою іншою його вершиною. Ясно, що прадерево має єдиний корінь (вершину, в яку не входить жодна дуга).

П риклад 11. Дерево Т на рис. 1.11 має 9 вершин і 8 ребер. Введення додаткового ребра (v₂, v₇) порушує ациклічність дерева і перетворює його на зв'язний граф Т₁, в якому цикл (v₂, v₇, v₈, v₅, v₃, v₂) виділений подвійною лінією. Видалення ребра (v₅, v₈) перетворює дерево Т в ліс, що складається з двох дерев, – Т₂ і Т₃.

Н а рис. 1.12 показані всі істотно різні шестивершинні дерева (Т₁ – Т₆ ), серед яких є послідовне дерево – Т₁ і зіркове дерево – Т₆.

На рис. 1.13 показане дерево з орієнтованими ребрами, яке, очевидно, є прадеревом з коренем v₀.

Д

v₀

v₀

о цих пір розглядалися дерева як мінімальні зв'язні графи на множині р вершин. Важливе значення має й інша точка зору, коли дерева або ліс є частками деякого графа, тобто утворюються з його ребер. Будь-яка зв'язна сукупність ребер, що не містить контурів, разом з інцидентними ним вершинами утворює дерево графа. Якщо таке дерево є суграфом (містить всі вершини графа), то воно називається покриваючим деревом або остовом. Оскільки петля є простим циклом, що складається з єдиного ребра, то вона не може входити до складу будь-якого дерева графа.

Р

Рисунок 1.14 – Дерево як частина графа (виділено жирними лініями): а – дерево; б – остов (покривне дерево)

ебра графа, які належать його дереву, називають гілками. Якщо дерево покриває граф, то множина ребер графа розбивається на дві підмножини: підмножина гілок і підмножина ребер доповнення ребер, названих хордами. При цьому зв'язний (р, q)-граф містить  = р – 1 гілок і  = q – р + 1 хорд. Якщо граф незв'язний, то сукупність остовів k його компонент утворює покривний ліс. У цьому випадку  = p – k і  = q – p + k.

Дерева мають важливе значення в різних прикладних задачах, коли, наприклад, мова йде про з'єднання яких-небудь об'єктів мінімальним числом каналів (ліній зв'язку, доріг, комунікацій) з певними властивостями. За допомогою дерева визначається система координат при моделюванні ланцюгів і систем різної фізичної природи. Дерева використовуються як моделі при розгляді ієрархічних систем об'єктів, структурних формул органічних сполук і тому подібне.