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

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

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


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


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

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

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

  • \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) — цикломатичне число.

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

[ред.] Джерела інформації

[ред.] Дивіться також


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.