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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

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

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

Приклади дерев[ред.ред. код]

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

Див. також[ред.ред. код]