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

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

Перейти до: навігація, пошук
Цей термін має також інші значення. Див. Дерево (значення).

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

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

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

  • \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, є шляхами (тобто, їхні дуги орієнтовані в напряму обходу).

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

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

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

 У Вікіпедії є портал


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.
Отримано з http://uk.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_(%D1%82%D0%B5%D0%BE%D1%80%D1%96%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D1%96%D0%B2)
Особисті інструменти