У теорії графів кореневим графом називають граф, у якому одна вершина позначена, щоб відрізняти її від інших вершин. Цю особливу вершину називають коренем графу
Число кореневих графів для 1, 2, ... вершин дорівнює 1, 2, 6, 20, 90, 544, ... ().
Кореневі графи можна комбінувати за допомогою кореневого добутку графів .
Кореневі дерева Кореневе дерево - дерево, в якому виділено одну вершину (корінь дерева). Формально кореневе дерево визначають як скінченну множину одного або більше вузлів з такими властивостями:
існує один корінь дерева ; інші вузли (за винятком кореня) розподілені серед неперетинних множин , і кожна з множин є кореневим деревом; дерева називають піддеревами даного кореня .
Пов'язані визначення
Рівень вузла - довжина шляху від кореня до вузла. Можна визначити рекурсивно:
рівень кореня дерева дорівнює 0; рівень будь-якого іншого вузла на одиницю більший, ніж рівень кореня найближчого піддерева дерева , що містить цей вузол.
Дерево із позначеною вершиною називають кореневим деревом. -й ярус дерева - множина вузлів дерева, на рівні від кореня дерева. частковий порядок на вершинах: , Якщо вершини і різні і вершина лежить на (єдиному! ) елементарному ланцюгу, що з'єднує корінь з вершиною . кореневе піддерево з коренем - підграф . У контексті, де передбачається, що дерево має корінь, дерево без виділеного кореня називається вільним.
Примітки
Література
Посилання