ДО_Лекция _4
Алгоритмы построения деревьев
Существует простой и важный тип графов - это деревья. Деревья важны не только потому, что они находят приложения в различных областях знания, но и в силу их особого положения в самой теории графов.
Часто при решении какой-либо задачи о графах ее сначала исследуют на деревьях [Харари,1973].
Определение: Дерево - это связный ациклический граф.
Граф, не содержащий циклов, называется лесом (компонентами леса являются деревья).
Если зафиксирована некоторая вершина ao, то она называется корнем дерева, а само дерево называется деревом с корнем.
Другие определения понятия "дерево" [Харари,1973]:
Пусть задан графа G, имеющего p вершин и q ребер
Утверждения:
(1) граф G - дерево;
(2) любые две вершины в графе G соединены единственной цепью;
(3) граф G - связный граф и p=q+1;
(4) граф G - ациклический граф и p=q+1;
(5) граф G - ациклический граф, и если любую пару несмежных вершин соединить ребром x, то в графе G+x будет точно один цикл;
(6) граф G - связный граф, отличный от Kp для p ≥3, и если любую пару несмежных вершин соединить ребром x, то в графе G+x будет точно один цикл.
(7) граф G - граф, отличный от K3K1 и K3K2, p=q+1, и если любую пару несмежных вершин соеди-нить ребром x, то в графе G+x будет точно один цикл.
Cледствия:
(1) в любом нетривиальном дереве имеется, по крайней мере, две висячие вершины [Харари,1973];
(2) каждое дерево с n вершинами имеет ровно n-1 ребро [Липский,1988].
Определение: Неориентированный граф, получающийся в результате "снятия ориентации с дуг" ориентированного графа G, называется лежащим в основе неориентированного графа G.
Ориентированный граф G называется деревом, если лежащий в его основе неориентированный граф также является деревом.
Ориентированный граф G называется ориентированным (корневым) деревом, если он является деревом и имеет корень. Поддеревом корневого дерева T называется его часть T', которая является корневым деревом, удовлетворяющим следующему условию: вместе с корнем v' дерево T' содержит все вершины и дуги, достижимые в T из v'.
Вершины графа G с нулевой полустепенью исхода (иными словами, не имеющие приемников), называются листьями.
Корневое дерево удовлетворяет следующим условиям:
(а) имеется ровно одна вершина, называемая корнем, в которую не входит ни одна дуга;
(б) в каждую вершину, отличную от корня, входит ровно одна дуга;
(в) приемники всякой вершины упорядочены.
Определение [Берж,1962]: Ориентированный конечный граф (V,E) есть прадерево с корнем x1V (корневое дерево с корнем x1V), если:
(1) в каждую вершину, отличную от вершины x1, заходит единственная дуга;
(2) в вершину x1 не заходит ни одна дуга;
(3) граф (V,E) не содержит контуров.
Определения
Двоичное дерево - это корневое дерево, в котором каждая вершина имеет не более двух преемников, называемых левыми и правыми приемниками (сыновьями).
2-3-дерево - это корневое дерево, в котором расстояния от корня до всех листьев совпадают, а каждая вершина, отличная от листа, имеет двух или трех преемников.
Деревом двоичного поиска для множества чисел S называется размеченное двоичное дерево, в котором каждая вершина v помечена числом l(v)ОS, и которое удовлетворяет следующим условиям:
(а) l(u)<l(v) для всех вершин u, v, если вершина u находится в поддереве, корень которого - левый преемник v;
(б) l(u)>l(v) для всех вершин u, v, если вершина u находится в поддереве, корень которого правый преемник v;
(в) для всякого A, принадлежащего S, существует единственная вершина v, для которой l(v)=A.
Обозначим через r(T) максимум среди расстояний от корня дерева T до его листьев.
АВЛ-деревом называется дерево двоичного поиска, в котором для каждой вершины v выполнено следующее условие: |(T1)- (T2)|≤1, где v1,v2 - приемники v, а T1,T2 - поддеревья с корнями v1,v2.
(а) дерево двоичного поиска; |
(б) АВЛ-дерево |
Определение: Обход корневого дерева T состоит в посещении вершин этого дерева в некотором порядке.
Прямой обход (П-обход) корневого дерева T описывается следующим образом:
(1) посетить корень v;
(2) выполнить П-обход поддеревьев с корнями v1,...,vn в указанной последовательности.
Обратный обход (О-обход) корневого дерева T описывается так:
(1) выполнить О-обход поддеревьев с корнями v1,...,vn в указанной последовательности;
(2) посетить корень v.
Обход во внутреннем порядке (В-обход) корневого дерева T определяется так:
(1) выполнить В-обход левого поддерева корня дерева T;
(2) посетить корень v дерева T;
(3) выполнить В-обход правого поддерева корня дерева T.