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

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

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

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

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

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

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

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

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

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

Примечания

Литература

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

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

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