Аноним

Дерево: различия между версиями

Материал из WEGA

Дерево (посмотреть исходный код)

Версия от 13:35, 3 февраля 2011

354 байта добавлено ,  3 февраля 2011
нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Дерево'''([[Tree|Tree]]) - [[связный граф|связный граф]] без циклов. Чаще всего этот термин используется как краткая форма термина [[корневое дерево|''корневое дерево'']], т.е. конечное множество одной или нескольких [[вершина|вершин]] таких, что, во-первых, среди них
'''Дерево'''([[Tree|Tree]]) — [[связный граф|связный граф]] без циклов. Чаще всего этот термин используется как краткая форма термина [[корневое дерево|''корневое дерево'']], т.е. конечное множество одной или нескольких [[вершина|вершин]] таких, что, во-первых, среди них
существует только одна особая вершина, называемая ''корнем'', и,
существует только одна особая вершина, называемая ''корнем'', и,
во-вторых, остальные вершины делятся на <math>d</math> непересекающихся множеств
во-вторых, остальные вершины делятся на <math>d</math> непересекающихся множеств
Строка 5: Строка 5:
деревом. Множества
деревом. Множества
<math>T_{1}, \, T_{2}, \ldots, \, T_{d}</math>называются [[поддерево|''поддеревьями'']] [[корень|корня]]. Если порядок в этих деревьях существен, дерево называется [[упорядоченное дерево|упорядоченным деревом]], в противном случае оно иногда называется неупорядоченным деревом. Дерево может быть представлено как [[граф|граф]], в котором корневая вершина представлена вершиной, соединенной [[дуга|дугами]] с вершинами, представляющими корни каждого из ее поддеревьев. Таким
<math>T_{1}, \, T_{2}, \ldots, \, T_{d}</math>называются [[поддерево|''поддеревьями'']] [[корень|корня]]. Если порядок в этих деревьях существен, дерево называется [[упорядоченное дерево|упорядоченным деревом]], в противном случае оно иногда называется неупорядоченным деревом. Дерево может быть представлено как [[граф|граф]], в котором корневая вершина представлена вершиной, соединенной [[дуга|дугами]] с вершинами, представляющими корни каждого из ее поддеревьев. Таким
образом, в терминах теории графов можно дать другое определение ([[ориентированное дерево|ориентированного]]) дерева: дерево --- это [[бесконтурный орграф|ориентированный бесконтурный
образом, в терминах теории графов можно дать другое определение ([[ориентированное дерево|ориентированного]]) дерева: дерево — это [[бесконтурный орграф|ориентированный бесконтурный
граф]] такой, что, во-первых, существует единственная вершина, в которую не входит ни одна дуга (эта вершина называется корнем), во-вторых, в каждую из оставшихся вершин входит ровно одна дуга, и, в-третьих, существует единственный путь из корня в любую другую вершину.
граф]] такой, что, во-первых, существует единственная вершина, в которую не входит ни одна дуга (эта вершина называется корнем), во-вторых, в каждую из оставшихся вершин входит ровно одна дуга, и, в-третьих, существует единственный путь из корня в любую другую вершину.


Строка 16: Строка 16:


==См. также==  
==См. также==  
[[АВЛ-Дерево|''АВЛ-дерево'']], ''[[Асимметричное дерево]]'', ''[[Бесконечное дерево]]'', ''[[Бинарное дерево]]'', ''[[Бинарное дерево сортировки]]'', ''[[Бицентральное  дерево]]'', ''[[Братское дерево]]'', [[1-2-Братское дерево|''1-2-братское дерево'']], ''[[Входящее дерево]]'', ''[[Выровненное дерево]]'', ''[[Вырожденное дерево]]'', ''[[Выходящее дерево]]'', ''[[Глубинное остовное дерево]]'', ''[[Гомеоморфно несводимое дерево]]'', ''[[Дерево обязательных предшественников]]'', ''[[Дерево обязательных преемников]]'', ''[[Доминаторное дерево]]'', ''[[Конечное дерево]]'', ''[[Корневое дерево]]'', ''[[Левостороннее дерево]]'', ''[[Линейное дерево]]'', ''[[Многомерное дерево сортировки]]'', [[Многомерное B-дерево|''Многомерное <math>B</math>-дерево'']], ''[[Ориентированное дерево]]'', ''[[Поисковое дерево]]'',
* [[АВЛ-Дерево|''АВЛ-дерево'']],
''[[Постдоминаторное дерево]]'', ''[[Плоское дерево]]'', [[r-Плотное дерево|''<math>r</math>-плотное дерево'']], ''[[Пустое дерево]]'', ''[[Свободное дерево]]'', ''[[Сильно плотное дерево]]'', [[Сильное B-дерево|''Сильное <math>B</math>-дерево'']], [[Симметричное бинарное B-дерево|''Симметричное бинарное <math>B</math>-дерево'']], ''[[Слабо плотное дерево]]'', [[Слабое B-дерево|''Слабое <math>B</math>-дерево'']], ''[[Сливаемое дерево]]'', ''[[Упорядоченное дерево]]'', [[B-Дерево|''<math>B</math>-дерево'']], [[BB-Дерево|''<math>BB</math>-дерево'']], [[H-Дерево|''<math>H</math>-дерево'']], [[HB-Дерево|''<math>HB</math>-дерево'']], [[HS-Дерево|''<math>HS</math>-дерево'']], [[1-Дерево|''<math>1</math>-дерево'']], [[k-Дерево малой высоты|''<math>k</math>-дерево малой высоты'']], [[kB-Дерево|''<math>kB</math>-дерево'']], [[k-d-Дерево|''<math>k-d</math>-дерево'']], [[2-3-Дерево|''2-3-дерево'']].
* ''[[Асимметричное дерево]]'',
* ''[[Бесконечное дерево]]'',
* ''[[Бинарное дерево]]'',
* ''[[Бинарное дерево сортировки]]'',
* ''[[Бицентральное  дерево]]'',
* ''[[Братское дерево]]'',
* [[1-2-Братское дерево|''1-2-братское дерево'']],
* ''[[Входящее дерево]]'',
* ''[[Выровненное дерево]]'',
* ''[[Вырожденное дерево]]'',
* ''[[Выходящее дерево]]'',
* ''[[Глубинное остовное дерево]]'',
* ''[[Гомеоморфно несводимое дерево]]'',
* ''[[Дерево обязательного предшествования]]'',
* ''[[Дерево обязательной преемственности]]'',
* ''[[Доминаторное дерево]]'',
* ''[[Конечное дерево]]'',
* ''[[Корневое дерево]]'',
* ''[[Левостороннее дерево]]'',
* ''[[Линейное дерево]]'',
* ''[[Многомерное дерево сортировки]]'',
* [[Многомерное B-дерево|''Многомерное <math>B</math>-дерево'']],
* ''[[Ориентированное дерево]]'',
* ''[[Поисковое дерево]]'',
* ''[[Постдоминаторное дерево]]'',
* ''[[Плоское дерево]]'',
* [[r-Плотное дерево|''<math>r</math>-плотное дерево'']],
* ''[[Пустое дерево]]'',
* ''[[Свободное дерево]]'',
* ''[[Сильно плотное дерево]]'',
* [[Сильное B-дерево|''Сильное <math>B</math>-дерево'']],
* ''[[Симметричное бинарное дерево]]'',
* ''[[Слабо плотное дерево]]'',
* [[Слабое B-дерево|''Слабое <math>B</math>-дерево'']],
* ''[[Сливаемое дерево]]'',
* ''[[Упорядоченное дерево]]'',
* [[B-Дерево|''<math>B</math>-дерево'']],
* [[BB-Дерево|''<math>BB</math>-дерево'']],
* [[H-Дерево|''<math>H</math>-дерево'']],
* [[HB-Дерево|''<math>HB</math>-дерево'']],
* [[HS-Дерево|''<math>HS</math>-дерево'']],
* [[1-Дерево|''<math>1</math>-дерево'']],
* [[k-Дерево малой высоты|''<math>k</math>-дерево малой высоты'']],
* [[kB-Дерево|''<math>kB</math>-дерево'']],
* [[k-d-Дерево|''<math>k-d</math>-дерево'']],
* [[2-3-Дерево|''2-3-дерево'']].
== Литература ==
== Литература ==
[Лекции],  
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.


[Евстигнеев-Касьянов/94]
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.




[[Категория:Деревья]]
[[Категория:Деревья]]
Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/6070