Степенная группа

Cтраница 3

Для обоснования соотношений (6.1.2) и (6.1.3) рассмотрим произвольную подстановку у ( а; Р) из степенной группы ВА. [31]

Для обоснования соотношений (6.1.2) и (6.1.3) рассмотрим произвольную подстановку у ( a; Р) из степенной группы ВА. [32]

Итак, эквивалентность орграфов относительно обращения соответствует эквивалентности функций из множества У 121, определяемой с помощью степенной группы В. [33]

Самообратные отношения на двух вершинах. [34]

Сколько орбит функций, отображающих множество из т элементов на множество из п элементов, определяются этими степенными группами. [35]

Другими словами, / - g означает, что функции / и g принадлежат одной и той же орбите степенной группы ЕА. [36]

Число самодополнительных орграфов. [37]

Существует много задач перечисления, в которых функциям назначаются полные веса так, что все функции одной и той же орбиты степенной группы имеют одинаковый вес. [38]

Графы с ребрами, окрашенными во взаимозаменяемые цвета. [39]

Отсюда следует, что производящая функция N ( х), которую мы ищем, получается с помощью применения соотношения (6.3.11) к нашей степенной группе ВА. [40]

Самодополнительные графы с 4 и 5 вершинами показаны на рис. 2.13. Результат Рида [3] для числа sp самодополнительных графов с р вершинами можно вывести из теоремы перечисления степенной группы. [41]

По аналогии с замечанием, приведенным после формулировки константной формы ТПСГ, обратим внимание на то, что форма степенного ряда ТПСГ включает в себя как существенную часть приложение теоремы Пойа к цикловому индексу степенной группы. [42]

Существует несколько очень полезных формул, позволяющих по цикловым индексам Z ( A) HZ ( В) групп А к В вычислять цикловые индексы суммы А В, произведения Ах В, композиции А [ В ] и степенной группы Вл. [43]

Таким образом, элементы 0 и 1 из множества Y используются для указания соответственно на существование или отсутствие ребра в графе. Рассмотрим степенную группу ВА, у которой А 5 ( P2) и В - Sz-Ясно, что графы, представимые двумя функциями, эквивалентны относительно дополнительности тогда и только тогда, когда эти две функции принадлежат одной и той же орбите рассматриваемой степенной группы ВА. Поэтому если подстановка ( а; ( 0) ( 1)) из этой группы преобразует функцию / в функцию g, то / и g представляют изоморфные графы. А если / преобразуется в g подстановкой ( а; ( О, 1)), то две функции представляют взаимно дополнительные графы. Следовательно, число ар р-вершинных графов, подсчитываемых с точностью до их взаимной дополнительности, равно числу орбит указанной выше степенной группы. [44]

Далее, пусть С ( х) - производящая функция для графов, имеющих в точности три компоненты, причем все компоненты в графе разные. Рассмотрим степенную группу Es с множеством объектов Yx. Более того, вес каждой орбиты равен порядку того графа, который соответствует этой орбите. [45]

Страницы: 1 2 3 4