Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки (1127096), страница 10
Текст из файла (страница 10)
Примеры иеориентированных графов приведены на рис. 19. Последовательность ребер графа, в которой'любые два соседние 53 ребра имеют общую вершину, называются путем в графе. Граф связан, если любые две вершины этого графа соединены по крайней мере одним путем. Пы рассматриваем графы без петель, т. е. без ребер, которые начинаются и заканчиваются в одной вершине. Такой граф называется деревом, если в нем нет замкнутых путей. Деревом является, например, граф, изображенный на рис.
19б, а графы 19а, в-деревьями не являются. Пусть ҄— множество всех транспозиций из 3„. Каждая транспозиция (1, 1) ен Т„ †э перестановка, оставляющая на месте все элементы множества (1, 2, ..., п), кроме чисел 1, 1, которые она переставляет. Поэтому первый элемент такой пары может быть любым из чисел 1, 2,... ..., и, а второй — любым отличным от первого.
Итак, имеется ровно п возможностей для выбора первого элемента пары, определяющей транспозицию, и, при каждом фиксированном выборе первого элемента, и — 1 возможность для выбора второго. Таким образом, можно построить п (п — 1) различных пар (1, /), определяющих транспозиции. Однако пары (1, /) и (1, 1), (чь/, определяют одну и ту же транспозицию, т. е, ( Т )= а(п — 1)/2.
Рис, 19 Пусть А — некоторое множество транспозиций из 5„', т. е. А с: Т„. По множеству А строится неориентированный граф, вершины которого обозначены числами 1, 2, ... ..., и, причем вершины 1, / соединены ребром тогда и только тогда, когда транспозицня (1, 1) принадлежит множеству А. Например, множеству транспозиций (1, 2), (2, 3), (2, 5), (3, 5), (4, 5) соответствует граф, изображенный на рис. 19а, а множеству (1, 2), (1, 3), (2, 3), (4, 5) — граф, изображенный на рис, 19в. Граф, построенный по некоторому множеству А транспозиций, часто называют графом Пойа этого множества.
Множества транс- позиций, являющиеся системами образующих симметрической группы (приводимыми или нет), выделяются по 54 свойствам своих графов Пойа. Прежде чем сформулировать теорему, характеризующую системы образующих транспозиций для симметрических групп, докажем одно вспомогательное утверждение, усиливающее равенство (3). Лемма. Для произвольной последовательности 1», 1»,... ..., 1» различных натуральных чисел, таких, что 1» — — Е, 1»=1, имеет место следующее разложение транспозиции (Е, 1): (Е', 1) =(Е, 1») ° (1, 1») .... (1 ьм 1) ° (1»-м 1 — ) ... ° (Е, Е). (4) Доказательство. Как и при проверке равенства (3), покажем, что перестановки из правой и левой частей равенства (4) действуют на любой элемент множества М одинаково.
Пусть 6;=(1; м 1;). Тогда (1)6»=1м (1»)б»=1» и т. д. На й-м шаге получим (1,,)6„=1. Действуя на элемент 1 любой из транспозиций б„м 6» „..., б„получим тот же элемент. Таким образом, перестановка, стоящая в правой части равенства (4), элемент Е переводит в элемент 1. Для элемента 1' получаем равенства (1)6,= =1, ..., (1)6»,=1, (1)6»=1, „(1„,)6,,=1» „..., (1,)6,=1, т. е. элемент 1 этой подстановкой переводится в Е.
Пусть теперь г ~ Е, 1. Транспозиция (Е, Е) оставляет элемент г на месте. Если г ф (1„ 1,, ..., 1»), то все транепозиции 6; (1(1(й) также оставляют г на месте и, следовательно, этот элемент является неподвижной точкой для перестановки из правой части (4). Если г совпадает с каким-то элементом Е„вФО,. й, то имеем следующие -равенства: (1,)6»=1„..., (1)6 1=1„(1,)6,=1» (1»)б„» — — 1, ь ...
(Ею-»)6.=(ю, (Ех)6,-»=1„..., (1,)6,=1„т. е, за~мент 1, является неподвижной точкой подстановки правой части из (4). Лемма доказана. Теорема. Множество транспозиций будет системой образующих симметрической группы б„тогда и только тогда, когда граф Пойа этого множества связан. Система образующих симметрической группы будет неприводимой тогда и только тогда, когда граф Лойп этой системы является деревом. Доказательство.
Пусть А — множество транспозиций, граф Пойа которого является связным, т. е. для произвольных вершин Е, 1 этого графа (1(Е, Е=-п, 1 ~1) существует путь, соединяющий зти вершины. Пусть 1»=1, 1,, ..., 1» „1»=1' — последовательность вершин, встречающихся вдоль этого пути при прохождении от вершины 1 к вершине 1. Согласно определению графа Пойа, подмножество А содержит транспозиции (Е, 1,), (Ем 1»), ° ~ (1»-» 1). 55 Но тогда, по доказанной выше лемме, транспозиция (1, /) раскладывается в произведение этих транспозиций из А. Поскольку вершины 1, 1 выбраны произвольно, отсюда получаем, что любая транспозиция из Т„ раскладывается в произведение транспозиций из А.
Так как Т„ порождает 5„, то А является системой образующих этой группы. Предположим теперь, что граф Пойа множества А не- связан. Тогда его можно разбить на связные части, т. е. выделить подмножества таких вершин, которые в этом графе связаны между собой, а вершины из различных подмножеств между собой никак не связаны.
Множество М можно представить как объединение попарно не пересекающихся частей: М=М,ОМ,()... () М„ причем в множество А входят лишь такие транспозицнн (1, 1), для которых при некотором /г элементы 1, 1 одно. временно содержатся в Мл. Поэтому множество А можно разбить на г подмно>кеств А„А„..., А, (некоторые из которых могут быть пустыми), включая в подмножество А,, те и только те транспозиции (1, 1), для которых 1, 1~ Мм Произведение транспозиций из множества А„(1 ( й ( г)— это некоторая перестановка на множестве М, подвижные точки которой принадлежат М».
Так как М„М„..., М, попарно не пересекаются, то при любых 1, 1, 1Ф1, перестановки, порождаемые транспозициями из А; и А~, яв.ляются взаимно простыми. Итак, любую перестановку ср, которая раскладывается в произведение транспозиций из множества А, можно разложить в произведение Ф=Ф~ Ч>а" ° "<~~ перестановок ~„рм ..., ~р„, подвижные точки которых содержатся соответственно в множествах М,, М„..., М,. Поскольку произвольную перестановку из 5„(например, цикл длины а) в таком виде записать нельзя, множество А транспозиций системой образующих З„не является.
Каждый граф, являющийся деревом, будет связным. Поэтому множество транспозицнй А, граф Пойа которого является деревом, будет системой образующих группы 5„. Поскольку при выбрасывании из дерева любого йебра его связность нарушается, такое множество транспозицнй А является непрнводнмой системой образующих симметрической группы. С другой стороны, если граф Пойа множества транс- позиций А деревом не является, то в нем можно выбрать 56 последовательность 1«, 1„..., 1», 1»+,-— 1«вершин так, что соединяющие их ребра образуют замкнутый путь.
Транс- позиции (1», 1,), (1„1,), ..., (1» „1,), (1„1,) содержатся в множестве А по определению графа Пойа. Поскольку числа 1«, 1ь..., 1» удовлетворяют условиям леммы, транс. позиция (1„1,) раскладывается в произведение остальных транспозиций этой последовательности. Следовательно, ее можно убрать из множества А, и оставшееся множество траиспозиций будет системой образующих 5„. Таким образом, множество А неприводимой системой образующих группы Я„не является. Теорема полностью доказана. 2 Ю Ф ау и Рис. 20 Неприводимые системы образующих, целиком состоящие из транспозиций, называют базисами симметрической группы 5„. Поскольку графы Пойа систем 1 и П, приведенных на с.
52, являются деревьями, (рис. 20), то эти системы неприводимы. По виду графов Пойа базис! называется линейным базисом, а базис П вЂ” звездообразным. Оба .эти базиса состоят из и — 1 транспозиции. Зто неслучайно. Покажем, что любое дерево с а вершинами содержит и — 1 ребро.
Воспользуемся методом математической индукции по числу а. Случай и = 2 — база индукции. В этом случае имеется лишь одно дерево, и оно имеет одно ребро. Предположим, что лкбэе дерево с й(п вершинами содержит й — ! ребро, и рассмотрим произвольное дерево с и вершинами. В любом'дереве имеется по крайней мере одна «висячая» вершина, т. е. такая, которая соединена ребром только с одной вершиной дерева.
(Если в конечном графе нет «висячих» вершин, то в нем обязательно есть замкнутые пути.) Удалим из дерева 'эту вершину и ребро, из нее выходящее. Получим снова связный граф, являющийся деревом. Поскольку число вершин этого графа равно и — 1, к нему применимо предположение индукции, т. е. он содержит и — 2 ребра.
Следовательно, исходное дерево содержит н — 1 ребро. Из этого простого утверждения получаем следующий важный вывод о базисах симметри- 57 ческой группы Я„'. все базисы симметрической группы Я„ равномощны и состоят из а — 1 транспозиции. Известна формула, принадлежащая А. Кэли '), для числа различных деревьев с п вершинами и, следовательно, для числа различных базисов симметрической группы Я„, Это число очень быстро растет с ростом п, т. е. при больших л в Я„имеется очень много неприводимых систем образующих (см. упражнения].
Упражнения 1. Доказать, что все перестановки из симметрической группы Я, можно расположить в такую последовательность, что: а) все члены этой последовательности различны; б) при любом (= 2, 3, ..., п( г-й член последовательностг. получается из (( — 1)-го ее члена умножением иа некоторую транспозицню. 2. Системою образующих полугруппы Р (М) всех преобразований множества М назовем такое множество А преобразований, что любой элемент из Р(М) можно разложить в произведение преобразований нз А.
Пусть А' — некоторая система образующих симметрической группы 3 (М). Тогда множество А' О (и), где (1 2 3 4 ... п) является системой образующих полугруппы Р (М). Доказать это. 3. Разложить перестановки (1 2 3 4 5 6 7 81 (1 2 3 4 5 6 7( (3 2 4 7 5 6 1 8) ' ) (7 6 2 1 4 3 5! ' (5 1 3 2 6 4) в произведение элементов каждой из систем образующих вида !, П, !П (с. 52) групп 5з, 5г и 5а соответственно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
