Page 52 - 4386

орієнтованому дереві є ребро (v, w), то немає ребра (w, v), інакше

шлях vwv буде циклом.

Рисунок 5.2

Дерева − це особливий і дуже важливий клас графів.

Особлива роль дерев визначається як широким їхнім

застосуванням у різних галузях науки, так і тим особливим

положенням, яке дерева займають у самій теорії графів. Останнє

випливає з граничної простоти будови дерев. Часто, при

розв’язуванні різних задач теорії графів, їхнє дослідження

починають з дерев. Зокрема, порівняно нескладною є проблема

перевірки ізоморфності дерев.

Якщо дано граф G, що містить більше однієї вершини, то

видаляючи його ребра можна одержати дерево тоді і тільки тоді,

коли він зв'язний.

Вершини дерева степеня 1 називаються кінцевими (листям),

інші вершини – внутрішніми вершинами.

Наприклад, у дерева, зображеного на рис. 5.1 а, кінцевими

вершинами є такі: v , v , v , v , v . Інші вершини є внутрішніми.
11
1
4
8
7
Лісом F називається незв'язний ациклічний граф (рис. 5.3).
Очевидно, що зв’язними компонентами лісу є дерева і тому,
кожен ліс може бути зображений у вигляді прямої суми дерев.

Орієнтований ліс визначається як звичайний ліс, що

складається не із простих, а з орієнтованих дерев.

51