ВУЗ:
Составители:
Рубрика:
Глава 1. Основные понятия теории графов 33
стояние). Для нахождения остовных деревьев, удовлетворяющих оп-
ределенным условиям, можно использовать, например, алгоритм
поиска «в глубину» или алгоритм поиска «в ширину» из [15, 16, 25].
Ориентированным деревом с корнем а называется корневое дере-
во, в котором каждое ребро заменено дугой таким образом, что либо
из каждой вершины можно попасть в корень, двигаясь вдоль ориен-
тации дуг (входящее дерево), либо в каждую вершину можно по-
пасть из корня, двигаясь вдоль ориентации дуг (выходящее или рас-
тущее дерево). Таким образом, задание корня превращает дерево в
ордерево, которое является ациклическим графом.
Николай
(1623 – 1708)
Якоб
(1654 – 1705)
I
Николай
(1662 1716) –
Николай
(1687 – 1759)
I Николай
(1695 – 1726)
II Даниил
(1700 – 1782)
I
Иоганн
(1667 – 1748)
I
Иоганн
(1710 – 1790)
II
Иоганн
(1744 – 1807)
III Даниил
(1754 – 1834)
II
Христофор
(1782 1863) –
Иоганн Густав
(1811 1863) –
Якоб
(1759 – 1789)
II
Рис. 1.36. Упорядоченное родословное дерево семьи Бернулли
В ордереве каждая концевая вершина называется листом, а путь,
ведущий из корня в лист, называется ветвью. Вершины дерева, на-
ходящиеся на одном расстоянии от корня, называются ярусом дере-
ва. Номер яруса определяется расстоянием до корня. Длина наи-
Страницы
- « первая
- ‹ предыдущая
- …
- 31
- 32
- 33
- 34
- 35
- …
- следующая ›
- последняя »
