Читать курсовая по математике: "Решения комбинаторных задач теории графов с помощью теоремы Пойа" Страница 7

(Назад) (Cкачать работу)

Теорема. Пусть А - группа подстановок, действующая на множестве X с орбитами Q1, Q2, …, Qn, и - функция, приписывающая веса каждой орбите (весовая функция). Более того,определяется на X так, что (x)= (i), если хi. Тогда сумма весов орбит равна: (1)

Доказательство

Мы уже видели, что порядок |А| группы A равен |А (х)|- | (х)| для любого х из X, где А(х) - стабилизатор элемента х. Кроме того, поскольку весовая функция постоянна на элементах данной орбиты, то

для каждой орбиты . Сопоставляя эти факты, находим, что

Суммируя по всем орбитам, имеем

откуда сразу следует (1).

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

Следствие (2) (лемма Бернсайда). Число N (А) орбит группы подстановок А равно

Все классические проблемы перечисления, к которым применяется теорема Пойа, имеют одну и ту же общую форму. Пусть дана область определения D, множество значений R и весовая функция , определенная на R. В качестве примера можно взять весовую функцию , приписывающую каждому rR упорядоченную пару (r) = (r,r) неотрицательных целых чисел. Объекты, подлежащие счету, - это функции, действующие из D в R. Для завершения постановки проблемы надо условиться о том, когда две функции из RD рассматриваются как неразличимые (эквивалентные). Это достигается указанием группы А, действующей на D; при этом две функции считаются эквивалентными, когда они принадлежат одной и той же орбите из ЕА, где Е - тождественная группа степени |R|.

Задержимся на минуту и проиллюстрируем эти идеи на «проблеме ожерелья». Рассмотрим ожерелья, скажем, с 4 бусинками, в которых одни бусинки красные, а другие синие. Два таких ожерелья считаются эквивалентными, если их можно сделать «конгруэнтными» с сохранением цветов бусинок. Здесь D - множество ячеек (мест), в которых могут находиться бусинки, R - множество {красная бусинка, синяя бусинка}, а функция f- приписывание бусинок каждому месту (каждый ячейке) на ожерелье. В этом примере группа А - диэдральная группа D4; весовую функциюможно определить равенствами(красная бусинка) (1, 0) и (синяя бусинка) = (0,1).

Следуя интуитивной терминологии Пойа, элементы области определения D будем называть местами, элементы множества значений - фигурами, функции - конфигурациями, а группу подстановок А-группой конфигураций. Припишем вес (f) каждой функции f RD:

Легко видеть, что все функции из данной орбиты множества RD, определяемой группой ЕА, имеют один и тот же вес, так что вес орбиты можно определить как вес любой функции из нее.

Предположим, имеются cmn фигур с весом (m, n) в R и Сmn орбит (эквивалентные классы конфигураций) с весом хmуn в RD. Перечисляющий ряд для фигур нумерует элементы из R, приписывая им веса, а перечисляющий ряд для конфигураций является производящей функцией для классов эквивалентности функций fRD. Теорема Пойа дает возможность выразить С(х, у) через с(х, у).

Если в (2) написать Z(A)=Z(A; a1, a2, …,ad), то для любой функции

h (х, у)Z(A,h (х, y))=Z (A; h (х, y),h(x2, у2), ..., h(xd, yd)). (3)

Теорема (теорема перечисления Пойа)

Перечисляющий ряд для

Похожие работы