Дерево (теорія графів)![]() Де́рево в теорії графів — зв'язний граф без циклів[1]. Орієнтоване (спрямоване) дерево — ациклічний орграф (орієнтований граф, що не містить циклів) — той, в якому тільки одна вершина має нульову напівстепінь входу, а всі інші вершини мають напівстепінь входу 1. Вершина з нульовим степенем входу називається коренем дерева, вершини з нульовим напівстепенем виходу (з яких не виходить жодне ребро) називаються кінцевими вершинами або листям. Формально дерево визначається як скінченна множина T одного або більше вузлів з наступними властивостями:
Характеристичні властивостіНайважливіші характеристичні властивості «дерева» висловлюються такими шістьма рівносильними одне одному висловленнями:
Тут — довільний граф, — кількість його вершин, — кількість ребер, — кількість компонент зв'язності, — цикломатичне число. Довільний граф без циклів часто називають лісом (оскільки кожна його складова — «дерево»). Ордерево, яке росте із x0, — це «дерево», в якому виділено одну вершину x0 («корінь»), а ребра орієнтовані таким чином, що всі ланцюги, які починаються в x0, є шляхами (тобто, їхні дуги орієнтовані в напряму обходу). Пов'язані визначенняСтепінь вершини — кількість інцидентних їй ребер. Кінцевий вузол (лист, термінальна вершина) — сайт зі ступенем 1 (тобто вузол, у який веде тільки одне ребро; у разі орієнтованого дерева — вузол, який веде тільки одна дуга і не виходить ні однієї дуги). Вузол розгалуження — некінцевий вузол. Рівень вузла — довжина шляху від кореня до вузла. Можна визначити рекурсивно: рівень кореня дерева дорівнює 0; рівень будь-якого іншого вузла на одиницю більше, ніж рівень кореня найближчого піддерева дерева, що містить цей сайт. Дерево із позначеною вершиною називається кореневим деревом. N-й ярус дерева — множина вузлів дерева, на n-ому рівні від кореня дерева. Частковий порядок на вершинах: якщо вершини різні і вершина лежить на елементарному ланцюзі, що з'єднує корінь з вершиною кореневе дерево з коренем — підграф . Кістякове дерево (остов) — це підграф даного графу, що містить всі його вершини і є деревом. Ребра графу, що не входять в остов, називаються хордами графу відносно остова. Незведеним називається дерево, в якому немає вершин ступеня 2. Ліс — множина дерев, або незв'язний граф без циклів.
Бінарне (двійкове) деревоТермін бінарне дерево (воно ж двійкове дерево) має кілька значень:
N-арні дереваN-арні дерева визначаються за аналогією з двійковим деревом. Для них також є орієнтовані та неорієнтовані випадки, а також відповідні абстрактні структури даних.
Властивості
Підрахунок деревКількість різних дерев, які можна побудувати на нумерованих вершинах, згідно формули Келі дорівнює . Див. також
Примітки
Джерела
|
Portal di Ensiklopedia Dunia