§ 5. ГРАФЫ ПРЕОБРАЗОВАНИЙ. ОРБИТЫ. ЦИКЛИЧЕСКАЯ ФОРМА ЗАПИСИ ПЕРЕСТАНОВОК

Стрелочные схемы — графы преобразований заданного множества — можно строить иначе, чем схемы произвольных отображений. Обозначим каждый элемент множества М точкой на плоскости так, чтобы разным элементам отвечали разные точки. Точки обозначим теми же самыми символами, что и соответствующие элементы множества М. Две точки - соединим стрелкой в направлении от а к b тогда и только тогда, когда для элементов а, b выполняется условие . Так получим граф преобразования Ясно, что он определяет преобразование однозначно. Наоборот, если не обращать внимание на форму стрелок и размещение точек на плоскости, то каждому преобразованию будет отвечать вполне определенный граф.

Примеры. 1. Пусть преобразование множества М = {1, 2, 3, 4, 5, 6} задано таблицей

Обозначим каждое число из М точкой на плоскости, например, так, как на рис. 9. Поскольку точки I и 3 соединим стрелкой в направлении от точки 1 к точке 3. Аналогично построим стрелки, которые выходят из точек 2, 3, 4, 5, 6 (рис. 10). Это и есть граф преобразования

2. Пусть — тождественное преобразование множества По определению, для каждого . Так что граф преобразования будет такой, как на рис. 11.

Рис. 9

Рис. 10

Рис. 11

Рис. 12

3. Пусть — постоянное преобразование множества , которое каждому элементу ЬМ ставит в соответствие фиксированный элемент т. е. для каждого ЬМ имеем

В этом случае на графе преобразования каждая точка b соединена с фиксированной точкой а стрелкой, которая заканчивается в а (рис. 12).

4. Пусть , — преобразование множества Z, которое каждому целому числу ставит в соответствие число . В этом случае граф преобразования полностью построить не удается, но можно изобразить определенную часть его так, чтобы стало понятным строение графа в целом (рис. 13).

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

В частности, если — перестановка на множестве М:

то ее граф будет такой, как на рис. 14.

Граф произвольного преобразования состоит из одной (рис. 10, 12) или нескольких (рис. 14) не связанных между собой частей, каждая из которых составляет одно целое. При этом отдельная связная часть графа преобразования может состоять лишь из одной точки с «петлей», т. е. со стрелкой, которая выходит из этой точки и заканчивается в ней.

Рис. 13

Если а — такая точка, то для соответствующего элемента справедливо равенство

Такие элементы называются неподвижными точками преобразования Если для элемента выполняется условие

то а называется подвижной точкой преобразования На графе подвижные точки — это точки без петель.

Рис. 14

Например, на рис. 14 точки 1, 2, 3, 4, 5, 6 — подвижные, а точка 7 — неподвижная точка преобразования

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

Пусть — некоторое преобразование множества М и а — произвольный элемент из М. Последовательность

элементов из М называется орбитой элемента а для преобразования .

В общем случае множество элементов орбиты (1) является подмножеством множества М. В частности, может случиться, что

Рассмотрим детально строение орбит, когда М — конечное множество, . Очевидно, в этом случае элементы в последовательности (1), начиная с некоторого места, будут повторяться. Пусть — наименьшее число такое, что

Ясно, что элементы также встречаются среди элементов . Поэтому и легко понять, что граф преобразования будет такой, как на рис. 15.

Если преобразование не является перестановкой, потому что в точке заканчиваются две стрелки. Для преобразование имеет граф, который называется циклом (рис. 16), и в этом случае оно, очевидно, будет перестановкой. Эта перестановка действует на элементы из М так:

Такая перестановка называется циклической или просто циклом и обозначается

Число есть длина цикла. Циклы длины 2 называются транспозициями.

Если элементы орбиты не исчерпывают все множество М, то графы (рис. 15, 16) не полностью характеризуют преобразование. Тогда нужно рассмотреть орбиты других элементов, которые не вошли в Разные орбиты для заданного преобразования могут иметь общие вершины (рис. 12), но для перестановки разные орбиты очерчивают не связанные части ее графа.

Действительно, пусть — разные орбиты перестановки Допустим, что имеют общие элементы. Идя в порядке возрастания номеров, выберем первый элемент который равняется определенному элементу . Тогда Значит, и преобразование не является перестановкой.

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

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

Рис. 15

Рис. 16

Пусть — произвольная перестановка на множестве М и Р — такое подмножество множества М, что для каждого элемента имеем

По перестановке на множестве М можно определить преобразование на множестве Р, положив для каждого

Ясно, что является перестановкой на Р. Будем называть ее ограничением перестановки на подмножество Р множества М.

