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

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

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

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

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

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

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

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

• 
• 

• 
• 

Джерела інформації

• Енциклопедія кібернетики, Зиков А. А., т. 1, с. 256.

Див. також

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