Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки (1127096), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

4. Нужно соединить л городов автомобильными дорогами так, чтобы из одного города всегда можно было проехать в другой. Какое наименьшее число дорог нздо построить? 5. Доказать, что связный граф является деревом тогда и только тогда, когда в нем для любых двух вершин существует единственный путь, соединяющий этн вершины. 6. Пусть Π— дерево с множеством вершин 1, 2, ..., л. Обозначим порез Ь, висячую вершину дерева О, которая первой встретится в списке 1, 2, ..., и, а через а,— вершину, которая соединена ребром с Ь,.

Выбрасывая из дерева О вершину Ь, и ребро, соединяющее вершины Ьз и а,, получим дерево Ом по которочу аналогично определяются вершины Ь, и а,. Продолжая этот процесс п — 2 шага, по. лучим последовательность вершин аь аз, ..., а„з дерева О, Дока. зать, что набор и (О)= [а,, а„ ..., а„,) однозначно определяет дерево О. ') А.

К э л и (!821 †18) †английск математик, получивший фундаментальные результаты по различным разделам алгебры и комбинаторики, 58 7. Используя упражнение 6, доказать, что существует в точности лч-з различных деревьев с л вершинами (а следовательно, и базисов транспозиций). а. Нужно соединить л городов линиями электропередач так, чтобы не строить лишних линий.

Сколькими способами можно построить такую систему энергоснабжения? 9. Будет ли системой образующих симметрической группы бзл г совокупность транспозицнй вида (К а+1), (й, й-,'-2), где й пробегает все нечетные числа от 1 до 2л — 3? Если да, то будет ли эта система неприводимой? 10. Порождает ли система зл транспозиций вида (1+31, 1+31+1), (1+31, 1+3!+2), (1+31, 1+3(1+1)) (1=О, 1, ..., л — 1) симметрическую группу Зз„„д? !1.

Каждое подмножество из Бю состоящее больше чем из л!?2 перестановок порождает 3„. Доказать это. 12. Доказать, что все цинлы длины 3 вместе с кахой-нибудь транспозицией являются системой образующих симметрической группы 5а. ф а. пОдГРуппы симметРичесКих ГРупп. ГРУППЫ ПЕРЕСТАНОВОК Некоторые множества перестановок из симметрической группы Я„сами могут образовывать группу относительно умножения перестановок. Определение. Подмножество Т множества Я„называется подгруппой группы 5„, если оно образует группу относительно операции умножения перестановок. В частности, само множество 5„также является своей подгруппой, которую называют несобственной. С другой стороны, множество Е„, состоящее из одной тождественной перестановки а, также является подгруппой группы 5„, как зто следует из равенства а ° в=а, е-'=а, Подгруппа Е„называется тривиальной подгруппой симметрической группы 5„.

Все подгруппы из 5„, отличные от 5„, называются собстаенныжи подгриапами. Следовательно, для собственной нетривиальной подгруппы 6 из 5„ выполнено неравенство ! <(6)<ц! Для любой подгруппы из 5„выполняются требования а) — г) из определения группы. Однако, проверяя будет ли данное подмножество из 5„ подгруппой, нет необходимости устанавливать для него истинность всех свойств а) — г). Имеет место следующая 39 Т е о р е м а. Непустое подмножество Т симмепгрической группы 5„образует подгруппу тогда и только тогда, когда выполнены следующие условия: 1) произведение а ° б любых двух перестановок а, )) из Т тоже содержится в Т (Т замкнуто относительно опера.

ции умножения перестановок); 2) если а ~ Т, то а-' ~ Т (Т замкнуто относительно перехода к обратной перестановке). Дока зател ьст в о. Согласно определению, произвольная подгруппа Т группы 5„замкнута относительно операции умножения перестановок и относительно перехода к обратной перестановке. Тем самым, условие теоремы является необходимым.

Покажем, что оно н достаточно. Пусть для некоторого непустого множества Т перестановок из 5„выполнены условия теоремы 1) и 2). Условие 1) означает, что для множества Т выполнено первое требование определения группы. Операция умножения перестановок из Т ассоциативна, поскольку умножение произвольных перестановок, а следовательно, и тех, которые принадлежат Т, подчиняется ассоциативному закону.

Итак, для множества Т и операции умножения перестановок выполнено второе требование определения группы, Далее, поскольку Т~ ф, то существует по крайней мере одна перестановка я, принадлежащая Т. По условию 2) теоремы отсюда имеем, что обратная перестановка а-' тоже принадлежит Т. Следовательно, по условию 1) перестановка а я-'= е содержится в Т, т.

