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

У теорії графів кореневим графом називають граф, у якому одна вершина позначена, щоб відрізняти її від інших вершин. Цю особливу вершину називають коренем графу^:454

Число кореневих графів для 1, 2, ... вершин дорівнює 1, 2, 6, 20, 90, 544, ... (послідовність A000666 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

Кореневі графи можна комбінувати за допомогою кореневого добутку графів .

Кореневі дерева

Кореневе дерево - дерево, в якому виділено одну вершину (корінь дерева). Формально кореневе дерево визначають як скінченну множину $T$ одного або більше вузлів з такими властивостями:

1. існує один корінь дерева $T$ ;
2. інші вузли (за винятком кореня) розподілені серед $m\geq 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\}$.
  • У контексті, де передбачається, що дерево має корінь, дерево без виділеного кореня називається вільним.

Література

• C. D. Godsil, B. D. McKay. A new graph product and its spectrum // Bull. Austral. Math. Soc. — 1978. — Т. 18, вип. 1 (21 квітня). — С. 21—28. — DOI:10.1017/S0004972700007760. Архівовано з джерела 5 лютого 2012. Процитовано 25 червня 2021.
• Frank Harary. The number of linear, directed, rooted, and connected graphs // Transactions of the American Mathematical Society. — 1955. — Вип. 78 (21 квітня). — С. 445—463. — DOI:10.1090/S0002-9947-1955-0068198-2.

Посилання

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