Теорема - перечисление
Cтраница 1
Теорема перечисления Редфилда может быть использована для подсчета числа суперпозиций и в тех случаях, когда конституэнты являются орграфами или когда среди конституэнт имеются и графы, и орграфы. Сам Редфилд проиллюстрировал свою теорему, строя суперпозиции циклов и ориентированных циклов, которые он использовал и отдельно друг от друга, и совместно. [1]
 |
Ожерелья с одним фиксированным цветом и двумя взаимозаменяемыми цветами. [2] |
Теорему перечисления степенной группы легко приспособить к решению таких задач, в которых область значений весовой функции принадлежит произвольному коммутативному кольцу, содержащему множество всех рациональных чисел. Однако нельзя сказать, что интуитивно интересные задачи такого уровня общности существуют в изобилии. [3]
Поэтому теорема перечисления ( см. Харари [7]) может быть дана в следующей форме. [4]
В приложениях теоремы перечисления Пойа часто встречаются определенные группы подстановок. [5]
Тогда более общий результат, даваемый теоремой перечисления Пойа для п переменных, может быть сформулирован так. [6]
Тогда более общий результат, даваемъи теоремой перечисления Пойа для п переменных, может бык сформулирован так. [7]
Уравнение (5.1.4) является вариантом следствия (2.5.1) из теоремы перечисления Пойа. Мы покажем, что редуцированная упорядоченная парная группа, порожденная группой Sp, как раз и является требуемой группой конфигураций. [8]
Уже в 1937 году, когда появилась его теорема перечисления, Пойа мог применить ее к задаче нахождения производящей функции, перечисляющей графы в соответствии с числами их вершин и ребер. Но об этом не было известно до появления статьи Харари [4] в 1955 году, в которой отражены детали доказательства. [9]
Группу подстановок, которая необходима нам для применения теоремы перечисления Пойа ( в форме следствия (2.5.1)), будем обозначать через Г ( Н) о Sp. Эта группа определяется следующим образом: положим G Н ( J Кр. [10]
Группу подстановок, которая необходима нам для применения теоремы перечисления Пойа ( в форме следствия (2.5.1)), будем обозначать через Г ( Н) о Sp. Эта группа определяется следующим образом: положим G Я U КР-п и заметим, что произведение Г ( Н) Sp. [11]
Доказательство - Уравнение (5.1.4) является вариантом следствия (2.5.1) из теоремы перечисления Пойа. Мы покажем, что редуцированная упорядоченная парная группа, порожденная группой Sp, как раз и является требуемой группой конфигураций. [12]
В частности, доказуемая строгая эквивалентность сильнее, чем обычная строгая эквивалентность, так как в противовес утверждению 4.1 ( е) механизм теорем перечисления, заложенный в формальной системе, позволяет построить процедуру частичного разрешения для отношения Р D. [13]
Самодополнительные графы с 4 и 5 вершинами показаны на рис. 2.13. Результат Рида [3] для числа sp самодополнительных графов с р вершинами можно вывести из теоремы перечисления степенной группы. [14]
 |
Три различные суперпозиции. [15] |
Страницы: 1 2 3