А Б В Г

Два вузли зв’язані дугою, яка вказує на бінарний зв’язок. Множина дуг утворює дерево, вузли якого відповідно пов’язані бінарним зв’язком. Якщо у графі є дуга, то кажуть, що вузли u і v зв’язані зв’язком R, який записують uRv. Скінченний орієнтований граф називається деревом, якщо:

а) у ньому наявний єдиний вузол, який не є кінцем жодної дуги, він називається коренем;

б) будь-який вузол цього графа, відмінний від кореня, є кінцем лише однієї дуги;

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

Отже, зображені графи А і Б є деревами, а В і Г – ні. У графі В є два вузли, які не є кінцями будь-якої дуги, тобто корінь не єдиний (не виконано умову а). Крім того, у ньому є вузол, до якого йдуть дві дуги (не виконано умову б). Для графа Г не виконані умови а і в. У ньому ми бачимо замкнений шлях і відсутність кореня.

Визначимо кілька понять, важливих для побудови й інтерпретації дерева залежностей.

1. Якщо з u до v йде дуга, то це означає, що u підпорядковує v. Якщо з u до v йде шлях, то v залежить від u.

2. Вузол дерева, який не є початком будь-якої дуги, називається висячим.

3. Множина всіх вузлів дерева, які підпорядковані вузлу u, називається кущем цього вузла, а кількість підпорядкованих вузлів у кущі – його шириною, або шириною розгалуження.

4. Рівнем вузла u називається кількість вузлів у шляху, який іде від кореня до вузла u. Кількість вузлів у найдовшому шляху дерева називається кількістю рівнів у дереві.

5. Дерево, на множині вузлів якого задано відношення порядку, тобто кожен вузол має свій номер (у реченні – кожна словоформа нумерується зліва направо), називається розташованим.

Зображувати розташоване дерево треба так: потрібно задати систему координат, у якій по осі абсцис – номери вузлів, а по осі ординат – номери рівнів. Кожен вузол зображений точкою у цій системі координат. Кожна дуга (u, v) – це відрізок, який з’єднує u і v.

0 1 2 3 4 5 6 7 8 9

5 U1 U2 U3 U4 U5 U6 U7 U8 U9

На зображеному розташованому дереві:

кількість вузлів – дев’ять;

кількість рівнів – п’ять;

ширина розгалуження вузла u3 – три;

ширина розгалуження вузла u6 – один;

група залежностей вузла u7 – складається з вузлів u4, u5, u6, u7, u8, u9;

до групи залежностей вузла u3 (корінь дерева) входять усі вузли дерева.

На зображеному дереві можна визначити ще три терміни: зиґзаґ – максимальна кількість змін напрямку шляху (на нашому дереві зиґзаґ дорівнює трьом, оскільки напрямок шляху – u3 u7 u4 u6 u5 змінювався тричі). Кількість вузлів, розташованих між вертикальними лініями координатної сітки, які проходять через початок і кінець дуги (u, v), називається протяжністю цієї дуги. У нашому графі максимально довгою є дуга u3 u7 з протяжністю 4.

Розташоване дерево називається проективним, якщо виконані дві умови:

а) жодні дуги не перетинаються;

б) жодна дуга, що виходить з вузла u, не перетинає вертикальних ліній координатної сітки, які проходять через верхні вузли.

Наведемо приклади непроективних дерев:

а) б)

U1 U2 U3 U4 U5 U1 U2 U3

U1 U2 U3 U4 U5 (в)

Є сім розташованих проективних дерев, утворених трьома вузлами і двома дугами, для яких О. Падучева запропонувала таку термінологію:

ліве і праве покриття

ліва і права доріжка

лівий і правий кут

<== попередня сторінка	\|	наступна сторінка ==>
Новий автоматичний у	\|	Таблична форма дерева залежностей

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.008 сек.