Дискретно-непрерывная математика (стр. 82 )

В случае, когда получена вершина, будем считать, что она и есть корень дерева Т. В случае получения ребра примем за корень одну из его конечных точек, например, вершину, которая дает корневое дерево более низкого ранга (или любую конечную точку в случае, когда они дают одинаковые корневые деревья). Упоря­дочим все корневые деревья так, чтобы из любых двух неодинаковых деревьев одно имело меньший ранг. (При другом подходе в качестве корня дерева Т можно вы­брать одну из вершин, которая образует корневое дере­во с минимальным рангом. Выбор вершины в этом слу­чае не однозначен, а результирующее корневое дерево определяется однозначно. Независимо от метода опре­деления корня два дерева идентичны тогда и только тогда, когда соответствующие им корневые деревья оди­наковы. Первый метод кажется более простым.)

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

Ранг корневых деревьев устанавливается в соответ­ствии с лексикографическим упорядочением соответ­ствующих последовательностей. Таким образом, ранг Т1 меньше, чем T2, если существует целое число k такое, что для j<k j-е члены двух последовательностей равны и кроме того, k-й член в последовательности Т1 либо меньше k-гo члена в последовательности Т2, либо больше.

Если удалить из корневого дерева T корень r и ребра, которые инцидентны ему, то получится несколько де­ревьев, каждое из которых соответствует одному из удаленных ребер. Эти деревья называются факторами корневого дерева Т. Каждый фактор T содержит точно одну вершину, которая соединяется с r в T. Эта вершина рассматривается как корень фактора. Таким образом, корневое дерево Т, если оно не является просто един­ственной вершиной, однозначно разбивается на один или несколько факторов, которые представляют собой также корневые деревья.

Последовательность для корневого дерева Т, состоя­щего из единственной вершины, имеет один член, рав­ный 1. Для любого другого корневого дерева Т все члены последовательности S, соответствующей Т, кроме пер­вого, получаются из последовательностей Si, соответст­вующих факторам Тi дерева Т, упорядочением Si по воз­растанию ранга. Конечно, в случае совпадения некото­рых Si их порядок не имеет значения, важно только, чтобы все они присутствовали в S. Таким образом, со­вокупность членов всех Si содержит все члены S, кро­ме первого. Первый член S равен единице плюс сумма первых членов Si, т. е. числу вершин в Т.

Заметим, что существует единственное взаимно од­нозначное соответствие между членами S и вершинами Т, при котором первый член S соответствует корню Т, а другие члены S соответствуют тем же самым верши­нам, что и члены Si, из которых они были получены. Каждая вершина v в Т является корнем только одного корневого дерева (обозначим его через Tv), которое включается в индуктивное определение S. Другими словами, Tv является фактором фактора... фактора Т. Ве­личина члена S, который соответствует v, равна числу вершин в Tv.

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

Осталось проверить достаточность идентичности со­ответствующих последовательностей. Это легко сделать, убедившись, что из последовательности S действительно получается дерево Т с помощью следующей однознач­ной процедуры.

Если S состоит из единственного члена, то он равен 1 и Т состоит из одной вершины. Если членов несколько, то, отбрасывая первый член S, все остальные члены можно разбить на несвязанные подпоследовательности Si (i=1 ,...,п), состоящие из следующих друг за другом членов S, так, что там, где ui обозначает первый член Si, ui есть второй член S. Кроме того, ui (i>1) есть ближайший к ui-1 член Si, величина которого не меньше ui-1. После un нет члена, величина которого была бы не меньше un.

Определенные таким образом Si являются последо­вательностями, соответствующие факторам Ti дерева Т. Это следует из двух фактов:

(1) первый член последо­вательности, соответствующей корневому дереву, больше всех остальных членов; 2) последовательности, соответ­ствующие факторам Т, располагаются в S в порядке возрастания их рангов.

После построения Ti, соответствующих Si, строится корневое дерево Т. Оно получается путем соединения дополнительной вершины (корня T) с корнями всех Ti. Описание процедуры построения корневого дерева по соответствующей ему последовательности завершается индукцией по размеру последовательности.

