Кореневий граф
граф, у якому одну вершину призначено коренем
У теорії графів кореневим графом називають граф, у якому одна вершина позначена, щоб відрізняти її від інших вершин. Цю особливу вершину називають коренем графу[1][2]
Число кореневих графів для 1, 2, ... вершин дорівнює 1, 2, 6, 20, 90, 544, ... (послідовність A000666 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).
Кореневі графи можна комбінувати за допомогою кореневого добутку графів .
Кореневі дерева
ред.Кореневе дерево - дерево, в якому виділено одну вершину (корінь дерева). Формально кореневе дерево визначають як скінченну множину одного або більше вузлів з такими властивостями:
- існує один корінь дерева ;
- інші вузли (за винятком кореня) розподілені серед неперетинних множин , і кожна з множин є кореневим деревом; дерева називають піддеревами даного кореня .
Пов'язані визначення
ред.- Рівень вузла - довжина шляху від кореня до вузла. Можна визначити рекурсивно:
- рівень кореня дерева дорівнює 0;
- рівень будь-якого іншого вузла на одиницю більший, ніж рівень кореня найближчого піддерева дерева , що містить цей вузол.
- Дерево із позначеною вершиною називають кореневим деревом.
- -й ярус дерева - множина вузлів дерева, на рівні від кореня дерева.
- частковий порядок на вершинах: , Якщо вершини і різні і вершина лежить на (єдиному! ) елементарному ланцюгу, що з'єднує корінь з вершиною .
- кореневе піддерево з коренем - підграф .
- У контексті, де передбачається, що дерево має корінь, дерево без виділеного кореня називається вільним.
Примітки
ред.- ↑ Daniel Zwillinger. CRC Standard Mathematical Tables and Formulae, 32nd Edition. — CRC Press, 2011. — ISBN 978-1-4398-3550-0.
- ↑ Frank Harary. The number of linear, directed, rooted, and connected graphs // Transactions of the American Mathematical Society. — 1955. — Вип. 78 (11 листопада). — С. 445—463. — DOI: .
Література
ред.- C. D. Godsil, B. D. McKay. A new graph product and its spectrum // Bull. Austral. Math. Soc. — 1978. — Т. 18, вип. 1 (11 листопада). — С. 21—28. — DOI: . Архівовано з джерела 5 лютого 2012. Процитовано 25 червня 2021.
- Frank Harary. The number of linear, directed, rooted, and connected graphs // Transactions of the American Mathematical Society. — 1955. — Вип. 78 (11 листопада). — С. 445—463. — DOI: .
Посилання
ред.- Weisstein, Eric W. Кореневий граф(англ.) на сайті Wolfram MathWorld.