ВУЗ:
Составители:
64
Количество ребер, связанных с данной вершиной определяет степень
вершины, которая может принимать значения от 1 до р – 1. Вершины первой
степени являются концевыми вершинами, а связанные с ними ребра – концевы-
ми ребрами. Любое конечное дерево при р 2 имеет хотя бы две концевые
вершины и хотя бы одно концевое ребро.
Любому дереву
Т можно поставить во взаимно-однозначное соответст-
вие некоторую упорядоченную последовательность р – 2 номеров вершин
(Т) = (
1
,
2
, . . . ,
р-2
),
называемую символом дерева. Среди вершин
(Т) могут быть и по-
вторяющиеся, причем
1
,
2
, . . . ,
р-2
V. Для данного дерева эта последо-
вательность образуется следующим образом. Пусть дерево задано множеством
вершин
N
p
= (1, 2, …, p).
Из этого множества выбирается концевая вершина с наименьшим но-
мером и в последовательность
(Т) записывается номер
1
связанной с ней
вершины, а сама концевая вершина удаляется из множества N
p
. Затем из множе-
ства выбирается следующая по номеру концевая вершина и записывается номер
2
связанной с ней вершины, а сама вершина удаляется из последовательности
N
p
. Процесс повторяется до тех пор, пока не будет сформирована вся последо-
вательность
(Т) = (
1
,
2
, . . . ,
р-2
).
На рис. 5.11 показаны два изоморфных дерева Т
1
, Т
2
и соответствующие
им символы.
Рис. 5.11. Изоморфные деревья и их символы
Рассматриваются также деревья с ориентированными ребрами (дугами).
Ориентированное дерево называется прадеревом или корневым деревом с кор-
нем
0
, если существует путь между вершиной
0
и любой другой его верши-
ной.
1
2
3
4
5
6
(Т) = (4, 4, 4, 5, 5)
Т
1
7
5
2
6
4
(Т) = (1, 3, 1, 1, 3)
Т
2
7
1
3
Страницы
- « первая
- ‹ предыдущая
- …
- 62
- 63
- 64
- 65
- 66
- …
- следующая ›
- последняя »
