алення збільшує число компонент.
Групи підстановок і їх циклової індекс.
Для вирішення завдань перерахування нам необхідно згадати деякий матеріал з теорії груп.
Безліч Г називається групою, якщо на ньому задана бінарна операція (·), що не виводить за межі множини і задовольняє таким трьом умовам:
. Для будь-яких x, y і z з Г справедливо (x · y) · z=x · (y · z);
. У Г існує одиничний елемент e, такий що для будь-якого x з Г e · x=x · e=x;
3.Для будь-якого елементу x з Г існує зворотний елемент також з безлічі Г, такий що.
Непорожнє підмножина A безлічі Г називають підгрупою групи Г, якщо воно задовольняє наступним двом умовам:
. Бінарна операція не виводить за межі підмножини A;
2.Для будь-якого елементу x з A зворотний до нього елемент також лежить в A.
Нехай A - деяка підгрупа групи Г. Правим класом суміжності групи Г по підгрупі A називається безліч виду Ax, де x - довільний елемент із Г (аналогічно визначаються ліві класи суміжності). Відомо також твердження про те, що якщо A - підгрупа групи Г, то групу Г можна розкласти в об'єднання правих (лівих) класів суміжності по підгрупі A.
Розглянемо тепер безліч. Підстановкою називається взаємно однозначне відображення. Множенням підстановок будемо називати їх композицію. Нехай A - деяка сукупність підстановок множини X, замкнута щодо операції множення. Тоді A є групою підстановок на множині об'єктів X. Порядок групи A, що позначається | A |, є число підстановок A, а ступінь групи - це число n елементів у множині об'єктів X.
Найбільш важливими для нас прикладами групи підстановок є симетрична група Sn - група всіх підстановок на безлічі з n об'єктів, ізнакопеременная група An - група всіх парних підстановок. Щоб визначити поняття парної підстановки введемо поняття транспозиції.
транспозиція називається підстановка, яка змінює два елементи місцями один з одним і залишає інші елементи на своїх місцях. Можна показати, що будь-яка підстановка розкладається в добуток транспозиций. Підстановка називається парною, якщо число транспозиций, в які розкладається підстановка, парне.
Нехай A - група підстановок з безліччю об'єктів. Циклом довжини k називається підстановка, що позначається, яка переводить Відомо, що кожна підстановка a може бути представлена ??у вигляді добутку непересічних циклів.
Наприклад,
або
.
Існує природний зв'язок між групами підстановок і графами.
Розглянемо два графа. Взаємно однозначне отбраженіе a безлічі вершин графа на безліч вершин графа, що зберігає суміжність, називаютізоморфізмом. Якщо, то a називається автоморфизмом графа. Сукупність усіх автоморфізмів графа G, що позначається Г (G), утворює групу, називаемуюгруппой графа G, або групою автоморфізмів графа G. Таким чином, елементи групи Г (G) є підстановками, діючими на безлічі вершин графа.
Розглянемо граф G, зображений на малюнку.
Рисунок 1.2 - граф G
Його чотири вершини складають безліч X цілих чисел 1, 2, 3, 4. Зауважимо, що наступний список підстановок
·
·
·
·
включає всі підстановки множини X, що зберігають відношення суміжності в графі G. Приміром, вершини 1 і 4 суміжні в G. Підстановка (13) (2...
