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

В теории графов корневым графом называется граф, в котором есть одна помеченная вершина. Эту помеченную вершину называют корнем графаШаблон:Rp.

Число корневых графов для 1, 2, 3, ... вершин равно 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