308
правок
Изменения
Нет описания правки
Также, композицию перестановок можно выразить как действие одной перестановки на другую.
Стоит отметить, что действие перестановки <tex>\pi^n</tex> соответствует переходу по графу <tex>n</tex> раз
==Циклы==
Перестановку можно представить в виде графа. Граф содержит ребро от вершины <tex>x_i</tex> к вершине <tex>x_j</tex> если <tex>\pi(x_i) = x_j</tex>. Тогда циклы перестановки соответствуют циклическим путям в графе.
С циклами связаны некоторые интересные свойства перестановок.
{{Определение
|neat = 1
|definition=Степенью перестановки называется минимальное число <tex>n \in N</tex> такое, что <tex>\pi^n = i</tex>}}
{{Утверждение
|statement=
Степень перестановки равна наименьшему общему кратному длин всех циклов
}}
Доказательство этого факта [[Вычисление_порядка_перестановки_в_группе_перестановок | здесь]]
{{Утверждение
|statement=
Если длины всех циклов не превышают 2, то перестановка является [[Умножение_перестановок,_обратная_перестановка,_группа_перестановок#def_involution | инволюцией]].
|proof=
Действительно, в таком случае по вышеупомянутому <tex>\pi^2 = i</tex>. Домножив на <tex>\pi^{-1}</tex> получим <tex>\pi^{-1} = \pi</tex>.
}}
== Источники ==
* [http://ru.wikipedia.org/wiki/%CF%E5%F0%E5%F1%F2%E0%ED%EE%E2%EA%E0 Википедия]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]
