1.2. Математическое введение

Графом называется пара (A,R), где A - множество вершин графа, а R - множество его дуг, т.е пар вида (a,b), a,b Î A. Графически дуга представляется в виде стрелки, выходящей из вершины a и входящей в вершину b. 

Граф называется размеченным, если задано множество меток S, функция разметки вершин f : A ® S и функция разметки дуг g : R ® S. Графически эти функции представляются надписыванием меток на вершинах и дугах. Множество меток может разделяться на два непересекающихся подмножества меток вершин и меток дуг.

Граф называется упорядоченным, если дуги, выходящие из каждой вершины, однозначно пронумерованы, начиная с 1. Дуги считаются упорядоченными в порядке возрастания номеров. При графическом представлении часто дуги считаются упорядоченными в порядке некоторого стандартного обхода (например, слева направо).

Два графа (A₁,R₁) и (A₂,R₂) называются изоморфными, если существует взаимнооднозначное отображение h множества A₁ на A₂, для которого (a,b) Î R₁  (h(a),h(b)) Î R₂. Таким образом, h устанавливает соответствие между вершинами и дугами графов. Для изоморфности размеченных и упорядоченных графов требуется ещё, чтобы это соответствие сохраняло разметку вершин и дуг и порядок дуг.

Степенью вершины по входу называется число входящих в неё дуг, а степенью по выходу - число выходящих дуг.

Последовательность вершин (a₀,a₁,...,a_n), n і 0, называется путём длины n из a₀ в a_n, если (a_i,a_i+1) Î R для всех 0 Ј i < n. В этом случае a_n достижима из a₀. Циклом называется путь, в котором a₀ = a_n. Граф без циклов называется ациклическим. Замыканием пути (a₀,a₁,...,a_n) называется дуга (a₀,a_n).

Деревом называется граф, у которого

• одна вершина, называемая корнем, имеет степень по входу 0;
• остальные вершины имеют степень по входу 1;
• все вершины достижимы из корня.

У т в е р ж д е н и е  1.1. Дерево обладает следующими свойствами:

1. Для каждой вершины дерева существует единственный путь, ведущий в эту вершину из корня.
2. Дерево является ациклическим графом.

Доказательство. Пусть r - корень дерева. 

1. Так как каждая вершина достижима из корня, существует хотя бы один путь в неё из корня. Предположим, что в вершину a есть два различных пути из r. Тогда они имеют вид (r,a₁,...,a_n,c₁,...,c_k) и (r,b₁,...,b_m,c₁,...,c_k), где c_k = a и a_n № b_m. Тогда c₁ имеет не менее двух входящих дуг - из a_n и b_m, что невозможно для дерева.
2. Пусть (a₀,a₁,...,a_n) - цикл, т.е. a₀ = a_n. Он не проходит через корень, иначе корень имел бы входящую дугу. Пусть (r,...,a₀) - путь из корня в a₀ длины m. Тогда (r,...,a₀,a₁,...,a_n) - путь из корня в a₀ длины m + n, что противоречит первой части утверждения.

Ђ

Деревья в программировании обычно изображаются корнем вверх, с дугами направленными вниз (и без стрелок) и упорядоченными (в упорядоченном дереве) слева направо. Листом дерева называется его вершина со степенью по выходу 0. Последовательность листьев, перечисленных слева направо, называется кроной.

Если в дереве (a,b) Î R, то b называется сыном a, а a - родителем b. Если из a достижима b, то b называется потомком a, а a - предком b. Эти названия подчёркивают иерархические отношения в дереве.

Высотой дерева называется наибольшая длина пути от корня к листу. Дерево высоты 0 состоит из одного корня. 

Т е о р е м а  1.1 (о неограниченной высоте). Пусть T - бесконечное множество деревьев с ограниченной степенью по выходу. Тогда не существует константы, ограничивающей высоту деревьев из T. То же справедливо для множеств упорядоченных и размеченных деревьев с одним и тем же конечным множеством меток.

Доказательство. Предположим, что высота деревьев из T ограничена константой h. Пусть степень вершин по выходу ограничена константой m. Построим дерево t₀ высоты h и степенью по выходу всех вершин, кроме листьев, равной m. Это дерево конечно, т.к. число его вершин равно (mⁿ⁺¹-1)/(m-1). Каждое дерево t из T можно наложить на t₀, начиная с корня, так, чтобы каждая дуга t совпала с одной дугой t₀. Очевидно, что способов такого наложения конечное количество. Значит, T - конечное множество, что противоречит условию. Добавление нумерации и меток увеличивает число способов наложения деревьев из T на t₀, но оставляет его конечным.
Ђ

Поддеревом дерева t с корнем a Î t называется граф с множеством вершин, достижимых в t из a, и дугами, соединяющими их в t. Если  упорядочено и размечено, то порядок дуг и разметка в поддереве должны сохраняться. Очевидно, что поддерево также является деревом.