е. выполнено третье из требований определения группы. Наконец, условие 2) показывает, что каждый элемент из Т имеет обратный, который также принадлежит Т. Таким образом, Т является подгруппой симметрической группы 5.. 4 Примеры. 1. Пусть Н вЂ” множество перестановок из симметрической группы 54.' 13 4 1 2)' У 14 3 2 1)' Проверим, является ли Н подгруппой группы 5,. Имеем а-'=я, р-'=р, у-'=у, следовательно, для множества Н выполняется условие 2) только что доказанной теоремы. Кроме того, я ° р=() а=у, а у=у а=р, р а=у ()=а, а а=яе=е', р ° р=(1'=е, у у=у'=а (проверьте!). Следовательно, произведение каждых двух элементов множества Н является элементом того же мно- жества, т. е.

для Н выполняется и условие 1) упомяну- той' теоремы. Из записанных нами равенств вытекает, что группа Н абелева. 2. Пусть б — множество перестановок (3 ! 2 3 4) ' (3 4 3 1 2) ' Тогда а-'= 6, ~-' у, 6-' =а, у-'= р; следовательно, выполняется условие 2) теоремы о подгруппах группы 5,. Кроме того, выполняются равенства а р=р а=у, р ° у=у ° р=е, а'=)), 64= у а.у = у ° а = 6, )) . 6 = 6.

)) = а, р4 = 6, уе =. а а ° 6=6 а=е, у ° 6=6 ° у='1! !проверьте!). Как видим, произведение каждых двух эле- ментов множества б является элементом из б, следова- тельно, выполняется и условие 1). Поэтому множество б является подгруппой группы 5„причем из приведенных равенств вытекает, что группа 0 абелева. 3. Пусть Т вЂ” множество перестановок (3 ! 2 4)' У (2 4 ! 3)' Зто множество не является подгруппой группы 54, так как для него не выполняется ни одно из условий 1), 2). Действительно, (3 ! 4 2) ~ ' У (4 ! 2 3) ~ Симметрическая группа 5„имеет много разных под- групп, причем их число очень быстро возрастает с увели- чением числа и.

Ряд примеров мы приведем в следующем параграфе. Полностью описать все подгруппы группы 5„удается лишь для небольших и, а для и больших изучаются лишь общие свойства таких подгрупп. 3 ад а ч а. Описать все подгруппы симметрической группы 54. 61 Решение.

1) Опишем сначала подгруппы, которые состоят из двух элементов. Если Н вЂ” такая подгруппа, то в нее входит элемент е и еще какой-то другой элемент а. Элемент, обратный к а, не может совпадать с е, поэтому сг'=и. Последнее равенство можно записать так: а'=е. Следовательно, а — перестановка второго порядка, т. е.

цикл длины 2. Таким образом, существует не больше трех подгрупп второго порядка группы 5,. Это такие подмножества множества Яз' А = (е, (1, 2)), В = (е, (2, 3)), С = (з, (1, 3)) Теперь, пользуясь сформулированной выше теоремой, легко убедиться, что подмножества А, В, С действительно являются подгруппами, так как для каждого из них выполняются условия 1), 2) этой теоремы. 2) Опишем подгруппы, которые состоят из трех элементов. Если О = (е,а, й) †так подгруппа, то элементы а, р должны иметь порядок 3.

Действительно, если один из них, например а, имеет порядок 2, то а-' =а, и, поскольку каждый элемент имеет лишь один обратный, отсюда получаем, что и ~-' = )), т. е. рз= е. Но легко проверить непосредственно, что произведением любых двух элементов ~р, ф, ~р Фф второго порядка является элемент, который имеет порядок 3. Следовательно, при таких предположениях произведение а р не принадлежит О и О не есть подгруппа.

Рассмотрим теперь случай, когда перестановки а и р имеют порядок 3, т. е. О=(е, (1, 2, 3), (1, 3, 2)). Имеем а-'=р, )1-'=а, а р=р а=е, аз=р, р'=и, т. е. подмножество О множества 5, действительно является подгруппой группы Я,. Легко убедиться:непосредственно, что подмножества множества Вм состоящие из 4 или 5 элементов, подгрупп не образуют. Это непосредственно следует также из теоремы Лагранжа, которая будет рассмотрена в 3 11.

Итак, симметрчческая группа Яз содержит шесть подгрупп, учитывая саму группу Я, как свою несобственную подгруппу и тривиальную подгруппу Е,. При решении многих задач подгруппы симметрической группы 5„ появляются и исследуются независимо, т. е. тот факт, что они являются подгруппами 5„ существенной роли не играет — сама объемлющая группа в рассмотрениях не участвует. В таких ситуациях подгруппы симметрической группы Я„называются просто группами перестановок на множестве (1, 2, ..., и).

Группы перестановок 62 принято обозначать 'парами символов, одним из которых обозначается сама группа, а другим — множество, на котором действуют перестановки из этой группы. Для наиболее употребительных групп перестановок употребляются стандартные обозначения, некоторые нз которых будут приведены ниже. 4 Примеры. 4. Пусть М=(1, 2, 3, 4), К вЂ” множество перестановок Множество К образует группу относительно операции умножения перестановок. (Проверьте() Поэтому можно говорить о группе перестановок (К, М). Она называется четверной группой Клейна. 5.

Характеристики

Список файлов книги