Задачи о раскрасках

Рассмотрим две комбинаторные задачи на применение леммы Бернсайда.

Задача 1: Сколькими способами можно раскрасить вершины куба в три цвета (например, красный, синий и зеленый)?

Каждую из восьми вершин куба можно раскрасить тремя способами, причем независимо от того, как раскрашены другие вершины, то множество всех вершин куба можно раскрасить 3⁸ = 6561 различными способами. Однако при таком подходе к решению задачи молчаливо предполагается, что мы умеем различать вер­шины куба перед окраской, т. е., скажем, куб жестко закреплен или его вершины занумерованы. При этом по­лученный ответ можно интерпретировать следующим обра­зом: можно так раскрасить 3⁸ абсолютно одинаковых, жестко закрепленных кубов, что все они будут разли­чаться. Дли 3⁸+1 кубов этого сделать уже нельзя.

Естественно считать, что два куба раскрашены одинаково, если их раскраски совпадают после некоторого вращения одного из кубов в пространстве. Будем говорить, что такие раскраски кубов геометрически неотличимы. Поэтому естественным уточнением задачи о раскраске является следующая задача: Сколькими геометрически различными способами можно раскрасить вершины куба в три цвета.

Переформулируем теперь эту задачу так, чтобы стала понятной ее связь с леммой Бернсайда. Пусть М — мно­жество всевозможных по-разному раскрашенных кубов одного размера, положение которых в пространстве фикси­ровано, G —группа всех вращений куба, состоя­щая из 24 перестановок. Группа G естественным образом определяет группу перестановок на множестве М. Именно: если — некоторое вращение, то каждому кубу из М можно сопоставить некоторый, вообще говоря, другой куб. который получается из первого при вращении . Это соответствие является, очевидно, перестановкой на мно­жестве М, которую будем обозначать . Группу всех таких перестановок множества М. определяемых переста­новками из G, мы будем обозначать . Ясно, что .

То, что два куба и из М раскрашены геометриче­ски одинаково, означает, что один из них можно пере­вести вращением в такое положение, в котором они не­различимы. Иными словами, существует такая переста­новка , что , т. е. и содержатся в одной орбите группы , действующей на множестве М. Таким образом, для того чтобы определить число геоме­трически различимых способов раскраски вершин куба, нужно найти количество орбит группы на множестве М.

Считая вершины кубов занумерованными числами 1,2, 3, 4, 5, 6, 7, 8. раскраску каждого из 3⁸ кубов можно однозначно охарактеризовать «словом» из 8 букв, каждая из которых есть либо k, либо c, либо з. То, что i-ая буква слова равна к (или с, или з), означает, что i-ая вершина при выбранной нумерации окрашена в красный цвет (или в синий, или в зеленый соответственно). Например, для кубов, изображенных на рис. 5, имеем соответственно последовательности ссззсскк, ссссккзз. Перестановки из группы переставляют такие последовательности. Напри­мер, если , то перестановка слово сссссссзпереводит в ссссзссс, слово ссззссккперево­дит в сззссккс, слова сссссссс, кккккккк, зззззззз оставляет неизменными и т. д. Выписать всю таблицу значений для перестановки затруднительно, поскольку она состоит из 3⁸ строк.

Для того чтобы применить лемму Бернсайда, необхо­димо определить число неподвижных точек каждой пере­становки из . Последовательность букв к, с, з будет не­подвижной для перестановки тогда и только тогда, когда при разложении соответствующей перестановки в произведение циклов вершины куба, номера которых входит в один и тот же цикл, окрашены одним цветом. Например, если = (1, 2, 3, 4) (5, 6, 7, 8), то неподвиж­ными относительно будут слова, составленные целиком из одной буквы, и слова, составленные из двух разных букв, причем одна из них стоит на первых четырех мес­тах в слове, а вторая — из четырех последующих. Поэтому имеется 9 неподвижных точек перестановки на множе­стве М. Уже на этом примере видно, что подсчет числа неподвижных точек перестановок из сильно упрощается, если известны разложении в произведение циклов соот­ветствующих перестановок из G. Если перестановка разложена в произведение k-циклов, то число ее неподвижных точек равно . Поэтому сначала мы опишем разложения в произведение циклов для всех пере­становок из группы G вращений куба.

а) Вокруг каждой из трех осей, соединяющих центры противоположных граней, имеется три нетождественных вращения. Им соответствуют перестановки

б) Вокруг каждой из четырех диагоналей, т. е. осей, соединяющих противоположные вершины куба, имеется по два нетривиальных вращения. Им соответствуют пере­становки

в) Вокруг каждой из шести осей, соединяющих сере­дины противоположных ребер, имеется одно нетривиаль­ное вращение. Им соответствуют перестановки

Вместе с тождественной получаем 24 перестановки. Итак, в группе G вращений куба имеется

1 перестановка типа

6 перестановок типа

9 перестановок типа

8 перестановок типа

Перестановка первого типа имеет 3⁸ неподвижных точек, любая из перестановок второго типа – 3², третьего и четвертого типов – 3⁴ неподвижных точек. Поэтому согласно Лемме Бернсайда имеем

Таким образом, число геометрически различимых способов раскраски першим куба в три цвета равно 333.

Задача 2: Сколько различных ожерелий из семи бусин можно составить из бусин двух цветов — красного и синего?

Для того чтобы стала понятной аналогия этой задачи с предыдущей, переформулируем ее следующим равно­сильным образом:

Сколькими геометрически различными способами можно раскрасить вершины правильного семиугольника в два цвета?

Здесь два способа раскраски неотличимы, если один из них можно получить из другого, применяя к семи­угольнику либо преобразования вращения, либо симмет­рии относительно осей, т. е. перестановки из группы ди­эдра D₇. Если вершины семиугольника пронумерованы, имеется 2⁷=128 различных вариантов их раскраски, так как каждую вершину независимо от других можно рас­красить двумя способами.

Снова будем описывать раскраски словами длины 7, составленными из букв к (вершина окрашена в красный цвет) и с (вершина окрашена в синий цвет). На множе­стве N всех таких слов действует группа перестановок, задаваемых перестановками из D₇. Например, если (1, 2, 3, 4, 5, 6, 7), то перестановка последнюю букву каждого слова переставляет в его начало, а остальные буквы не изменяет. Для того чтобы определить число орбит группы , на множестве N, необходимо найти типы перестановок из D₇. Эта задача гораздо проще аналогич­ного вопроса для группы G из задачи 1. Группа D₇, состоит из 14 перестановок множества {1, 2, 3, 4, 5, б, 7}, которые распределены по возможным типам так:

1 перестановка имеет тип

6 перестановок имеют тип

7 перестановок имеют тип .

Слово неподвижно относительно перестановки , тогда и только тогда, когда буквы, стоящие на местах с номерами из одного цикла в перестановке , совпадают. Поэтому тождествен на я перестановка имеет 2⁷ неподвиж­ных точек на N, перестановки второго типа — по 2, а пе­рестановки третьего типа —по 2⁴. Применяя лемму Берн­сайда, получаем

Итак, из бусин двух цветов можно составить 18 семи-бусенных ожерелий.

Заключение

Целью данной курсовой работы является рассмотрение понятие групп, и изучения леммы Бернсайда, а также применения данной леммы для решения задач о раскрасках.

Группы повсеместно используются в математике и естественных науках, часто для обнаружения внутренней симметрии объектов. Внутренняя симметрия обычно связана с инвариантными свойствами; множество преобразований, которые сохраняют это свойство, вместе с операцией композиции, образуют группу, называемую группой симметрии.

В теории Галуа, которая и дала начало понятию группы, группы используются для описания симметрии уравнений, корнями которых являются корни некоторого полиномиального уравнения. Из-за важной роли, которую они играют в этой теории, получили своё название разрешимые группы.

Абелевы группы (т.е. группы, в которых операция коммутативна) являются основой для построения более сложных объектов абстрактной алгебры, таких как кольца, поля и модули.

Понимание теории групп также очень важно для физики и других естественных наук. В химии группы используются для классификации кристаллических решёток и симметрий молекул. В физике группы используются для описания симметрий, которым подчиняются физические законы. Особенно важны в физике представления групп, в частности, групп Ли, так как они часто указывают путь к «возможным» физическим теориям.

Литература

Богопольский О. В. «Введение в теорию групп» 2002г.

Калужнин Л.А., Сущанский В.И. «Преобразования и перестановки» 1985г.

Кострикин А.И. «Введение в алгебру» 1977г.

Поиск по сайту: