Элементы теории деревьев

Применение методов искусственного интеллекта в переборных алгоритмах

В начале определим дерево (в индуктивной форме). Элементами дерева являются вершины и дуги, то есть направленные ребра. При этом одна из инцидентных дуге вершин называется ее началом, а другая - концом. Деревом является: а) одна вершина; б) дерево с добавленными вершиной и дугой, начинающейся в старой и заканчивающейся в новой вершине. Если старая вершина обозначена как А, а новая - В, то дуга из первой во вторую обозначается АВ.

Корнем дерева называется вершина, в которую не ведет ни одна дуга. Концевой вершиной (листом) называют такую, из которой не исходит ни одна дуга. Непустое подмножество дерева A, составляющее дерево, называют поддеревом дерева A. Если B и C - поддеревья дерева A, а D - их непустое пересечение, то D - поддерево дерева A.

Говорят, что вершина В подчинена вершине А, если: а) В?А; б) В - конец дуги, выходящей из вершины, подчиненной А.

Если А - вершина дерева A, то А-поддеревом дерева A называют такое его поддерево, которое содержит все подчиненные A вершины, и только их. Если А - не корневая вершина, то открытым поддеревом называют А-поддерево вместе с дугой. Если из дерева A выбросить открытое А-поддерево, то оставшееся будет деревом.

Будем считать корень вершиной ранга 0. Если вершина А имеет ранг n, а АВ - дуга дерева, то вершина В имеет ранг n+1.

Пусть А - вершина дерева, В - вершина А-поддерева, тогда веткой W(A,B) будем называть последовательность дуг АА₁, А₁А₂, ..., А_sВ, принадлежащих дереву, если она существует. При этом если ветка W(A,B) существует, то она единственна.

А.В.Мосеев, underwood.narod.ru, 1999 год