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

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

Z(A + B) = Z(A)Z(B),

Где d (r, s) и m (r, s) обозначают соответственно наибольший общий делитель и наименьшее общее кратное чисел г и s;

Z(A[B])=Z(A)[Z(B)],

где ( и

- известная теоретико-числовая функция. [2]

.3 Решения задач

Задание 1

Пусть G - множество всех подстановок граней тетраэдра, которые могут быть получены его вращениями. Найти цикловой индекс группы G.

Решение:

PG=( +8x1x3 + 3)/12. Здесь можно воспользоваться тем, что двойственным к тетраэдру правильным многогранником является сам тетраэдр.

Задание 2

Пусть G -множество тех подстановок вершин куба, которые могут быть получены его вращениями. Найти цикловой индекс группы G.

Решение:

вращения куба можно разбить на пять частей:

) тождественное;

) 3 поворота на 180 вокруг прямых, соединяющих центры противоположных граней;

) 6 поворотов на 90° вокруг прямых, соединяющих центры противоположных граней;

) 6 поворотов на 180° вокруг прямых, соединяющих середины противоположных ребер;

) 8 поворотов на 120° вокруг прямых, соединяющих противоположные вершины.

Подстановка 1) дает 8 циклов длины 1. Подстановка 2) дает 4 цикла длины 2. Подстановка типа 3) дает 2 цикла длины 4. Подста- новка типа 4) дает 4 цикла длины 2. Подстановка типа 5) дает 2 цикла длины 1 и 2 цикла длины 3. Поэтому

Задание 3

Доказать, что цикловой индекс симметрической группы Sn равен коэффициенту при zn в разложении

exp {zx1 + z2x2/2 + z3x3/3 + ...}.

Решение

ехр(zx1+ =Коэффициент при zn получается суммированием выражений по всевозможным целым неотрицательным числам b1, b2, ... , удовлетворяющим условию b1+2b2+3b3+…=n. [4] Заключение В работе рассмотрены основное понятие графа - совокупность конечного числа точек (вершины) и попарно соединяющих некоторые из этих вершин линий (ребра или дуги графа). Были решены задачи с использованием графов, приведены примеры различных задач из других областей науки и техники. Список используемой литературы1. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. - М.: ВШ, 1976. с 9-18, 239-243, 245-248.

. Харари Ф. Теория графов. - М.: Мир, 1973. с 21-26, 211-216.

. Калужнин Л.А., Сущанский В.И. Преобразования и перестановки. - М.: Наука, 1985. с 50-63, 81-85

. Комбинаторный анализ. Задачи и упражнения. - М.: Наука, 1982.

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