Перегляд вихідного коду сторінки Дерево (теорія графів)

{{Otheruses|Дерево (значення)}}
[[Файл:Arbre binaire ordonne.svg|right|thumb|Приклад дерева]]
'''Де́рево''' в [[теорія графів|теорії графів]]&nbsp;— зв'язний [[Граф (математика)|граф]] без [[цикл (теорія графів)|циклів]]<ref>{{СУМ-20|Дерево}}</ref>.

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

Формально дерево визначається як скінченна множина T одного або більше вузлів з наступними властивостями:
# Існує один корінь дерева <math>T</math>.
# Інші вузли (за винятком кореня) розподілені серед <math>M\geqslant0</math> непересічних множин <math>T_1,...,T_m</math> і кожна з множин є деревом; дерева <math>T_1,...,T_m</math> називаються піддеревами даного кореня <math>T</math>.

== Характеристичні властивості ==
Найважливіші характеристичні властивості «дерева» висловлюються такими шістьма рівносильними одне одному висловленнями:
* <math>\varkappa(L) = 1\,</math> та <math>\lambda(L) = 0\,</math> (визначення «дерева»);
* <math>\lambda(L) = 0\,</math> та <math>m(L) = n(L) - 1\,</math>;
* <math>\varkappa(L) = 1\,</math> та <math>m(L) = n(L) - 1\,</math>;
* для довільної пари вершин ''x'', ''y'' в ''L'' існує один і тільки один [[ланцюг (теорія графів)|ланцюг]], який з'єднує ''x'' та ''y'';
* <math>\varkappa(L) = 1\,</math>, але якщо із ''L'' видалити будь яке ребро, то для отриманого графу ''L''<sup>&minus;</sup> буде <math>\varkappa(L^{-}) = 2\,</math>;
* <math>\lambda(L) = 0\,</math>, але якщо до <math>L\,</math> додати будь яке ребро (не додаючи вершин), то у отриманого графу <math>L^+\,</math> буде <math>\lambda(L^+) = 1\,</math>.

Тут <math>L\,</math>&nbsp;— довільний граф, <math>n(L)\,</math>&nbsp;— кількість його вершин, <math>m(L)\,</math>&nbsp;— кількість ребер, <math>\varkappa(L)\,</math>&nbsp;— кількість компонент зв'язності, <math>\lambda(L)\,</math>&nbsp;— [[цикломатичне число]].

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

== Пов'язані визначення ==
{{main|Словник термінів теорії графів}}
'''[[Степінь вершини (теорія графів)|Степінь вершини]]'''&nbsp;— кількість інцидентних їй ребер.

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

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

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

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

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

''Дерево із позначеною вершиною називається [[Кореневий граф|кореневим]] деревом.''

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

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

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

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

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

: '''[[Лінійний ліс]]'''&nbsp;— ліс, утворений з [[Диз'юнктне об'єднання|диз'юнктного об'єднання]] [[Шлях (теорія графів)|шляхів]].

== Бінарне (двійкове) дерево ==
{{main|Двійкове дерево}}
Термін бінарне дерево (воно ж двійкове дерево) має кілька значень:
* Неорієнтоване дерево, в якому ступені вершин не перевищують 3.
* Орієнтоване дерево, в якому вихідні ступені вершин (число вихідних ребер) не перевищують 2.
* Абстрактна структура даних, яка використовується в програмуванні. На двійковому дереві засновані такі структури даних, як [[бінарне дерево пошуку]], [[двійкова купа]], [[червоно-чорне дерево]], [[АВЛ-дерево]], [[фібоначчієва купа]] та ін.

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

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

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

== Властивості ==
* Дерево не має [[Кратні ребра|кратних ребер]] та петель.
* Будь-яке дерево з <math>n</math> вершинами містить <math>n-1
</math> ребер. Більш того, скінченний зв'язний граф є деревом, тоді і тільки тоді, коли <math>B-P=1</math>, де <math>B</math>&nbsp;— число вершин, <math>P</math>— число ребер графу.
* Граф є деревом, тоді і тільки тоді, коли будь-які дві різні його вершини можна з'єднати єдиним простим ланцюгом.
* Будь-яке дерево однозначно визначається відстанями (найменшою довжиною ланцюга) між його кінцевими (ступеня 1) вершинами.
* Будь-яке дерево є двочастковим графом. Будь-яке дерево, множина вершин якого не більше ніж рахункова, є планарним графом.
* Для будь-яких трьох вершин дерева шляхи між парами цих вершин мають одну спільну вершину.

== Підрахунок дерев ==
Кількість різних дерев, які можна побудувати на <math>n</math> нумерованих вершинах, згідно [[Формула Келі (теорія графів)|формули Келі]] дорівнює <math>n^{n-2}</math>.

== Див. також ==
{{Портал|Математика}}
* [[Теорія графів]]&nbsp;— містить визначення багатьох термінів.
* [[Дерево (структура даних)]]&nbsp;— застосування дерев в програмуванні.
* [[Дерево Тремо]]
* [[Псевдоліс]]

== Примітки ==
{{reflist}}

== Джерела ==
* [[Енциклопедія кібернетики]], [[Зиков Олександр Олександрович|Зиков О. О.]], т. '''1''', с. 256.
* {{Cite web
|url=http://cyb.univ.kiev.ua/library/training-materials/discrete-mathematics/graph-theory.pdf
|title=Теорія графів
|last=Трохимчук
|first=Роман
|language=Українська
|accessdate=27 березня 2016
|archive-date=4 березня 2016
|archive-url=https://web.archive.org/web/20160304212903/http://cyb.univ.kiev.ua/library/training-materials/discrete-mathematics/graph-theory.pdf
}}
* {{Cite web
|url=http://vuz.exponenta.ru/pdf/teogr.html
|title=ТЕОРИЯ ГРАФОВ
|website=vuz.exponenta.ru
|accessdate=2016-03-27
|archive-date=12 квітня 2016
|archive-url=https://web.archive.org/web/20160412104634/http://vuz.exponenta.ru/PDF/teogr.html
}}

{{Math-stub}}

[[Категорія:Дерева (теорія графів)| ]]
[[Категорія:Двочасткові графи]]