с) Предположим, что did2...dn и did2...dn-последовательности количеств узлов-наследников для двух лесов. Докажите, что существует третий лес с такой последовательностью количеств узлов-наследников:

min(di, di) min(d2,d2) - niin(d„,dn). 2.3.4. Основные математические свойства деревьев

Древовидные структуры еще задолго до изобретения компьютеров были объектом обширных математических исследований, а потому в течение многих лет было накоплено большое количество интересных фактов об их свойствах. В настоящем разделе предложен краткий обзор математической теории деревьев, который позволяет не только глубже понять их природу, но и применить эти результаты на практике в компьютерных алгоритмах.

Читателям, которым не интересна чисто математическая сторона обсуждаемых вопросов, рекомендуется сразу же перейти к подразделу 2.3.4.5, в котором с практической точки зрения рассматривается несколько вопросов, наиболее часто возникающих при использовании описываемых ниже приложений.

Приведенный ниже материал, в основном, относится к большому разделу математики, а именно - к теории графов. К сожалению, в этой области не существует устоявшейся терминологии, и автор придерживается обычной практики при написании современных книг по теории графов. Иначе говоря, здесь используются термины, аналогичные, но не идентичные тем терминам, которые применяются в других книгах по теории графов. В следующих подразделах (и далее во всей книге) будет предпринята попытка выбрать короткие, но емкие термины для наиболее важных понятий. Они будут выбраны среди общеупотребительных слов так, чтобы в то же время они не противоречили общепринятой терминологии. Следует учесть, что здесь эта терминология имеет непосредственное отношение к компьютерным приложениям. Поэтому инженер-электрик может назвать деревом то, что здесь называется свободным деревом, так как более краткий термин "дерево" обозначает более широкое понятие, которое часто используется в компьютерной литературе, а потому оно гораздо важнее в компьютерных приложениях. Если следовать терминологии, предлагаемой некоторыми авторами работ по теории графов, то следовало бы вместо термина "дерево" использовать термин "конечное упорядоченное дерево с указанным корнем", а вместо термина "бинарное дерево" - "топологическая раздвоенная древовидность"!

2.3.4.1. Свободные деревья. Граф (graph) обычно определяется как множество точек (называемых вершинами (vertices)) вместе с набором линий (называемых ребрами (edges)), которые соединяют определенные пары вершин. Каждая пара вершин соединяется не более чем одним ребром. Две вершины называются смежными (adjacent), если их соединяет ребро. Если V и V являются вершинами и я > О, то (Vo,Vi,... ,Vn) называется путем длины п от вершины V к вершине V, если V = Vo, вершина 14 является смежной для вершины T4+i для О < к < п, aV„ = V. Путь называется простым (simple), если различны вершины Vo,Vi,...,F„ i и если различны вершины Vi,..., V„ i, F„. Граф называется связным (connected), если существует путь между любыми двумя его вершинами. Циклом называется простой путь длиной, большей или равной трем, от некоторой вершины к ней самой.

Рис. 30. Свободное дерево.

Эти определения проиллюстрированы на рис. 29, на котором изображен связный граф с пятью вершинами и шестью ребрами. Вершина С является смежной с А, но она не смежная с вершиной В. От вершины В к вершине С ость два пути длиной два: {В,А,С) и {B,D,C). В этом графе имеется несколько циклов, например {B,D,E,B).

Свободное дерево (free tree), или дерево без корня (рис. 30), определяется как связный граф без циклов. Это определение применимо как для бесконечных графов, так и для конечных, хотя в компьютерных приложениях обычно используются только конечнью деревья. Можно привести несколько эквивалентных сгюсобов определения свободного дерева, например некоторые из них представлены в следающсй хорошо известной теореме.

Теорема А. Если G -граф, то для него будут эквивалентными следующие утве]у ждения.

a) G - свободное дерево.

b) G - связный граф, который прн удалении произвольного ребра перестает быть связным.

