Пояснение к работе

Практическое занятие № 9

Тема: «Деревья»

Цель занятия:

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

Время выполнения практического задания – 2 часа.

Последовательность выполнения

1. Руководствуясь приведенным теоретическим материалом, ответить на следующие вопросы:

Какое дерево называется остовным? Привести пример.

Как определяется цикломатическое число графа?

Какой граф является ориентированным деревом?

Как определяются высота ордерева и высота вершины ордерева?

Какое дерево называется упорядоченным?

Как определяется глубина вершины?

Что такое уровень вершины ордерева?

Какие деревья являются изоморфными?

2. Дать определение следующих понятий:

– неориентированное дерево;

– лес.

3. Выполнить задания для аудиторных занятий.

4. Выполнить задания для самостоятельной работы.

9.1. Основные определения

Неориентированным деревом (или просто деревом) называется связный граф без циклов. Этому определению эквивалентны, как легко показать, следующие определения:

а) дерево есть связный граф, содержащий р вершин и р – 1 ребер;

б) дерево есть граф, любые две вершины которого можно соединить простой цепью.

Пример. Графы, изображенные на рис. 34, являются деревьями.

а) б) в) Рис. 3

Рис. 34

Если граф несвязный и не имеет циклов, то каждая его связная компонента будет деревом. Такой граф называется лесом.

Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Пример. Для графа, изображенного на рис. 35 а, графы на рис. 35 б и 35 в) являются остовными деревьями.

а) б) в)

Рис. 35

Пусть граф G имеет р вершин и q ребер. Так как всякое дерево с р вершинами по определению имеет р – 1 ребер, то любое остовное дерево графа G получается из этого графа в результате удаления q – (р – 1) = q – р + 1 ребер. Число g = q – р + 1 называется цикломатическим числом графа.

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

Ориентированным деревом называется орграф со следующими свойствами:

1. Существует единственный узел, для которого полустепень захода равна 0.

2. Полустепень захода для остальных узлов равна 1.

3. Каждый узел достижим из корня.

4. Если в ордереве отменить ориентацию ребер, то получится свободное дерево.

5. В ордереве нет контуров.

6. Для каждого узла существует единственный путь, ведущий в этот узел из корня.

7. Если в свободном дереве любую вершину назначить корнем, то получится ордерево. Каждое свободное дерево определяет не более р ориентированных деревьев.

Вершину v ордерева называют потомком вершины j, если существует путь из j в v. Вершина, не имеющая потомков, – лист.

Рассмотрим некоторые числовые параметры, которые характеризуют ордерево. Высота ордерева – это наибольшая длина пути из корня в лист. Глубина d(v) вершины v ордерева – это длина пути из корня в эту вершину. Высота h(v) вершины v ордерева – наибольшая длина пути из данной вершины в лист. Уровеньвершины ордерева – это разность между высотой ордерева и глубиной данной вершины.

Пример. Приведем пример ориентированных деревьев (рис. 36).

Рис. 36

Упорядоченные деревья – это деревья, в которых относительный порядок поддеревьев фиксирован.

Пример. Рассмотрим три дерева, которые выглядят различными (рис. 37).

Рис. 37

Как упорядоченные деревья все они различны, как ориентированные деревья первое и второе одинаковы, а второе и третье различны, как свободные деревья все они изоморфны.

Задания

Для аудиторных занятий

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

2. Доказать, что количество рёбер дерева на единицу меньше количества вершин.

3. Доказать, что связными компонентами леса являются деревья.

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

5. Изобразить все возможные диаграммы деревьев из семи вершин.

6. Изобразить все попарно неизоморфные 4-вершинные ордеревья.

7. Для заданного дерева построить деревья, которые различны с исходным как упорядоченные деревья, одинаковые как ориентированные деревья, как свободные деревья изоморфны.

8. Для заданных деревьев (рис. 37) определить высоту ордерева, уровеньвершин.

9. Для заданных деревьев (рис. 36) определить высоту h(v) вершин, глубину d(v) вершин.

10. Для заданных деревьев (рис. 35 а, 35 б) построить все возможные ордеревья.

Для самостоятельной работы

1. Изобразить все попарно неизоморфные 5-вершинные деревья.

2. Доказать, что количество рёбер дерева на единицу меньше количества вершин.

3. Для заданных деревьев (рис. 26) определить высоту ордерева, уровеньвершин.

4. Для заданных деревьев (рис. 37) определить высоту h(v) вершин, глубину d(v) вершин.

5. Изобразить все возможные диаграммы деревьев из шести вершин.

6. Для заданного дерева построить деревья, которые различны с исходным как упорядоченные деревья, одинаковые как ориентированные деревья, как свободные деревья изоморфны.

7. Для заданных деревьев (рис. 37) построить все возможные ордеревья.

8. Для заданного дерева (рис. 35 б) построить изоморфные ему деревья.

9. Для заданного дерева (рис. 35 в) построить не изоморфные ему деревья.

10. Для заданного дерева (рис. 35 б) построить деревья, которые различны с исходным как упорядоченные деревья.

Литература

1. Новиков, Ф. А. Дискретная математика для программистов: учебник для вузов / Ф. А. Новиков. – СПб.: Питер, 2001. – 304 с.

2. Горбатов, В. А. Фундаментальные основы дискретной математики / В. А. Горбатов. – М.: Наука, 2000. – 544 с.

3. Акимов, О. Е. Дискретная математика. Логика, группы, графы – 2-е изд., доп. / О. Е. Акимов. – М.: Лаборатория базовых знаний, 2001. – 367 с.

Дата добавления: 2017-02-01