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

граф, у якому одну вершину призначено коренем

У теорії графів кореневим графом називають граф, у якому одна вершина позначена, щоб відрізняти її від інших вершин. Цю особливу вершину називають коренем графу[1][2]:454

Число кореневих графів для 1, 2, ... вершин дорівнює 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 (11 листопада). — С. 445—463. — DOI:10.1090/S0002-9947-1955-0068198-2.

Література

ред.

Посилання

ред.
  • Weisstein, Eric W. Кореневий граф(англ.) на сайті Wolfram MathWorld.