У теорії графів кореневим графом називають граф, у якому одна вершина позначена, щоб відрізняти її від інших вершин. Цю особливу вершину називають коренем графу
Число кореневих графів для 1, 2, ... вершин дорівнює 1, 2, 6, 20, 90, 544, ... (послідовність A000666 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).
Кореневі графи можна комбінувати за допомогою кореневого добутку графів .
Кореневі дерева
Кореневе дерево - дерево, в якому виділено одну вершину (корінь дерева). Формально кореневе дерево визначають як скінченну множину одного або більше вузлів з такими властивостями:
- існує один корінь дерева ;
- інші вузли (за винятком кореня) розподілені серед неперетинних множин , і кожна з множин є кореневим деревом; дерева називають піддеревами даного кореня .
Пов'язані визначення
- Рівень вузла - довжина шляху від кореня до вузла. Можна визначити рекурсивно:
- рівень кореня дерева дорівнює 0;
- рівень будь-якого іншого вузла на одиницю більший, ніж рівень кореня найближчого піддерева дерева , що містить цей вузол.
- Дерево із позначеною вершиною називають кореневим деревом.
- -й ярус дерева - множина вузлів дерева, на рівні від кореня дерева.
- частковий порядок на вершинах: , Якщо вершини і різні і вершина лежить на (єдиному! ) елементарному ланцюгу, що з'єднує корінь з вершиною .
- кореневе піддерево з коренем - підграф .
- У контексті, де передбачається, що дерево має корінь, дерево без виділеного кореня називається вільним.
Примітки
- Daniel Zwillinger. CRC Standard Mathematical Tables and Formulae, 32nd Edition. — CRC Press, 2011. — .
- Frank Harary. The number of linear, directed, rooted, and connected graphs // Transactions of the American Mathematical Society. — 1955. — Вип. 78 (17 червня). — С. 445—463. — DOI: .
Література
- C. D. Godsil, B. D. McKay. A new graph product and its spectrum // Bull. Austral. Math. Soc. — 1978. — Т. 18, вип. 1 (17 червня). — С. 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 (17 червня). — С. 445—463. — DOI: .
Посилання
- Weisstein, Eric W. Кореневий граф(англ.) на сайті Wolfram MathWorld.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет