Кореневий граф

У теорії графів кореневим графом називають граф, у якому одна вершина позначена, щоб відрізняти її від інших вершин. Цю особливу вершину називають коренем графуШаблон:Rp

Число кореневих графів для 1, 2, ... вершин дорівнює 1, 2, 6, 20, 90, 544, ... (Шаблон:OEIS).

Кореневі графи можна комбінувати за допомогою кореневого добутку графів .

Кореневі дерева

Кореневе дерево - дерево, в якому виділено одну вершину (корінь дерева). Формально кореневе дерево визначають як скінченну множину $T$ одного або більше вузлів з такими властивостями:

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

Пов'язані визначення

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

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

• Дерево із позначеною вершиною називають кореневим деревом.
  • $m$-й ярус дерева $T$ - множина вузлів дерева, на рівні $m$ від кореня дерева.
  • частковий порядок на вершинах: $u\prec v$, Якщо вершини $u$ і $v$ різні і вершина $u$ лежить на (єдиному! ) елементарному ланцюгу, що з'єднує корінь з вершиною $v$.
  • кореневе піддерево з коренем $v$ - підграф $\{v\}\cup \{w\mid v<w\}$.
  • У контексті, де передбачається, що дерево має корінь, дерево без виділеного кореня називається вільним.

Література

• Шаблон:Стаття
• Шаблон:Стаття

Посилання

• Шаблон:Mathworld