Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Дерево (теорія графів)



План:


Введення

Дерево - це зв'язний ациклічний граф (тобто граф, який не містить циклів, між будь-якою парою вершин якого існує рівно один шлях). [1]

Орієнтоване (спрямоване) дерево - аціклічний орграф ( орієнтований граф, який не містить циклів), в якому тільки одна вершина має нульову ступінь заходу (до неї не ведуть дуги), а всі інші вершини мають ступінь заходу 1 (у них веде рівно по одній дузі). Вершина з нульовим ступенем заходу називається коренем дерева, вершини з нульовим ступенем результату (з яких не виходить жодна дуга) називаються кінцевими вершинами або листям. [2]

Формально дерево визначається як скінченна множина T одного або більше вузлів з наступними властивостями:

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

1. Пов'язані визначення

  • Ступінь вузла - кількість вихідних дуг (або, інакше, кількість піддерев вузла).
  • Кінцевий вузол (лист) - вузол зі ступенем 1 (тобто вузол, у який веде тільки одне ребро; в разі орієнтованого дерева - вузол, у який веде лише одна дуга і не виходить жодної дуги).
  • Вузол розгалуження - некінцевим вузол.
  • Рівень вузла - довжина шляху від кореня до вузла. Можна визначити рекурсивно:
  1. рівень кореня дерева T дорівнює 0;
  2. рівень будь-якого іншого вузла на одиницю більше, ніж рівень кореня найближчого піддереві дерева T , Що містить даний вузол.
  • Дерево із зазначеною вершиною називається кореневим деревом.
    • m ярус дерева T - Безліч вузлів дерева, на рівні m від кореня дерева.
    • частковий порядок на вершинах: u \ prec v , Якщо вершини u і v різні і вершина u лежить на (едінственной!) елементарної ланцюга, що з'єднує корінь з вершиною v .
    • кореневе піддерево з коренем v - Подграф \ {V \} \ cup \ {w \ mid v <w \} .
  • Остовне дерево (остов) - це подграф даного графа, що містить всі його вершини і є деревом. Ребра графа, що не входять в остов, називаються хордами графа щодо остова.
  • Ліс - безліч (зазвичай впорядковане), не містить жодного перетинається дерева або містить кілька непересічних дерев.

2. Двійкове дерево

Просте бінарне дерево розміру 9 і висоти 3, з коренем значення 2. Це дерево не збалансовано і не відсортовано.

Термін бінарне дерево (воно ж бінарне дерево) має кілька значень:


3. N-арні дерева

N-арні дерева визначаються за аналогією з двійковим деревом. Для них також є орієнтовані і неорієнтовані випадки, а також відповідні абстрактні структури даних.

  • N-арное дерево (неорієнтоване) - це дерево (звичайне, неорієнтоване), в якому ступеня вершин не перевершують N +1.
  • N-арное дерево (орієнтоване) - це орієнтоване дерево, в якому вихідні ступеня вершин (число вихідних ребер) не перевершують N.

4. Властивості

  • Дерево не має кратних ребер і петель.
  • Будь-яке дерево з n вершинами містить n - 1 ребро. Більше того, кінцевий зв'язний граф є деревом тоді й тільки тоді, коли B - P = 1 , Де B - Число вершин, P - Число ребер графа.
  • Граф є деревом тоді й тільки тоді, коли будь-які дві різні його вершини можна з'єднати єдиним елементарним шляхом.
  • Будь-яке дерево однозначно визначається відстанями (довжиною найменшою ланцюга) між його кінцевими (ступеня 1) вершинами.
  • Будь-яке дерево є дводольним графом. Будь-яке дерево, що містить рахункове кількість вершин, є планарним графом.
  • Для будь-яких трьох вершин дерева, шляхи між парами цих вершин мають рівно одну спільну вершину.

5. Підрахунок дерев

  • Число різних дерев, які можна побудувати на n нумерованих вершинах, дорівнює n n - 2 (Теорема Келі [3]).
  • Твірна функція
T (z) = \ sum_ {n = 1} ^ \ infty T_nz ^ n
для числа T n неізоморфних кореневих дерев з n вершинами задовольняє функціональному рівнянню
T (z) = z \ exp \ sum_ {r = 1} ^ \ infty \ frac1r T (z ^ r) .
  • Твірна функція
