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

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

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

Число корневых графов для 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\}.
    • В контексте, где дерево предполагается имеющим корень, дерево без выделенного корня называется свободным.

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

  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

Литература[править | править вики-текст]

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