c) Если V и V -различные вершины графа G, то существует единственный простой путь от верш1шы V к вершине V.

Более того, если граф G конечен и содержит в точности п > О вершин, слсд}Ющпо утверждения также будут эквивалентны утверждениям (а)-(с).

d) G не содержит циклов и имеет п - 1 ребер.

e) G - связный граф, который имеет п - 1 ребер.

Доказательство. Из (а) следует (Ь), так как при удалении ребра V - V, при котором граф G остается связным, должен суш,ествовать простой путь {V, Vi,..., V) длины два или более (см. упр. 2), а тогда {V, Vl,..., V, V) будет циклом в G.

Из (Ь) следует (с), так как есть по крайней мере один путь от вершины V к вершине V. И, если бы существовало два таких пути {V, V,..., V) и [V, V{,..., V), можно было бы найти такое наименьшее к, для которого V,. Ф \1 при здалении ребра Vk-\ - Vk граф оставался бы связным, так как все еще существует путь (4-1 fc • • > • • к) вершины Т4 1 к вершине 14, который по включает удаленное ребро.

Из (с) следует (а), так как если G содержит цикл (Г,Y\,...,V), то существует два простых пути от вершины V к вершине V\.

Чтобы показать, что (d) и (е) также эквивалентны (а)-(с), сначала докажем вспомогательный результат: в конечном графе G без циклов и хотя бы с одним

ребром существует по крайней мере одна вершина, которая является смежной в точности для одной другой вершины. Докажем это, рассмотрев некоторую вершину Vi и смежную с цем другую вершину V2. Для к > 2 вершина 14 является смежной либо для вершины 14-1 и никакой другой, либо для какой-то другой, например с вершиной Vk+\ ф Ук-\- Поскольку в этом графе нет циклов, вершины Fl, V2, •, Ук+\ должны быть различными, а потому данный процесс должен в конечном итоге завершиться.

Предположим теперь, что G - это дерево с гг > 1 вершинами, а F„-вершина. Смежная только для какой-то одной другой вершины, например для вершины Vn-\-При удалении вершины F„ и ребра Vn-i - Кг полученный в результате граф G является деревом, так как вершина V„ может находиться в простом пути графа G только в качестве начального или конечного элемента. Таким образом, доказано (методом индукции по тг), что G имеет тг - 1 ребер, а значит, из (а) следует (d).

Предположим, что G удовлетворяет условию (d) и величины F„,

V,i ] и G

имеют тот же смысл, что и в предыдущем абзаце. Тогда граф G является связным, поскольку вершина У„ связана с вершиной K-i, которая (по индукции по п) связана со всеми другими вершинами графа G. Таки.м образом, из (d) следует (е).

Наконец, предположим, что граф G удовлетворяет условию (е). Если граф G содержит цикл, то можно удалить любое ребро этого цикла, не нарушая связность графа G. Следовательно, продолжая таким образом удалять ребра, получим связный граф G сп~\ - к ребрами и без циклов. Но поскольку из (а) следует (d), то fc = О, т. е. G = I

Понятие свободного дерева можно непосредственно использовать для анализа компьютерных алгоритмов. В разделе 1.3.3 уже рассматривалось применение первого закона Кирхгофа для решения задачи о подсчете числа выполнений каждого шага алгоритма. В результате было найдено, что закон Кирхгофа не позволяет полностью подсчитать это количество, но с его помощью можно сократить число неизвестных, значения которых еще потребуется особым образом интерпретировать. Благодаря теории деревьев можно установить количество оставшихся независимых неизвестных и предложить метод их поиска.

Рис. 31. -Абстрактная блок-схе.ма программы 1.3.ЗА.

Этот метод легче понять на конкретном примере, который впоследствии будет еще не раз использоваться для иллюстрации результатов применения данной теории. На рис. 31 показана абстрактная блок-схема программы 1.3.ЗА после ее анализа на основе закона Кирхгофа из раздела 1.3.3. Каждый квадратик (т. е. блок) на рис. 31