Пример 6. Пусть

Непосредственно видно, что для каждого поэтому можно рассмотреть ограничение на Р.

Это будет перестановка

Обратно, если имеем перестановку на множестве , то можно определить перестановку на множестве М, положив для каждого элемента :

То есть на элементы из Р перестановка действует так же, как перестановка а все остальные элементы из М оставляет на месте. Будем называть перестановку расширением перестановки на множество М.

Пример 7. Пусть

и

Тогда расширением на М является перестановка

Назовем две перестановки на множестве М взаимно простыми, если их множества подвижных точек не имеюх общих элементов.

Взаимно простыми будут, например, перестановки

ибо множеством подвижных точек для является для

В отличие от перестановок общего вида, произведение взаимно простых перестановок не зависит от порядка множителей.

Действительно, пусть — взаимно простые перестановки и а — произвольный элемент множества М. Если а — подвижная точка для перестановки , то положим элементы а, b — неподвижные точки для ибо . Поэтому имеем

т. е. в этом случае

Если а — неподвижная точка перестановки то положим (если а является неподвижной точкой и для перестановки , то ) и аналогично получим, что элементы а, с не меняются под действием перестановки а поэтому

Так что и в этом случае перестановки действуют на элемент одинаково, а это и означает, что

Таблицу произведения двух взаимно простых перестановок составить очень просто. Для этого во втором ряду таблицы нужно записать на своих местах (т. е. на тех местах, на которых они стоят в таблицах для ) все подвижные точки перестановок , а остальные места заполнить неподвижными точками. Например,

Пусть теперь — произвольная перестановка на множестве М. Разобьем М на части каждая из которых является орбитой некоторого элемента из М. Это разбиение имеет такие свойства:

а) каждый элемент из М принадлежит одному из подмножеств

б) если то не имеют общих элементов;

в) для каждого ; (i есть один из номеров ) элемент также принадлежит

По последнему свойству можно рассмотреть ограничение перестановки на каждое из подмножеств М; есть, очевидно, циклическая перестановка на Она определяется перестановкой однозначно.

В свою очередь, каждую из перестановок можно расширить на все множество М. Обозначим это расширение через Далее такие перестановки также будем называть циклическими и обозначать их так, как и обычные циклы. Следовательно, перестановка будет циклической в этом понимании тогда и только тогда, когда она имеет граф такого вида, как на рис. 17.

Очевидно, множество подвижных точек каждой из перестановок совпадает с множеством по свойству в) перестановки взаимно просты. Пользуясь приведенным выше правилом для умножения взаимно простых перестановок, получаем

Поскольку перестановки — попарно взаимно простые, это произведение не зависит от порядка множителей. Таким образом, доказана такая

Теорема. Каждую перестановку на конечном множестве М можно разложить в произведение взаимно простых циклов, причем это разложение однозначно с точностью до порядка множителей.

Рис. 17

Набор чисел , являющихся длинами циклов, на которые разложена данная перестановка, называется ее типом и обозначается

Пример 8. Разложить в произведение циклов перестановку

Находим разные орбиты для Имеем

Так что орбиты определяют подмножества Ограничениями перестановки на эти множества будут такие перестановки:

Расширениями этих перестановок на множество М будут перестановки

Поэтому можно записать

Последняя запись однозначно определяет перестановку лишь тогда, когда известно, на каком множестве она действует.

Упражнения

1. Может ли произвольный граф быть графом какого-нибудь преобразования?

2. Перестановка задана графом, Как построить граф обратной перестановки?

3. Указать правило для нахождения графа произведения преобразований, каждое из которых задано своим графом, не строя таблиц этих преобразований.

4. Построить графы преобразований, заданных таблицами:

5. Каждая перестановка, граф которой связан, циклична, Доказать это.

6. Длиной орбиты называется число ее элементов. Найти наибольшее и наименьшее значения сумм длин разных орбит для преобразований множества из элементов.

7. Преобразование множества М будет перестановкой тогда и только тогда, когда сумма длин разных ее орбит равняется Доказать это.

8. Пусть — произвольное преобразование множества М. Существует такое множество и такое натуральное число к, что для каждого и ограничение на Р есть перестановка. Доказать это.

9. Разложить в произведение взаимно простых циклов и найти типы таких перестановок:

10. Описать общий вид графа про звольного преобразования (так, как это сделано для перестановок).

11. Сколько существует перестановок на множестве из элементов, которые имеют заданный тип (ясно, что ).

12. В группе найти число перестановок каждого возможного типа.

13. Определить тип перестановки, - характеризующей расположение тридцати физкультурников после двукратной перегруппировки (см, упражнение 12 § 3),