![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Дерево – связный граф без циклов. Лес (или ациклический граф) – неограф без циклов. Компонентами леса являются деревья.
Теорема 14.1. Для неографа G с n вершинами без петель следующие условия эквивалентны:
1) G – дерево;
2) G – связной граф, содержащий n – 1 ребро;
3) G – ациклический граф, содержащий n – 1 ребро;
4) Любые две несовпадающие вершины графа G соединяет единственная цепь;
5) G – ациклический граф, такой, что если в него добавить одно ребро, то в нем появится ровно один цикл.
Теорема 14.2. Неограф G является лесом тогда и только тогда, когда коранг графа v(G)=0.
Висячая вершина в дереве – вершина степени 1. Висячие вершины называются листьями, все остальные – внутренними вершинами.
Если в дереве особо выделена одна вершина, называемая корнем, то такое дерево называется корневым, иначе – свободным.
Корневое дерево можно считать орграфом с ориентацией дуг из корня или в корень. Очевидно, что для любой вершины корневого дерева, кроме корня, . Для корня
, для листьев
.
Вершины дерева, удаленные на расстояние k (в числе дуг) от корня, образуют k -й ярус (уровень) дерева. Наибольшее значение k называется высотой дерева.
Если из какой-либо вершины корневого дерева выходят дуги, то вершины на концах этих дуг называют сыновьями (в английской литературе – дочери (daughter)).
Дата публикования: 2014-11-28; Прочитано: 564 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!