Де́рево в теорії графів — зв'язний граф без циклів.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOWtMMlF3TDBGeVluSmxYMkpwYm1GcGNtVmZiM0prYjI1dVpTNXpkbWN2TWpJd2NIZ3RRWEppY21WZlltbHVZV2x5WlY5dmNtUnZibTVsTG5OMlp5NXdibWM9LnBuZw==.png)
Орієнтоване (спрямоване) дерево — ациклічний орграф (орієнтований граф, що не містить циклів) — той, в якому тільки одна вершина має нульову напівстепінь входу, а всі інші вершини мають напівстепінь входу 1. Вершина з нульовим степенем входу називається коренем дерева, вершини з нульовим напівстепенем виходу (з яких не виходить жодне ребро) називаються кінцевими вершинами або листям.
Формально дерево визначається як скінченна множина T одного або більше вузлів з наступними властивостями:
- Існує один корінь дерева .
- Інші вузли (за винятком кореня) розподілені серед непересічних множин і кожна з множин є деревом; дерева називаються піддеревами даного кореня .
Характеристичні властивості
Найважливіші характеристичні властивості «дерева» висловлюються такими шістьма рівносильними одне одному висловленнями:
та
(визначення «дерева»);
та
;
та
;
- для довільної пари вершин x, y в L існує один і тільки один ланцюг, який з'єднує x та y;
, але якщо із L видалити будь яке ребро, то для отриманого графу L− буде
;
, але якщо до
додати будь яке ребро (не додаючи вершин), то у отриманого графу
буде
.
Тут — довільний граф,
— кількість його вершин,
— кількість ребер,
— кількість компонент зв'язності,
— цикломатичне число.
Довільний граф без циклів часто називають лісом (оскільки кожна його складова — «дерево»). Ордерево, яке росте із x0, — це «дерево», в якому виділено одну вершину x0 («корінь»), а ребра орієнтовані таким чином, що всі ланцюги, які починаються в x0, є шляхами (тобто, їхні дуги орієнтовані в напряму обходу).
Пов'язані визначення
Степінь вершини — кількість інцидентних їй ребер.
Кінцевий вузол (лист, термінальна вершина) — сайт зі ступенем 1 (тобто вузол, у який веде тільки одне ребро; у разі орієнтованого дерева — вузол, який веде тільки одна дуга і не виходить ні однієї дуги).
Вузол розгалуження — некінцевий вузол.
Рівень вузла — довжина шляху від кореня до вузла. Можна визначити рекурсивно:
рівень кореня дерева дорівнює 0;
рівень будь-якого іншого вузла на одиницю більше, ніж рівень кореня найближчого піддерева дерева, що містить цей сайт.
Дерево із позначеною вершиною називається кореневим деревом.
N-й ярус дерева — множина вузлів дерева, на n-ому рівні від кореня дерева.
Частковий порядок на вершинах: якщо вершини різні і вершина лежить на елементарному ланцюзі, що з'єднує корінь з вершиною кореневе дерево з коренем — підграф .
Кістякове дерево (остов) — це підграф даного графу, що містить всі його вершини і є деревом. Ребра графу, що не входять в остов, називаються хордами графу відносно остова.
Незведеним називається дерево, в якому немає вершин ступеня 2.
Ліс — множина дерев, або незв'язний граф без циклів.
- Лінійний ліс — ліс, утворений з диз'юнктного об'єднання шляхів.
Бінарне (двійкове) дерево
Термін бінарне дерево (воно ж двійкове дерево) має кілька значень:
- Неорієнтоване дерево, в якому ступені вершин не перевищують 3.
- Орієнтоване дерево, в якому вихідні ступені вершин (число вихідних ребер) не перевищують 2.
- Абстрактна структура даних, яка використовується в програмуванні. На двійковому дереві засновані такі структури даних, як бінарне дерево пошуку, (двійкова купа), червоно-чорне дерево, АВЛ-дерево, (фібоначчієва купа) та ін.
N-арні дерева
N-арні дерева визначаються за аналогією з двійковим деревом. Для них також є орієнтовані та неорієнтовані випадки, а також відповідні абстрактні структури даних.
- N-арне дерево (неорієнтоване) — це дерево звичайне (неорієнтоване), в якому ступені вершин не перевищують N+1.
- N-арне дерево (орієнтоване) — це орієнтоване дерево, в якому вихідні ступені вершин (число вихідних ребер) не перевершують N.
Властивості
- Дерево не має кратних ребер та петель.
- Будь-яке дерево з
вершинами містить
ребер. Більш того, скінченний зв'язний граф є деревом, тоді і тільки тоді, коли
, де
— число вершин,
— число ребер графу.
- Граф є деревом, тоді і тільки тоді, коли будь-які дві різні його вершини можна з'єднати єдиним простим ланцюгом.
- Будь-яке дерево однозначно визначається відстанями (найменшою довжиною ланцюга) між його кінцевими (ступеня 1) вершинами.
- Будь-яке дерево є двочастковим графом. Будь-яке дерево, множина вершин якого не більше ніж рахункова, є планарним графом.
- Для будь-яких трьох вершин дерева шляхи між парами цих вершин мають одну спільну вершину.
Підрахунок дерев
Кількість різних дерев, які можна побудувати на нумерованих вершинах, згідно (формули Келі) дорівнює
.
Див. також
- Теорія графів — містить визначення багатьох термінів.
- Дерево (структура даних) — застосування дерев в програмуванні.
- Дерево Тремо
- Псевдоліс
Примітки
- Дерево // Словник української мови : у 20 т. — К. : Наукова думка, 2010—2022.
Джерела
- Енциклопедія кібернетики, (Зиков О. О.), т. 1, с. 256.
- Трохимчук, Роман. (PDF) (Українська) . Архів оригіналу (PDF) за 4 березня 2016. Процитовано 27 березня 2016.
- . vuz.exponenta.ru. Архів оригіналу за 12 квітня 2016. Процитовано 27 березня 2016.
![]() | Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет