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

Дерево — это связный ациклический граф. Связность означает наличие путей между любой парой вершин, ацикличность — отсутствие циклов и то, что между парами вершин имеется только по одному пути.

Лес — упорядоченное множество упорядоченных деревьев.

Ориентированное (направленное) дерево — ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями.

Связанные определения

• Степень вершины — количество инцидентных ей ребер.
• Концевой узел (лист, терминальная вершина) — узел со степенью 1 (то есть узел, в который ведёт только одно ребро; в случае ориентированного дерева — узел, в который ведёт только одна дуга и не исходит ни одной дуги).
• Узел ветвления — неконцевой узел.
• Уровень узла — длина пути от корня до узла. Можно определить рекурсивно:

1. уровень корня дерева <math>T</math> равен 0;
2. уровень любого другого узла на единицу больше, чем уровень корня ближайшего поддерева дерева <math>T</math>, содержащего данный узел.

• Дерево с отмеченной вершиной называется корневым деревом.
  • <math>m</math>-й ярус дерева <math>T</math> — множество узлов дерева, на уровне <math>m</math> от корня дерева.
  • частичный порядок на вершинах: <math>u \prec v</math>, если вершины <math>u</math> и <math>v</math> различны и вершина <math>u</math> лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной <math>v</math>.
  • корневое поддерево с корнем <math>v</math> — подграф <math>\{v\}\cup\{w\mid v<w\}</math>.
  • В контексте, где дерево предполагается имеющим корень, дерево без выделенного корня называется свободным.
• Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.
• Несводимым называется дерево, в котором нет вершин степени 2.
• Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.

Двоичное дерево

Термин двоичное дерево (оно же бинарное дерево) имеет несколько значений:

• Неориентированное дерево, в котором степени вершин не превосходят 3.
• Ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят 2.
• Абстрактная структура данных, используемая в программировании. На двоичном дереве основаны такие структуры данных, как двоичное дерево поиска, двоичная куча, красно-чёрное дерево, АВЛ-дерево, фибоначчиева куча и др.

N-арные деревья

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

• N-арное дерево (неориентированное) — это дерево (обычное, неориентированное), в котором степени вершин не превосходят N+1.
• N-арное дерево (ориентированное) — это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят N.

Свойства

• Дерево не имеет кратных рёбер и петель.
• Любое дерево с <math>n</math> вершинами содержит <math>n-1</math> ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда <math>B-P=1</math>, где <math>B</math> — число вершин, <math>P</math> — число рёбер графа.
• Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственной простой цепью.
• Любое дерево однозначно определяется расстояниями (длиной наименьшей цепи) между его концевыми (степени 1) вершинами.
• Любое дерево является двудольным графом. Любое дерево, множество вершин которого не более чем счётное, является планарным графом.
• Для любых трёх вершин дерева, пути между парами этих вершин имеют ровно одну общую вершину.

Подсчёт деревьев

• Число различных деревьев, которые можно построить на <math>n</math> нумерованных вершинах, равно <math>n^{n-2}</math> (Теорема Кэли).
• Производящая функция

<math>T(z)=\sum_{n=1}^\infty T_nz^n</math>

для числа <math>T_n</math> неизоморфных корневых деревьев с <math>n</math> вершинами удовлетворяет функциональному уравнению

<math>T(z)=z\exp\sum_{r=1}^\infty\frac1r T(z^r)</math>.

• Производящая функция

<math>t(z)=\sum_{n=1}^\infty t_nz^n</math>

для числа <math>t_n</math> неизоморфных деревьев с <math>n</math> вершинами можно представить с помощью перечисляющего ряда для корневых деревьев:

<math>t(z)=T(z)-\frac12\left(T^2(z)-T(z^2)\right).</math>

• При <math>n\to\infty</math> верна следующая асимптотика

<math>t_n\sim C\alpha^n/n^{5/2}</math>

где <math>C</math> и <math>\alpha</math> определённые константы, <math>C=0,534948...</math>, <math>\alpha=2,95576...</math>.

Кодирование деревьев

Дерево можно кодировать наборами из нулей и единиц. Рассмотрим, например, укладку дерева на плоскости. Начиная с какой либо вершины, будем двигаться по ребрам дерева, сворачивая в каждой вершине на ближайшее справа ребро и поворачивая назад в концевых вершинах дерева. Проходя по некоторому ребру, записываем <math>0</math> при движении по ребру в первый раз и <math>1</math> при движении по ребру второй раз (в обратном направлении). Если <math>m</math> — число рёбер дерева, то через <math>2m</math> шагов мы вернемся в исходную вершину, пройдя по каждому ребру дважды. Полученная при этом последовательность из <math>0</math> и <math>1</math> (код дерева) длины <math>2m</math> позволяет однозначно восстанавливать не только само дерево <math>D</math>, но и его укладку на плоскости. Произвольному дереву соответствуют несколько таких кодов. В частности, из этого способа кодирования вытекает следующая грубая оценка на число деревьев с <math>n</math> вершинами:

<math>t_n\le T_n< 2^{2n}</math>

См. также

• Глоссарий теории графов
• Лес непересекающихся множеств

Литература

• Дональд Кнут. Искусство программирования, том = The Art of Computer Programming, vol. 1. Fundamental Algorithms. — 3-е изд. — М.: Вильямс, 2006. — Т. 1. Основные алгоритмы. — 720 с. — ISBN 0-201-89683-4.
• Оре О. Теория графов. — 2-е изд. — М.: Наука, 1980. — 336 с.
• Харари Ф. Теория графов. — М.: Мир, 1973. — 302 с.

Отрывок, характеризующий Дерево (теория графов)

Анна Михайловна глубоко вздохнула: – Долохов, Марьи Ивановны сын, – сказала она таинственным шопотом, – говорят, совсем компрометировал ее. Он его вывел, пригласил к себе в дом в Петербурге, и вот… Она сюда приехала, и этот сорви голова за ней, – сказала Анна Михайловна, желая выразить свое сочувствие Пьеру, но в невольных интонациях и полуулыбкою выказывая сочувствие сорви голове, как она назвала Долохова. – Говорят, сам Пьер совсем убит своим горем.
– Ну, всё таки скажите ему, чтоб он приезжал в клуб, – всё рассеется. Пир горой будет.
На другой день, 3 го марта, во 2 м часу по полудни, 250 человек членов Английского клуба и 50 человек гостей ожидали к обеду дорогого гостя и героя Австрийского похода, князя Багратиона. В первое время по получении известия об Аустерлицком сражении Москва пришла в недоумение. В то время русские так привыкли к победам, что, получив известие о поражении, одни просто не верили, другие искали объяснений такому странному событию в каких нибудь необыкновенных причинах. В Английском клубе, где собиралось всё, что было знатного, имеющего верные сведения и вес, в декабре месяце, когда стали приходить известия, ничего не говорили про войну и про последнее сражение, как будто все сговорились молчать о нем. Люди, дававшие направление разговорам, как то: граф Ростопчин, князь Юрий Владимирович Долгорукий, Валуев, гр. Марков, кн. Вяземский, не показывались в клубе, а собирались по домам, в своих интимных кружках, и москвичи, говорившие с чужих голосов (к которым принадлежал и Илья Андреич Ростов), оставались на короткое время без определенного суждения о деле войны и без руководителей. Москвичи чувствовали, что что то нехорошо и что обсуждать эти дурные вести трудно, и потому лучше молчать. Но через несколько времени, как присяжные выходят из совещательной комнаты, появились и тузы, дававшие мнение в клубе, и всё заговорило ясно и определенно. Были найдены причины тому неимоверному, неслыханному и невозможному событию, что русские были побиты, и все стало ясно, и во всех углах Москвы заговорили одно и то же. Причины эти были: измена австрийцев, дурное продовольствие войска, измена поляка Пшебышевского и француза Ланжерона, неспособность Кутузова, и (потихоньку говорили) молодость и неопытность государя, вверившегося дурным и ничтожным людям. Но войска, русские войска, говорили все, были необыкновенны и делали чудеса храбрости. Солдаты, офицеры, генералы – были герои. Но героем из героев был князь Багратион, прославившийся своим Шенграбенским делом и отступлением от Аустерлица, где он один провел свою колонну нерасстроенною и целый день отбивал вдвое сильнейшего неприятеля. Тому, что Багратион выбран был героем в Москве, содействовало и то, что он не имел связей в Москве, и был чужой. В лице его отдавалась должная честь боевому, простому, без связей и интриг, русскому солдату, еще связанному воспоминаниями Итальянского похода с именем Суворова. Кроме того в воздаянии ему таких почестей лучше всего показывалось нерасположение и неодобрение Кутузову.
– Ежели бы не было Багратиона, il faudrait l'inventer, [надо бы изобрести его.] – сказал шутник Шиншин, пародируя слова Вольтера. Про Кутузова никто не говорил, и некоторые шопотом бранили его, называя придворною вертушкой и старым сатиром. По всей Москве повторялись слова князя Долгорукова: «лепя, лепя и облепишься», утешавшегося в нашем поражении воспоминанием прежних побед, и повторялись слова Ростопчина про то, что французских солдат надо возбуждать к сражениям высокопарными фразами, что с Немцами надо логически рассуждать, убеждая их, что опаснее бежать, чем итти вперед; но что русских солдат надо только удерживать и просить: потише! Со всex сторон слышны были новые и новые рассказы об отдельных примерах мужества, оказанных нашими солдатами и офицерами при Аустерлице. Тот спас знамя, тот убил 5 ть французов, тот один заряжал 5 ть пушек. Говорили и про Берга, кто его не знал, что он, раненый в правую руку, взял шпагу в левую и пошел вперед. Про Болконского ничего не говорили, и только близко знавшие его жалели, что он рано умер, оставив беременную жену и чудака отца.


3 го марта во всех комнатах Английского клуба стоял стон разговаривающих голосов и, как пчелы на весеннем пролете, сновали взад и вперед, сидели, стояли, сходились и расходились, в мундирах, фраках и еще кое кто в пудре и кафтанах, члены и гости клуба. Пудренные, в чулках и башмаках ливрейные лакеи стояли у каждой двери и напряженно старались уловить каждое движение гостей и членов клуба, чтобы предложить свои услуги. Большинство присутствовавших были старые, почтенные люди с широкими, самоуверенными лицами, толстыми пальцами, твердыми движениями и голосами. Этого рода гости и члены сидели по известным, привычным местам и сходились в известных, привычных кружках. Малая часть присутствовавших состояла из случайных гостей – преимущественно молодежи, в числе которой были Денисов, Ростов и Долохов, который был опять семеновским офицером. На лицах молодежи, особенно военной, было выражение того чувства презрительной почтительности к старикам, которое как будто говорит старому поколению: уважать и почитать вас мы готовы, но помните, что всё таки за нами будущность.
Несвицкий был тут же, как старый член клуба. Пьер, по приказанию жены отпустивший волоса, снявший очки и одетый по модному, но с грустным и унылым видом, ходил по залам. Его, как и везде, окружала атмосфера людей, преклонявшихся перед его богатством, и он с привычкой царствования и рассеянной презрительностью обращался с ними.
По годам он бы должен был быть с молодыми, по богатству и связям он был членом кружков старых, почтенных гостей, и потому он переходил от одного кружка к другому.
Старики из самых значительных составляли центр кружков, к которым почтительно приближались даже незнакомые, чтобы послушать известных людей. Большие кружки составлялись около графа Ростопчина, Валуева и Нарышкина. Ростопчин рассказывал про то, как русские были смяты бежавшими австрийцами и должны были штыком прокладывать себе дорогу сквозь беглецов.
Валуев конфиденциально рассказывал, что Уваров был прислан из Петербурга, для того чтобы узнать мнение москвичей об Аустерлице.
В третьем кружке Нарышкин говорил о заседании австрийского военного совета, в котором Суворов закричал петухом в ответ на глупость австрийских генералов. Шиншин, стоявший тут же, хотел пошутить, сказав, что Кутузов, видно, и этому нетрудному искусству – кричать по петушиному – не мог выучиться у Суворова; но старички строго посмотрели на шутника, давая ему тем чувствовать, что здесь и в нынешний день так неприлично было говорить про Кутузова.
Граф Илья Андреич Ростов, озабоченно, торопливо похаживал в своих мягких сапогах из столовой в гостиную, поспешно и совершенно одинаково здороваясь с важными и неважными лицами, которых он всех знал, и изредка отыскивая глазами своего стройного молодца сына, радостно останавливал на нем свой взгляд и подмигивал ему. Молодой Ростов стоял у окна с Долоховым, с которым он недавно познакомился, и знакомством которого он дорожил. Старый граф подошел к ним и пожал руку Долохову.