Русская Википедия:Корневой граф

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

Корневые графы можно комбинировать с помощью корневого произведения графов.

Корневые деревья

Корневое дерево — дерево, в котором выделена одна вершина (корень дерева). Формально корневое дерево определяется как конечное множество <math>T</math> одного или более узлов со следующими свойствами:

1. существует один корень дерева <math>T</math>;
2. остальные узлы (за исключением корня) распределены среди <math>m\geq 0</math> непересекающихся множеств <math>T_1, ..., T_m</math>, и каждое из множеств является корневым деревом; деревья <math>T_1, ..., T_m</math> называются поддеревьями данного корня <math>T</math>.

Связанные определения

• Уровень узла — длина пути от корня до узла. Можно определить рекурсивно:

1. уровень корня дерева <math>T</math> равен 0;
2. уровень любого другого узла на единицу больше, чем уровень корня ближайшего поддерева дерева <math>T</math>, содержащего данный узел.

• Дерево с отмеченной вершиной называется корневым деревом.
  • <math>m</math>-й ярус дерева <math>T</math> — множество узлов дерева, на уровне <math>m</math> от корня дерева.
  • частичный порядок на вершинах: <math>u \prec v</math>, если вершины <math>u</math> и <math>v</math> различны и вершина <math>u</math> лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной <math>v</math>.
  • корневое поддерево с корнем <math>v</math> — подграф <math>\{v\}\cup\{w\mid v<w\}</math>.
  • В контексте, где дерево предполагается имеющим корень, дерево без выделенного корня называется свободным.

Литература

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

Внешние ссылки

• Шаблон:Mathworld