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

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

В теории графов корневым графом называется граф, в котором есть одна помеченная вершина. Эту помеченную вершину называют корнем графа[1][2]:454.

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

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

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

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

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

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

  • Уровень узла — длина пути от корня до узла. Можно определить рекурсивно:
  1. уровень корня дерева равен 0;
  2. уровень любого другого узла на единицу больше, чем уровень корня ближайшего поддерева дерева , содержащего данный узел.
  • Дерево с отмеченной вершиной называется корневым деревом.
    • ярус дерева — множество узлов дерева, на уровне от корня дерева.
    • частичный порядок на вершинах: , если вершины и различны и вершина лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной .
    • корневое поддерево с корнем — подграф .
    • В контексте, где дерево предполагается имеющим корень, дерево без выделенного корня называется свободным.

Примечания[править | править код]

  1. Daniel Zwillinger. CRC Standard Mathematical Tables and Formulae, 32nd Edition. — CRC Press, 2011. — ISBN 978-1-4398-3550-0.
  2. Frank Harary. The number of linear, directed, rooted, and connected graphs // Transactions of the American Mathematical Society. — 1955. — Вып. 78. — С. 445—463. — doi:10.1090/S0002-9947-1955-0068198-2.

Литература[править | править код]

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