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

Кореневе дерево - дерево, в якому виділено одну вершину (корінь дерева). Формально кореневе дерево визначають як скінченну множину ${\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 (28 січня). — С. 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 (28 січня). — С. 445—463. — DOI:10.1090/S0002-9947-1955-0068198-2.

• Weisstein, Eric W. Кореневий граф(англ.) на сайті Wolfram MathWorld.