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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории графов корневым графом называется граф, в котором одна вершина помечена, чтобы отличать её от других вершин. Эту специальную вершину называют корнем графа.

Число корневых графов для 1, 2, ... вершин равно 1, 2, 6, 20, 90, 544, ... (последовательность A000666 в OEIS)

Корневые графы можно комбинировать с помощью корневого произведения графов[en].

Корневые деревья[править | править вики-текст]

Корневое дерево — дерево, в котором выделена одна вершина (корень дерева). Формально корневое дерево определяется как конечное множество T одного или более узлов со следующими свойствами:

  1. существует один корень дерева T
  2. остальные узлы (за исключением корня) распределены среди m\geq 0 непересекающихся множеств T_1, ..., T_m, и каждое из множеств является корневым деревом; деревья T_1, ..., T_m называются поддеревьями данного корня T

Связанные определения[править | править вики-текст]

  • Уровень узла — длина пути от корня до узла. Можно определить рекурсивно:
  1. уровень корня дерева T равен 0;
  2. уровень любого другого узла на единицу больше, чем уровень корня ближайшего поддерева дерева T, содержащего данный узел.
  • Дерево с отмеченной вершиной называется корневым деревом.
    • mярус дерева T — множество узлов дерева, на уровне m от корня дерева.
    • частичный порядок на вершинах: u \prec v, если вершины u и v различны и вершина u лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной v.
    • корневое поддерево с корнем v — подграф \{v\}\cup\{w\mid v<w\}.
    • В контексте, где дерево предполагается имеющим корень, дерево без выделенного корня называется свободным.

Ссылки[править | править вики-текст]

Внешние ссылки[править | править вики-текст]