Тема электронные средства обучения и их использование

§ деревом называется связный неориентированный граф, у которого удаление одного
ребра приводит к нарушению связности,
§ деревом называется связный неориентированный граф, имеющий n вершин и n-1 реб-
ро,
§ деревом называется граф без циклов с n вершинами и n-1 ребрами,
§ деревом называется неориентированный граф, все возможные пути в котором про-
стые, т.е. ни одна вершина не входит в них дважды.
Не ссылаясь на понятие графа и не рассматривая дерево как частный случай графа,
можно определить дерево через свойства его вершин и отношений между ними.
Деревом (иерархией) можно назвать граф, в каждую вершину которого приходит не
более одного ребра. Исходить же из вершины может любое количество ребер. Вершина, из
которой исходит ребро по отношению к вершине, в которую ребро приходит, называется ро-
дительской. Наоборот, вершина, в которую приходит ребро, называется сыновней. Таким
образом, в дереве для каждой сыновней вершины может существовать не более одного роди-
теля. Выделяются вершины с особым сочетанием связей. Вершина, не имеющая родителей,
называется корнем дерева. Вершины, не имеющие сыновних вершин, называются листьями
дерева.
Внимательное рассмотрение структуры, которую порождает дерево, приводит к фор-
мулировке основного свойства дерева: каждая вершина обязательно достижима из корня.
Иначе говоря, если вершина А - корень дерева, а вершина В - любая вершина дерева, то су-
ществует путь из вершины А в вершину В, притом единственный.
Каждая вершина вместе с системой сыновних вершин, в свою очередь, образует дерево
с корнем в данной вершине. По отношению к объемлющему дереву такое дерево называется
поддеревом. Примеры деревьев приведены на рисунке.

---

112
Одним из ключевых моментов манипулирования с иерархическими информационными
структурами является достаточно хорошая формализация последовательного обхода всех
вершин дерева (иерархии). Рассмотрим основные положения, касающиеся обхода вершин с
целью их последующего учета при разработке и описании технологии информационного ин-
тегрирования и конкретных ЭСО.
Для так называемого обхода дерева в глубину можно воспользоваться тремя способа-
ми: проходить вершины в префиксном, инфиксном или постфиксном порядке. Эти способы
обхода дерева определяются следующим образом. В случае, когда дерево пусто, оно прохо-
дится без выполнения каких-либо действий. В противном случае прохождение складывается
из трех видов действий, одних и тех же для разных способов, но выполняемых в разной по-
следовательности.