t (z) = \ sum_ {n = 1} ^ \ infty t_nz ^ n
для числа t n неізоморфних дерев з n вершинами можна представити за допомогою перераховує ряду для кореневих дерев:
t (z) = T (z) - \ frac12 \ left (T ^ 2 (z)-T (z ^ 2) \ right).
  • При n \ to \ infty вірна наступна асимптотика
t n ~ C α n / n 5 / 2
де C і α певні константи, C = 0,534948 ... , α = 2,95576 ... .

6. Кодування дерев

Дерево можна кодувати наборами з нулів та одиниць. Розглянемо, наприклад, укладання дерева на площині. Починаючи з будь-якої вершини, будемо рухатися по ребрах дерева, згортаючи в кожній вершині на найближчий справа ребро і повертаючи назад в кінцевих вершинах дерева. Проходячи по деякому ребру, записуємо 0 при русі по ребру в перший раз і 1 при русі по ребру вдруге (в зворотному напрямку). Якщо m - Число ребер дерева, то через 2 m кроків ми повернемося в початкову вершину, пройшовши по кожному ребру двічі. Отримана при цьому послідовність з 0 і 1 (Код дерева) довжини 2 m дозволяє однозначно відновлювати не тільки саме дерево D , Але і його укладання на площині. Безпідставного дереву відповідають декілька таких кодів. Зокрема, з цього способу кодування випливає наступна груба оцінка на число дерев з n вершинами:

t_n \ le T_n <2 ^ {2n}

Примітки

  1. 13. Визначення дерева / / Лекції з теорії графів / Емелічев В. А., Мельников О. І., Сарванов В. І., Тишкевич Р. І. - М .: Наука, Физматлит, 1990. - С. 53. - 384 с. - 22000 екз . - ISBN 5-02-013992-0.
  2. Альфс Берзтісс. Глава 3. Теорія графів. 3.6. Дерева / / Структури даних = AT Berztiss. Data structures. Theory and practice - М .: Статистика, 1974. - С. 131. - 10500 екз .
  3. Дискретна математика: алгоритми. Формула Келі - rain.ifmo.ru/cat/view.php/theory/graph-general/cayley-2008 /

Література

  • Дональд Кнут. Мистецтво програмування, тому = The Art of Computer Programming, vol. 1. Fundamental Algorithms - 3-е изд. - М .: Вільямс, 2006. - Т. 1. Основні алгоритми. - 720 с. - ISBN 0-201-89683-4.
  • Оре О. Теорія графів - 2-е вид. - М .: Наука, 1980. - 336 с.
Дерево (структура даних)
Двійкове дерево пошуку Дерево (теорія графів) Деревоподібна структура
Двійкові дерева Двійкове дерево T-дерево
Самобалансірующейся двійкові дерева АА-дерево АВЛ-дерево Червоно-чорне дерево Расширяющееся дерево Дерево зі штрафами Декартово дерево Дерево Фібоначчі
B-дерева B-дерево 2-3-дерево B + дерево B *- дерево UB-дерево 2-3-4 дерево (A, b)-дерево Танцююче дерево
Префіксние дерева Суффіксное дерево Radix tree Ternary search tree
Двійкове розбиття простору k-мірне дерево VP-дерево
Недвійкова дерева Октодерево Sparse Voxel Octree Експоненціальне дерево PQ-дерево
Розбиття простору R-дерево R +-дерево R *- дерево X-дерево M-дерево Дерево Фенвік Дерево відрізків
Інші дерева Купа TTH Finger tree Metric tree Cover tree BK-tree Doubly-chained tree iDistance Link-cut tree
Алгоритми Пошук в ширину Пошук в глибину DSW-алгоритм Алгоритм сполучного дерева

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Теорія графів
Клітка (теорія графів)
Петля (теорія графів)
Кліка (теорія графів)
Шарнір (теорія графів)
Шлях (теорія графів)
PQ-дерево
B-дерево
Дерево
© Усі права захищені
написати до нас
Рейтинг@Mail.ru