Дерево (теорія графів)

Приклад дерева

Де́рево в теорії графів — зв'язний граф без циклів^[1].

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

Формально дерево визначається як скінченна множина T одного або більше вузлів з наступними властивостями:

1. Існує один корінь дерева ${\displaystyle T}$.
2. Інші вузли (за винятком кореня) розподілені серед ${\displaystyle M\geqslant 0}$ непересічних множин ${\displaystyle T_{1},...,T_{m}}$ і кожна з множин є деревом; дерева ${\displaystyle T_{1},...,T_{m}}$ називаються піддеревами даного кореня ${\displaystyle T}$.

Характеристичні властивості

Найважливіші характеристичні властивості «дерева» висловлюються такими шістьма рівносильними одне одному висловленнями:

• ${\displaystyle \varkappa (L)=1\,}$ та ${\displaystyle \lambda (L)=0\,}$ (визначення «дерева»);
• ${\displaystyle \lambda (L)=0\,}$ та ${\displaystyle m(L)=n(L)-1\,}$;
• ${\displaystyle \varkappa (L)=1\,}$ та ${\displaystyle m(L)=n(L)-1\,}$;
• для довільної пари вершин x, y в L існує один і тільки один ланцюг, який з'єднує x та y;
• ${\displaystyle \varkappa (L)=1\,}$, але якщо із L видалити будь яке ребро, то для отриманого графу L⁻ буде ${\displaystyle \varkappa (L^{-})=2\,}$;
• ${\displaystyle \lambda (L)=0\,}$, але якщо до ${\displaystyle L\,}$ додати будь яке ребро (не додаючи вершин), то у отриманого графу ${\displaystyle L^{+}\,}$ буде ${\displaystyle \lambda (L^{+})=1\,}$.

Тут ${\displaystyle L\,}$ — довільний граф, ${\displaystyle n(L)\,}$ — кількість його вершин, ${\displaystyle m(L)\,}$ — кількість ребер, ${\displaystyle \varkappa (L)\,}$ — кількість компонент зв'язності, ${\displaystyle \lambda (L)\,}$ — цикломатичне число.

Довільний граф без циклів часто називають лісом (оскільки кожна його складова — «дерево»). Ордерево, яке росте із x₀, — це «дерево», в якому виділено одну вершину x₀ («корінь»), а ребра орієнтовані таким чином, що всі ланцюги, які починаються в x₀, є шляхами (тобто, їхні дуги орієнтовані в напряму обходу).

Пов'язані визначення

Степінь вершини — кількість інцидентних їй ребер.

Кінцевий вузол (лист, термінальна вершина) — сайт зі ступенем 1 (тобто вузол, у який веде тільки одне ребро; у разі орієнтованого дерева — вузол, який веде тільки одна дуга і не виходить ні однієї дуги).

Вузол розгалуження — некінцевий вузол.

Рівень вузла — довжина шляху від кореня до вузла. Можна визначити рекурсивно:

рівень кореня дерева дорівнює 0;

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

Дерево із позначеною вершиною називається кореневим деревом.

N-й ярус дерева — множина вузлів дерева, на n-ому рівні від кореня дерева.

Частковий порядок на вершинах: якщо вершини різні і вершина лежить на елементарному ланцюзі, що з'єднує корінь з вершиною кореневе дерево з коренем — підграф .

Кістякове дерево (остов) — це підграф даного графу, що містить всі його вершини і є деревом. Ребра графу, що не входять в остов, називаються хордами графу відносно остова.

Незведеним називається дерево, в якому немає вершин ступеня 2.

Ліс — множина дерев, або незв'язний граф без циклів.

Лінійний ліс — ліс, утворений з диз'юнктного об'єднання шляхів.

Бінарне (двійкове) дерево

Термін бінарне дерево (воно ж двійкове дерево) має кілька значень:

• Неорієнтоване дерево, в якому ступені вершин не перевищують 3.
• Орієнтоване дерево, в якому вихідні ступені вершин (число вихідних ребер) не перевищують 2.
• Абстрактна структура даних, яка використовується в програмуванні. На двійковому дереві засновані такі структури даних, як бінарне дерево пошуку, двійкова купа, червоно-чорне дерево, АВЛ-дерево, фібоначчієва купа та ін.

N-арні дерева

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

• N-арне дерево (неорієнтоване) — це дерево звичайне (неорієнтоване), в якому ступені вершин не перевищують N+1.

• N-арне дерево (орієнтоване) — це орієнтоване дерево, в якому вихідні ступені вершин (число вихідних ребер) не перевершують N.

Властивості

• Дерево не має кратних ребер та петель.
• Будь-яке дерево з ${\displaystyle n}$ вершинами містить ${\displaystyle n-1}$ ребер. Більш того, скінченний зв'язний граф є деревом, тоді і тільки тоді, коли ${\displaystyle B-P=1}$, де ${\displaystyle B}$ — число вершин, ${\displaystyle P}$— число ребер графу.
• Граф є деревом, тоді і тільки тоді, коли будь-які дві різні його вершини можна з'єднати єдиним простим ланцюгом.
• Будь-яке дерево однозначно визначається відстанями (найменшою довжиною ланцюга) між його кінцевими (ступеня 1) вершинами.
• Будь-яке дерево є двочастковим графом. Будь-яке дерево, множина вершин якого не більше ніж рахункова, є планарним графом.
• Для будь-яких трьох вершин дерева шляхи між парами цих вершин мають одну спільну вершину.

Підрахунок дерев

Кількість різних дерев, які можна побудувати на ${\displaystyle n}$ нумерованих вершинах, згідно формули Келі дорівнює ${\displaystyle n^{n-2}}$.

Див. також

• Теорія графів — містить визначення багатьох термінів.
• Дерево (структура даних) — застосування дерев в програмуванні.
• Дерево Тремо
• Псевдоліс

Примітки

1. Дерево // Словник української мови : у 20 т. / НАН України, Український мовно-інформаційний фонд. — К. : Наукова думка, 2010—2022.

Джерела

• Енциклопедія кібернетики, Зиков О. О., т. 1, с. 256.
• Трохимчук, Роман. Теорія графів (PDF) (Українська) . Архів оригіналу (PDF) за 4 березня 2016. Процитовано 27 березня 2016.
• ТЕОРИЯ ГРАФОВ. vuz.exponenta.ru. Архів оригіналу за 12 квітня 2016. Процитовано 27 березня 2016.