ВУЗ:
Составители:
Рубрика:
Рис. 1.11 Дерево
Деревом называется связанный граф, такой, что все возможные пути в нем являются дугами, т.е.
не содержат циклов и не проходят ни одной вершины более одного раза (рис. 1.11).
Начальная точка "0" (рис. 1.11) называется корнем дерева, отходящие от нее ребра "0а", "0б", "0с",
"0д" отделяют изолированные подграфы, похожие на ветви дерева. Именно из-за этого сходства такой
граф получил название дерева.
Дерево – это наиболее простой вид графа, легко поддающийся исследованию. Исследование других бо-
лее сложных графов сводится некоторым усложненным алгоритмом к исследованию соответствующего де-
рева.
Корень дерева называется вершиной нулевого уровня. Вершины, в которые можно перейти из
корня (вершины "а", "b", "с" на рис. 1.12)
Рис. 1.12 Вершины разных уровней
Рис. 1.13 Отношение между вершинами
называются вершинами первого уровня. Вершины, в которые можно попасть за один переход, называ-
ются вершинами второго уровня. Вершинами n-го уровня называются вершины, в которые можно по-
пасть за один переход из вершины n – 1-го уровня.
Если из вершины "а" (n – 1)-го уровня следуют вершины "б", "в", "г" следующего n-го уровня (рис.
1.13), то вершина "а" называется материнской, вершины "б", "в", "г" называются дочерними. Также
вершина "а" называется "предком", а вершины "б", "в", "г" – потомками.
Вершины, из которых не выходят ребра, называются конечными вершинами. Конечных вершин
может быть много.
Начальных вершин (корней) также может быть много. В случае дерева каждая начальная верши-
на (корень) выделяет изолированное дерево, так как у дерева в отличие от произвольного графа от-
сутствуют циклы.
Поиск решений в пространстве состояний
Первоначально следует рассмотреть состояние системы в виде дерева.
0 уровень
1 уровень
2 уровень
3 уровень
0
a
b
c
d e f
q
h
j
k
l
m
n
p
r
s
t
а
б
в
г
Страницы
- « первая
- ‹ предыдущая
- …
- 6
- 7
- 8
- 9
- 10
- …
- следующая ›
- последняя »
