Упражнения

1. Доказать, что все перестановки из симметрической группы можно расположить в такую последовательность, что:

а) все члены этой последовательности различны;

б) при любом член последовательности получается из ее члена умножением на некоторую транспозицию.

2. Системой, образующих полугруппы Р(М) всех преобразований множества М назовем такое множество А преобразований, что любой элемент из Р(М) можно разложить в произведение преобразований из А. Пусть А — некоторая система образующих симметрической группы S (М). Тогда множество , где

является системой ббразукщих полугруппы Р(М). Доказать это.

3. Разложить перестановки

в произведение элементов каждой из систем образующих вида I, II, III (с. 52) групп соответственно.

4. Нужно соединить городов автомобильными дорогами так, чтобы из одного города всегда можно было проехать в другой. Какое наименьшее число дорог надо построить?

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

6. Пусть - дерево с множеством вершин . Обозначим через висячую вершину дерева D, которая первой встретится в списке , а через — вершину, которая соединена ребром с Выбрасывая из дерева D вершину и ребро, соединяющее вершины получим дерево по которому аналогично определяются вершины Продолжая этот процесс шага, получим последовательность вершин дерева D. Доказать, что набор однозначно определяет дерево D.

7. Используя упражнение 6, доказать, что существует в точности различных деревьев с вершинами (а следовательно, и базисов транспозиций).

8. Нужно соединить городов линиями электропередач так, чтобы не строить лишних линий. Сколькими способами можно построить такую систему энергоснабжения?

9. Будет ли системой образующих симметрической группы совокупность транспозиций вида , где пробегает все нечетные числа от 1 до Если да, то будет ли эта система неприводимой?

10. Порождает ли система транспозиций вида симметрическую группу

11. Каждое подмножество из состоящее больше чем из перестановок порождает . Доказать это.

12. Доказать, что все циклы длины 3 вместе с какой-нибудь транспозицией являются системой образующих симметрической группы