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

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

Число кореневих графів для 1, 2, ... вершин дорівнює 1, 2, 6, 20, 90, 544, ... (послідовність A000666 з Онлайн енциклопедії послідовностей цілих чисел, 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\}}$.
  • У контексті, де передбачається, що дерево має корінь, дерево без виділеного кореня називається вільним.

Примітки

1. Daniel Zwillinger. CRC Standard Mathematical Tables and Formulae, 32nd Edition. — CRC Press, 2011. — .
2. Frank Harary. The number of linear, directed, rooted, and connected graphs // Transactions of the American Mathematical Society. — 1955. — Вип. 78 (17 червня). — С. 445—463. — DOI:10.1090/S0002-9947-1955-0068198-2.

Література

• C. D. Godsil, B. D. McKay. A new graph product and its spectrum // Bull. Austral. Math. Soc. — 1978. — Т. 18, вип. 1 (17 червня). — С. 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 (17 червня). — С. 445—463. — DOI:10.1090/S0002-9947-1955-0068198-2.

Посилання

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