Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки (1127096), страница 7
Текст из файла (страница 7)
Убедимся, например, что б — группа. Поскольку все клетки первой из отмеченных таблиц заполнены только символами а„ а,, а„ множество б замкнуто относительно умножения заданных перестановок. Условие ассоциативности для умножения элементов из б выполняется автоматически, потому что оно выполняется для умножения произвольных преобразований. Перестановка ас является нейтральным элементом группы. Из таблицы также видно, что каждый нз элементов аь сс„сса имеет обратный, а именно а,'=ас, а,'=ам а '=а .
~ 36 Упражнения 1. Образуют ли полугруппы такие множества с заданными на них операциями: а) множество натуральных чисел с операцией, которая кюкдой паре чисел ставит в соответствие их наибольший общий делитель; б) множество всех многочленов произвольной ненулевой степени для суперпозиция многочленов; в) множество нечетных целых чисел для операции умножения? 2. Являются ли группами такие множества с заданными на ния операциями: а) множество действительных чисел для операции умножения; б) совокупность функций у=х, у= — х, у= !/х, у= — 1/х, определенных на множестве действительных чисел без нуля, для супер. позиции функций; в) множество функций у=х, у= — х для суперпозиции функций; г) множества с операциями из упражнения 1? 3.
Доказать, что в каждом ряду и в каждом столбце таблицы умножения для группы перестановок обозначение каждой из перестановок встречается точно два раза. 4. Какое свойство таблиц умножения абелевой группы не имеет места для таблиц умножения неабелевых групп? 5. Составить таблицу умножения; а) для гррппы 5 (М), где М=(1, 2, 3); б) для группы из упражнения 2, б); в) для полугруппы Р(М), где М=(1, 2). 6.
Сколько можно составить разных таблиц умножения для четырехэлементного множества перестановок, которые были бы таблицамн группы? 5 5. ГРАФЫ ПРЕОБРАЗОВАНИЙ. ОРБИТЫ; ЦИКЛИЧЕСКАЯ ФОРМА ЗАПИСИ ПЕРЕСТАНОВОК Стрелочные схемы — графы преобразований заданного множества — можно строить иначе, чем схемы произвольных отображений. Обозначим каждый элемент множества М точкой на плоскости так, чтобы разным элементам отвечалн разные точки. Точки обозначим теми же самыми символами, что и соответствующие элементы множества М. Две точки ° соединим стрелкой в направлении от а к Ь тогда и только тогда, когда длн элементов 'а, Ь выполняется условие (а)гр=Ь.
Так получим граф преобразоеания гр. Ясно, что он определяет преобразование однозначно. Наоборот, если не обращать внимание на форму стрелок и размещение точек на плоскости, то каждому преобразованию будет отвечать вполне определенный граф.
4 Примеры. 1. Пусть преобразование р множества М =(1, 2, 3, 4, б, 61 задано таблицей /1 2 3 4 5 6) 13 4 2 5 6 2/' 37 Обозначим каждое число из М точкой на плоскости, например, так, как на рнс. 9. Поскольку (1)~Р=З, точки ! н 3 соединим стрелкой в направлении от точки! к точке 3. Аналогично построим стрелки, которые выходят из точек 2, 3, 4, Ю, б (рис. 10). Это и есть граф преобразования <р. 2. Пусть ~р = е — тождественное преобразование множества М=(1, 2, 3, ..., л). По определению, для каждого а~М (а)е=а. Так что граф преобразования е будет такой, как на рис. !1. 3ч КФ Хи'« Рис. 9 Рис.
1О 3. Пусть ~р = ф, — постоянное преобразование множества М=(1, 2, ..., л), которое каждому элементу ЬенМ ставит в соответствие фиксированный элемент а ен М, т. е. для каждого Ьен М имеем (Ь)ф, = а. В этом случае на графе преобразования ~р каждая точка Ь соединена с фиксированной точкой а стрелкой, которая заканчивается в а (рис. 12). 4. Пусть М = Х, ~Р— преобразование множества Х, которое каждому целому числу х ставит в соответствие число х+3: (х)~р=х+3.
В этом у случае граф преобразования х полностью построить не удается, но можно изобразить определенную часть его так, чтобы стало а «-~ понятным строение графа в ° . ~ целом (рис. 13), ьа+У 5. Если М вЂ” конечное мноРис. 12 жество и преобразование ~р яв- ляется перестановкой на множестве М, то из каждой вершины графа ~р выходит одна и только одна стрелка и в каждую вершину обязательно входит стрелка, причем только одна. за В частности, если М = «1, 2, 3, 4, 6, 6, 7«и !р — перестановка на множестве М: (! 2 3 4 б б 7! (2 4 1 3 б б 7!' то ее граф будет такой, как на рис.
14. 9 Граф произвольного преобразования <р состоит из одной (рнс. 10,,12) или нескольких (рис. 14) не связанных между собой частей, каждая из которых составляет одно целое." При этом отдельная связная часть графа преобразования <р может состоять лишь из одной точки с <петлей», т. е. со стрелкой, которая выходит из этой точки Х Л д 4 д д 7 д д Рис. !3 и заканчивается в ней. Если а — такая точка, то для соответствующего элемента а ен М справедливо равенство (а) !р = а. Такие элементы называются неподвижными точками преобразования <р. Если для элемента а ~ М выполняется условие (а)~р Ф а, то а называется подвижной »почкой преобразования <р.
На графе подвижные точки— это точки без петель. Например, на рис. 14 точки 1,2, д, 4,5, б — под- д ~~- ~д внжные, а точка 7 — неподвижная точка преобразования «р. Количество подвижных точек преобразования является одной из важных его характеристик, которая называется апепенкю этого преобразования.
Единственным преобразованием степени нуль является тождественное преобразование; постоянное преобразование множества из и элементов имеет степень и — 1. Пусть ~р — некоторое преобразование множества М н а — произвольный элемент из М. Последовательность а»=а, (а)!р=ам (а»)~р=а„..., (а„)<р=а„+ь " (1) 39 элементов из М называется орбитой элемента а для преобразования ор. В общем случае множество О (а, Ч~) = = (ао, а„..., а„, ...» элементов орбиты (1) является подмножеством множества М.
В частности, может случиться, что 0(а, ф) =М. Рассмотрим детально строение орбит, когда М вЂ” конечное множество, 0(а, <р)=М и ~М~=т. Очевидно, в этом случае элементы в последоиательности (!), начиная с некоторого места, будут повторяться. Пусть я — наименьшее число такое, что (ао)ф = ао, 1( й. Ясно, что элементы аооь алло, ... также встречаются среди элементов ао, а„а„..., ао.
Поэтому и=т — 1 и легко понять, что граф преобразования ~р будет такой, как на рис. 15. Если 1~ О, преобразование р не является перестановкой, потому что в точке а, заканчиваются две стрелки. Для 1 = 0 преобразование имеет граф, который называется циклом (рис. 1б), и в этом случае оно, очевидно, будет перестановкой. Эта перестановка действует на элементы из М так: (ао)% =а„(ао)~р = а„..., (а о)~р = а „(а -о)~р = а,. Такая перестановка называется циклической или просто циклом и обозначается ~р=(ао, ам ао, .', а,). Число т есть длина цикла. Циклы длины 2 называются транслозиииями. Если элементы орбиты 0(а, ср) не исчерпывают все множество М, то графы (рис.
15, 16) не полностью характеризуют преобразование. Тогда нужно рассмотреть орбиты других элементов, которые не вошли в 0(а, ч). Разные орбиты для заданного преобразования могут иметь общие вершины (рис. 12), но для перестановки разные орбиты очерчивают не связанные части ее графа. Действительно, пусть От=(аь ао, ..., а„» и Оо= = (Ьь до, . д„» — разные орбиты перестановки <р. Допустим, что Оо и Оо имеют общие элементы. Идя в порядке возрастания номеров, выберем первый элемент ао ы О„который равняется определенному элементу д~е:-Оо.
Тогда ао,~)ь-ь Значит, (ао,)р=ао=(ь=(д1-о)ор и преобразование ср не является перестановкой. Мы 40 пришли к противоречию, которое и доказывает 'сформулированное утверждение. Теперь можно подробнее охарактеризовать графы пере. становок на конечном множестве М. В этом случае множество М распадается на отдельные части без общих элементов. На каждой из этих частей перестановка ф сбразует цикл. Поэтому граф каждой перестановки состоит из определенного числа не связанных между собой циклов.
Поскольку граф перестановки распадается на отдельные, не связанные между собой циклы, перестановки на конечном множестве удобно записывать так, чгобы по этой записи сразу же можно было строить отдельные части графа — циклы. Соответствующая запись перестановок называется циклической. Прежде чем рассказать про такую форму записи перестановок, сделаем несколько' сбщих замечаний. «НХ «Нв «1+а «Д «ге «1 «, «„4 Рис.
16 Рис. 15 Пусть ф — произвольная перестановка на множестве М и Р— такое подмножество множества М, что для каждого элемента а ен Р имеем (а)ф я Р. По перестановке ф на множестве М можно определить преобразование ф на множестве Р, положив для каждого ЬяР (ЬИ-(Ь)ф. Ясно, что !Р является перестановкой на Р. Будем называть ее ограничением перестановки ф на подмножество Р множества М. 4 Пр имер 6. Пусть М=11, 2, 3, 4, 6, 6), Р=(1; 2, 3, 41, 1 2 3 4 5 5 (4 3 2 1 б 5)' Непосредственно видно, что (а)ф вн Р для каждого а~Р, поэтому можно рассмотреть ограничение ф на Р. 41 Э то будет перестановка 14 3 2 !)' Обратно, если имеем перестановку !р' на множестве Р с: М, то можно определить перестановку ф на множестве М, положив для каждого элемента аенМ: (а)ф, если а ен Р, (а)ф = а, если а ер.
Р. То есть на элементы из Р перестановка ф действует так же, как перестановка ф, а все остальные элементы из М оставляет на месте. Будем называть перестановку ф расширением перестановки ф на множество М. 4 Пример 7. Пусть Р = [1, 2, 3, 4, 5<, М = <1, 2, 3, 4, 5, 6, 7, 8) (1 2 3 4 5) Тогда расширением ф на М является перестановка 7! 2 3 4 5 6 7 81 12 3 ! 5 4 6 7 8)' Назовем две перестановки на множестве М взаимно простыми, если их множества подвижных точек не имек!г общих элементов. Взаимно простыми будут, например, перестановки /! 2 3 4 5 б 7 81 7! 2 3 4 5 б 7 81 (3 4 2 ! 5 6 7 8!' т 1! 2 3 4 5 7 б 8/' ибо множеством подвижных точек для р является (1, 2, 3, 4), для ф — <6, 7).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