Рассмотренный метод идентификации деревьев вряд ли может дать хороший алгоритм решения более общей задачи определения того, содержит ли данное корневое дерево подграф, идентичный другому заданному корневому дереву при совпадении их корней. Такой алгоритм было бы очень интересно получить.

Упражнение 25. Показать, что последовательности, полученные удалением всех членов, равных 1, из последовательностей S, соответ­ствующих корневым деревьям, так же могут использоваться для идентификации деревьев, как и исходные последовательности S.

5.22. Простая модель из органической химии

Некоторые органические молекулы могут быть пред­ставлены как плоские графы. При этом атомы соответ­ствуют вершинам, а связи между атомами — ребрам. Простейшими из таких молекул являются углеводороды парафинового ряда СkH2k+2. Здесь k атомов углерода рассматриваются как вершины степени 4 (с учетом свя­зей как с водородом, так и с другими атомами углеро­да), a 2k+2 атомов водорода — как вершины степени 1. На приводимых ниже рисунках атомы водорода не по­казаны, так как они не влияют на изомеризм (т. е. на число различных типов связей в молекуле с фиксирован­ным числом атомов).

Общее число вершин п в этом случае будет равно 3k+2, а общее число ребер m=1/2(4k+2k+2)=3k+l. Так как число независимых циклов

т—п+1 в данном случае равно нулю, такие молекулы могут быть пред­ставлены в виде дерева, где кратные связи исключены. Деревья, образованные из k вершин, включают все воз­можные углеродные структуры, которые дают атомы. При k≥4можег быть несколько различных структур. Если добавить водородные связи в каждой части рис. 5.52 так, чтобы степени вершин, соответствующих атомам углерода, оказались равными 4, то можно убе­диться в том, что в каждом соединении присутствует необходимое число атомов водорода. Каждое такое соединение называется изомером.

Рис. 5.52.

Первая схема в каждой группе на рис. 5.52 соответ­ствует так называемой прямой цепи углеводорода (про­исхождение названия очевидно), а остальные — развет­вленным цепям углеводородов, К названиям последних часто добавляется приставка изо - (от понятия изомерии). Эти вещества возникают, естественно, как смеси всевоз­можных устойчивых изомеров. С ростом k свойства раз­личных изомеров становятся совершенно различными. Поэтому необходимо знать, сколько различных изоме­ров может быть в соединении.

В 1875 г. Кэли опубликовал первую работу по при­менению теории графов в химии. Он предложил способ решения названной задачи «без ошибки и повторения», При этом молекула представлялась корневым деревом, рассматривались все возможные структуры, а затем при­нималось решение о том, какие формы являются хими­чески эквивалентными. Например, для k = 5 существует девять корневых деревьев, изображенных на рис. 5.53

Рис. 5.53.

Можно видеть, что шесть из них химически эквивалент­ны трем остальным, Таким образом, для k=5 только три структуры, показанные на рис. 5.52, действительно являются изомерами.

Задачу повторения можно решить, представляя все фигуры в качестве «одноцентровых» или «бкцентровых»

Pис. 5.54.

деревьев, как на рис. 5.54. Под одноцентровым деревом понимается дерево, имеющее две или более главные ветви одинаковой высоты, инцидентные с корнем. Бицентровое дерево имеет два корня, Каждому корню ин­цидентны несколько главных ветвей, Здесь также важно, чтобы главные ветви имели одинаковую высоту, После введения названных понятий оказывается, что все дуб­лирования устраняются и мы снова получаем три хими­чески различных изомера,

Изображая всевозможные изомеры в соответствии с этим простым правилом, Кэли определил число струк­турных изомеров для парафинового ряда при всех зна­чениях k вплоть до 13. Этот результат приведен в таб­лице 5.1.

Таблица 5.1

Более глубокий результат в этой области опублико­ван также в 1875 г, Шиффом. Метод Шиффа тре­бует, чтобы рассматриваемые односвязные или насы­щенные углеводороды при k≥5 изображались по сим­метричной схеме, как показано на рис. 5.55.