Дерево - це окремий випадок графа, найбільш широко застосовуваний в програмуванні.
Існує досить багато рівносильних визначень дерев, ось лише деякі з них.
Дерево - це зв'язний граф без циклів.
Дерево - це зв'язний граф, в якому при N вершинах завжди рівно N-1 ребро.
Дерево - це граф, між будь-якими двома вершинами якого існує рівно один шлях.
Аналогічним чином визначається і орієнтоване дерево - як орграф, в якому між будь-якими двома вершинами існує не більше одного шляху.
Деревом називають кінцевий зв'язний граф з виділеної вершиною (коренем), що не має циклів.
Для кожної пари вершин дерева - вузлів - існує єдиний маршрут, тому вершини зручно класифікувати за ступенем віддаленості від кореневої вершини.
Відстань до кореневої вершини V0 називається ярусом s вершини.
Оскільки маршрут між двома вершинами єдиний, то. застосовуючи це властивість до суміжних вершин, можна зробити висновок, що будь-яка галузь є мостом.
При видаленні ребра єдиний маршрут переривається і граф розпадається на два подграфа.
Кореневе дерево - це орієнтоване дерево, в якому можна виділити вершини трьох видів: корінь, листя (інша їх назва: термінальні вершини) і інші вершини (нетермінальні); причому повинні виконуватися дві обов'язкові умови:
з листя не виходить жодна дуга; з інших вершин може виходити скільки завгодно дуг;
в корінь не входить жодна дуга; в усі інші вершини заходить рівно по одній дузі.
Традиційно в математиці і в родинних їй науках (в тому числі і в теоретичному програмуванні) дерева "ростуть" вниз головою: це робиться просто для зручності нарощування листя в разі потреби. Таким чином, на малюнках корінь дерева виявляється самої верхньої вершиною, а листя - найбільш нижніми.
Предок вершини v - це вершина, з якої виходить дуга, що заходить в вершину v. Нащадок вершини v - це вершина, в яку заходить дуга, яка виходить із вершини v. У цих термінах можна дати інші визначення поняттям корінь і лист: у кореня немає предків, у листа немає нащадків.
Бінарне дерево - це кореневе дерево, кожна вершина якого має не більше двох нащадків. У такому випадку іноді говорять про лівому нащадку і правом нащадку для поточної вершини.
Висота кореневого дерева - це максимальна кількість дуг, що відокремлюють листя від кореня. Якщо дерево не зважене, то його висота - це просто відстань від кореня до самого віддаленого листа.
Граф G (V, X) є деревом тоді і тільки тоді, коли виконується хоча б одна з умов:
1. Щоб простий зв'язний граф був деревом, необхідно і достатньо, щоб число вершин було більше числа ребер на один.
2. Щоб граф був деревом, необхідно і достатньо, щоб будь-які дві вершини його з'єднувалися єдиним маршрутом.
3. Граф буде деревом тоді і тільки тоді, коли додавання будь-якого нового ребра призводить до появи рівно одного циклу.
4. Граф G (V, X) зв'язний і не містить циклів.
5. Граф G (V, X) зв'язний. але втрачає це властивість після видалення будь-якого ребра.
Отже, дерево з n вершинами має n-1 ребро, тому воно буде мінімальним зв'язковим графом.
Висячі вершини, за винятком кореневої, називають листям.
Кістяком зв'язкового графа називається будь-який його підграф. що містить всі вершини графа і є деревом.
Подграф G 1 = (V 1, E 1) графа G = (V. E), називається остовне деревом в