В теории графов корневым графом называется граф, в котором есть одна помеченная вершина. Эту помеченную вершину называют корнем графа.
Число корневых графов для 1, 2, 3, ... вершин равно 1, 2, 6, 20, 90, 544, ... ().
Корневые графы можно комбинировать с помощью корневого произведения графов.
Корневые деревья Корневое дерево — дерево, в котором выделена одна вершина (корень дерева). Формально корневое дерево определяется как конечное множество одного или более узлов со следующими свойствами: существует один корень дерева ; остальные узлы (за исключением корня) распределены среди непересекающихся множеств , и каждое из множеств является корневым деревом; деревья называются поддеревьями данного корня .
Связанные определения Уровень узла — длина пути от корня до узла. Можно определить рекурсивно: уровень корня дерева равен 0; уровень любого другого узла на единицу больше, чем уровень корня ближайшего поддерева дерева , содержащего данный узел. Дерево с отмеченной вершиной называется корневым деревом. -й ярус дерева — множество узлов дерева, на уровне от корня дерева. частичный порядок на вершинах: , если вершины и различны и вершина лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной . корневое поддерево с корнем — подграф . В контексте, где дерево предполагается имеющим корень, дерево без выделенного корня называется свободным.
Примечания
Литература
Внешние ссылки
Категория:Теория графов Категория:Обобщения графов