ЕСТЕСТВЕННЫЕ НАУКИ

6.21. Идентификация в химии

Одна из основных задач теории графов состоит в нахождении хорошего алгоритма для определения того, являются ли два конечных графа одинаковыми в абстрактном смысле или, в более общем случае, является ли один граф подграфом другого. Первая задача называется задачей идентификации графа, а вторая — задачей идентификации подграфа. Чтобы формулировка задачи была более четкой, слову «хороший» нужно придать некоторый математический смысл. Будем считать, что алгоритм является «хорошим», если объем вычислений связанных с его применением для любой пары графов, растет в худшем случае как степенная функция, а не экспоненциально с ростом числа ребер в выбранной паре графов.

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

Существование нескольких видов атомов не вносит серьезных трудностей в задачу идентификации. В настоящее время много внимания уделяется разработке «эвристических» алгоритмов химической идентификации — алгоритмов, не являющихся «хорошими» в нашем

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

Алгоритм идентификации деревьев использует каталожную систему, построенную на основе линейного упорядочения множества всех конечных деревьев. Однако наличие такой системы совершенно не обязательно. Например, существует хороший алгоритм для определения идентичности (в комбинаторном смысле) любых двух поверхностных карт. Карты обладают свойством комбинаторной «жесткости» — так, что если карты и идентичны и установлено, что ребро идентично ребру конечная точка ребра идентична с конечной точкой ребра и грань содержащая идентична с гранью содержащей идентификация оставшихся частей однозначна и легко устанавливается. Таким образом, для того чтобы установить идентичность карт необходимо только идентифицировать ребро с каждым ребром четырьмя способами, соответствующими каждому возможному способу идентификации вершины и грани Из такой процедуры, конечно, непосредственно не следует система каталогизации карт.

Упомянутое выше свойство «жесткости» можно использовать для определения идентичности деревьев а также идентичности их способа изображения на плоскости. Под идентичностью способа изображения мы будем понимать, что для каждой пары взаимно идентичных вершин ребра, которые пересекаются в в изображении располагаются вокруг в том же самом порядке, в каком идентичные ребра расположены вокруг в изображении дерева Различные способы изображения одинаковых деревьев обычно усложняют проверку на идентичность, а число различных способов изображения дерева, вообще говоря, растет экспоненциально с числом ребер в дереве.

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

деревьев есть процедура приведения деревьев к каноническому виду.

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

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

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

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

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

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

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

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

словами, является фактором фактора... фактора Величина члена который соответствует равна числу вершин в

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

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

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

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

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

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

корневому дереву при совпадении их корней. Такой алгоритм было бы очень интересно получить.

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