Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Ориентированные деревья

Определение. Ориентированным деревом (или ордеревом) называется ориентированный граф без циклов, во все вершины которого, кроме одной, входит ровно одна дуга. Единственная вершина, из которой дуги только выходят, называется корнем дерева. Остальные вершины называются узлами дерева.

Из определения дерева следует, что корень связан единственным путем с любой другой вершиной дерева.

На рис. 5 приведены диаграммы всех неизоморфных ориентированных деревьев с тремя и четырьмя вершинами.

Утверждение. Всякое дерево можно ориентировать.

Доказательство. Выберем произвольную вершину и дерева и назначим ее корнем. Ребра, инцидентные вершине и, ориентируем от вершины и. Далее повторим эту процедуру: войдя в некоторую вершину v по дуге, ориентируем все остальные ребра, инцидентные вершине v, от вершины v. Так как дерево не содержит циклов, ориентация ребер не приведет к противоречиям.

На рис. 6 приведен пример ориентированного дерева. Вершина, выбранная корнем, обозначена двойным кружком.

Выбор корня однозначно определяет ориентацию дерева. Поэтому каждому дереву с р вершинами соответствует р ориентированных деревьев.

Висячая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой ордерева. Расстояние от корня до некоторой вершины называется уровнем вершины. Сам корень имеет уровень 0. Вершины одного уровня образуют ярус дерева.

 

Другая терминология.

Вершины, достижимые из вершины и, называются потомками вершины и. Если в дереве существует дуга , то вершина и называется отцом вершины v, а вершина v называется сыном вершины и. Сыновья одного отца называются братьями.

Замечание. При изображении ориентированных деревьев принято помещать корень наверху и все стрелки дуг ориентировать сверху вниз, что избавляет от необходимости изображать эти стрелки.

На рис. 7 показано дерево с рис. 6, изображенное в соответствии с этими правилами. Вершины дерева разбиты на 4 яруса. Нулевой ярус содержит корень дерева. В первом и втором ярусах по 4 вершины, в третьем ярусе 8 вершин.

<== предыдущая лекция | следующая лекция ==>
Доказательство | Точки сочленения
Поделиться с друзьями:


Дата добавления: 2013-12-13; Просмотров: 1335; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.013 сек.