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

Матеріал з Вікіпедії — вільної енциклопедії.

Видається за доцільне, щоб цю статтю було об'єднано з Дерево (структура даних),
але, можливо, варто це додатково обговорити

Цей термін має також інші значення. Див. Дерево (значення)

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

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

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

$\varkappa(L) = 1$ та $λ(L) = 0$ (визначення «дерева»);
$λ(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$ ;
λ(L) = 0, но якщо до L додати будь яке ребро (не додаючи вершин), то у отриманого графу L⁺ буде λ(L⁺) = 1.

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

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