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

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

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

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

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

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

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

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

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

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

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

Литература

• C. D. Godsil, B. D. McKay. A new graph product and its spectrum // Bull. Austral. Math. Soc. — 1978. — Т. 18, вып. 1. — С. 21—28. — doi:10.1017/S0004972700007760.
• Frank Harary. The number of linear, directed, rooted, and connected graphs // Transactions of the American Mathematical Society. — 1955. — Вып. 78. — С. 445—463. — doi:10.1090/S0002-9947-1955-0068198-2.

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

• Weisstein, Eric W. Rooted Graph (англ.) на сайте Wolfram MathWorld.