Перечисление - деревей
Cтраница 2
Это соотношение позволяет дать очень краткое доказательство формулы Оттера для перечисления деревьев. [16]
Интересно посмотреть, что произойдет, если применить к задаче перечисления помеченных ориентированных деревьев наш обычный метод производящих функций. Для этой цели, пожалуй, проще всего рассмотреть величину т ( п, q) - число помеченных направленных графов с п вершинами, в которых нет ориентированных циклов и в которых от каждой из q помеченных вершин исходит по одной дуге. [17]
В большой и важной части статьи Пойа [10] речь идет о перечислении деревьев. Эти вопросы здесь рассматриваться не будут, так как все понятия эквивалентности деревьев очень сложны. Мы их оставляем для статьи Харари, стр. В этой статье мы будем стремиться элементарно изложить и полностью описать комбинаторные понятия, заменяя первоначальные интуитивные представления конкретными понятиями, такими, как множества и отображения. Однако в вопросах, связанных с классами эквивалентности деревьев, представляется трудным провести эту программу при первом знакомстве, и, что еще хуже, от этого проиграло бы изящество предмета, в котором интуиция занимает такую большую часть. [18]
 |
Помеченные мономеры ( а и девять способов ( б - в их объединения в тример, первые восемь из которых ( ( 3 2 - 2 - 2 приводят к изоморфным. [19] |
Возникающее при этом суммирование обратных порядков групп автоморфизмов можно свести к известной задаче перечисления корневых упорядоченных деревьев. [20]
Таким образом, можно решить первую из перечисленных выше проблем - проблему членства путем перечисления деревьев и проверки каждого из них, не является ли оно деревом вывода этой функциональной зависимости. Но хотя и может быть показано, что для любой / е ( / 7) существует дерево вывода, основанное на F, такое, что ни один из путей из корня в висячую вершину не содержит один и тот же атрибут дважды, такой способ неприемлем из-за больших временных затрат. Так как атрибуты, стоящие в правой части функциональной зависимости, должны взвешивать корневые вершины соответствующих IX-ДВ, основанных на F, то, получив все множество атрибутов, каждый из которых взвешивает корни некоторого X-ДВ, основанного на F, можно проверить вхождение нужных атрибутов в это множество и тем самым решить задачу. [21]
Это утверждение о связи между / ( г) и g ( z) дает нам интересное представление для формулы перечисления деревьев Пойа из упр. [22]
Чтобы вывести формулу для ряда t ( x), перечисляющего 2-де-ревья, воспользуемся теоремой о характеристике неподобия для 2-деревьев и формулой (3.5.1) абсолютно так же, как поступил Оттер при перечислении деревьев. [23]
Энергия молекулы с разнотипными связями зависит не только от состава 1, но и от чисел 6ц связей, образовавшихся в результате реакции функциональных групп i - ro и / - го типов, поэтому вычисление ММР и РСР сводится к перечислению упорядоченных деревьев с заданным распределением 1 цветных вершин и матрицей В ( Ьц ] цветных связей. При этом помимо счетчиков звеньев sv необходимо ввести счетчики Хц связей разных типов. [24]
Причем последние появляются только в результате разрезания. Перечисление получающихся деревьев предлагается производить, используя изложенную выше хему обычного ветвящегося процесса, но с учетом того, что у произвольного мономерного звена теперь могут быть и циклические функциональные группы. [25]
Здесь 9i обозначает порядок группы автоморфизмов нестянутого молекулярного графа i - ro изомера, а в знаменателе фигурной скобки стоит порядок группы автоморфизмов изолированного цикла. Далее соотношение (1.21) приводит к перечислению упорядоченных деревьев заданного состава. Само распределение впервые было найдено в работе [50] прямым комбинаторным вычислением числа способов сборки молекул с заданным вектором циклов. Такой метод, в отличие от только что описанного, более утомителен и труднее поддается обобщению на случай многокомпонентных систем. [26]
 |
Различные топологические ориентации цикла, стягивающиеся в одну и ту же вершину листовой композиции. [27] |
Порядок группы автоморфизмов У ( m, q) этой листовой композиции выражается формулой (1.21) через число отвечающих ей корневых упорядоченных деревьев. Таким образом задача построения пространственной меры циклических молекул сводится к перечислению деревьев со многими типами вершин. [28]
Для применений к деревьям и графам, введенным Пойа [10], мы отсылаем к обзору Харари [9] и ссылкам, данным там; смотрите также Уленбек и Форд [16] и статью Харари ( стр. Сейчас мы будем рассматривать только применения и обобщения, которые не относятся к перечислению деревьев и графов. [29]
Тогда суммарная концентрация с ( 1) молекул заданного состава, пропорциональная сумме обратных порядков групп автоморфизмов ( 93 ( 1, 7)) - 1, сведется, согласно (1.21), к перечислению упорядоченных деревьев с заданным распределением типов вершин. [30]
Страницы: 1 2 3