![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/d/d0/Arbre_binaire_ordonne.svg/languk-640px-Arbre_binaire_ordonne.svg.png&w=640&q=50)
Дерево (теорія графів)
З Вікіпедії, безкоштовно encyclopedia
Де́рево в теорії графів — зв'язний граф без циклів[1].
У Вікіпедії є статті про інші значення цього терміна: Дерево (значення).
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d0/Arbre_binaire_ordonne.svg/320px-Arbre_binaire_ordonne.svg.png)
Орієнтоване (спрямоване) дерево — ациклічний орграф (орієнтований граф, що не містить циклів) — той, в якому тільки одна вершина має нульову напівстепінь входу, а всі інші вершини мають напівстепінь входу 1. Вершина з нульовим степенем входу називається коренем дерева, вершини з нульовим напівстепенем виходу (з яких не виходить жодне ребро) називаються кінцевими вершинами або листям.
Формально дерево визначається як скінченна множина T одного або більше вузлів з наступними властивостями:
- Існує один корінь дерева
.
- Інші вузли (за винятком кореня) розподілені серед
непересічних множин
і кожна з множин є деревом; дерева
називаються піддеревами даного кореня
.