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

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

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

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

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

Формально дерево визначається як скінченна множина T одного або більше вузлів з наступними властивостями:

  1. Існує один корінь дерева T.
  2. Інші вузли (за винятком кореня) розподілені серед M\geqslant0 непересічних множин T_1,...,T_m і кожна з множин є деревом; дерева T_1,...,T_m називаються піддеревами даного кореня T.

Характеристичні властивості[ред.ред. код]

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

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

Пов'язані визначення[ред.ред. код]

Ступінь вершини — кількість інцидентних їй ребер.

Кінцевий вузол (лист, термінальна вершина) — сайт зі ступенем 1 (тобто вузол, у який веде тільки одне ребро; у разі орієнтованого дерева — вузол, який веде тільки одна дуга і не виходить ні однієї дуги).

Вузол розгалуження — неконцевой вузол.

Рівень вузла — довжина шляху від кореня до вузла. Можна визначити рекурсивно:

рівень кореня дерева дорівнює 0;

рівень будь-якого іншого вузла на одиницю більше, ніж рівень кореня найближчого піддерева дерева , що містить цей сайт.

Дерево із зазначеною вершиною називається кореневим деревом.

N-й ярус дерева — множина вузлів дерева, на n-ому рівні від кореня дерева.

Частковий порядок на вершинах: якщо вершини різні і вершина лежить на елементарному ланцюзі, що з'єднує корінь з вершиною кореневе дерево з коренем — підграф .

Остовне дерево (остов) — це підграф даного графа, що містить всі його вершини і є деревом. Ребра графа, що не входять в остов, називаються хордами графа відносно остова.

Незведеним називається дерево, в якому немає вершин ступеня 2.

Ліс — множина дерев, або незв’язний граф без циклів.

Бінарне (двійкове) дерево[ред.ред. код]

Докладніше: Двійкове дерево

Термін двійкове дерево (воно ж двійкове дерево) має кілька значень:

N-арні дерева[ред.ред. код]

N-арні дерева визначаються за аналогією з двійковим деревом. Для них також є орієнтовані та неорієнтовані випадки, а також відповідні абстрактні структури даних.

  • N-арне дерево (неорієнтоване) — це дерево звичайне (неорієнтоване), в якому ступені вершин не перевищують N+1.
  • N-арне дерево (орієнтоване) — це орієнтоване дерево, в якому вихідні ступені вершин (число вихідних ребер) не перевершують N.

Властивості[ред.ред. код]

  • Дерево не має кратних ребер та петель.
  • Будь-яке дерево з n вершинами містить n-1
ребер. Більш того, скінченний зв'язний граф є деревом, тоді і тільки тоді, коли B-P=1, де B — число вершин, P— число ребер графа.
  • Граф є деревом, тоді і тільки тоді, коли будь-які дві різні його вершини можна з'єднати єдиним простим ланцюгом.
  • Будь-яке дерево однозначно визначається відстаннями (найменшою довжиною ланцюга) між його кінцевими (ступеня 1) вершинами.
  • Будь-яке дерево є двочастковим графом. Будь-яке дерево, множина вершин якого не більше ніж рахункова, є планарним графом.
  • Для будь-яких трьох вершин дерева шляхи між парами цих вершин мають одну спільну вершину.

Підрахунок дерев[ред.ред. код]

Кількість різних дерев, які можна побудувати на n нумерованих вершинах, згідно формули Келі дорівнює n^{n-2}.

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

  • Трохимчук, Роман. Теорія графів (Українська). Процитовано 27 березня 2016. </ref>

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


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