Дискретная математика и криптология



СТРУКТУРА И ПЕРИОДЫ ПРЕОБРАЗОВАНИЙ - часть 4


Если j - преобразование п-множества X, то графом преобразования j называют ориентированный граф G(j)=(X,U) с множеством вершин X и множеством дуг U, где (x,y)ÎU Û y=j(x).

Полустепень захода px равна 1 для всех xÎX тогда и только тогда, когда j биективно.

Граф G(j) преобразования j состоит из r компонент связности, 1£r<n, каждая из которых представляет собой простой цикл и, в случае небиективного преобразования, возможно, несколько подходов к этому циклу.

Структурными характеристиками графа G(j) являются число компонент связности, число циклических вершин, число циклов и число подходов к циклам заданной длины и др. Неподвижный элемент преобразования j образует петлю в графе G(j).

Граф G(j) биективного преобразования j (подстановки на множестве Х) состоит из r независимых циклов, 1£r£n. Если ki - число циклов длины i в графе G(j), iÎ{1,2,...,n}, то:

,

где 0£ki£n. Цикловая структура такого графа записывается в виде набора символов

, в котором опускаются все компоненты
, для которых ki=0.

Преобразования j и y множества X называются подобными, если найдётся биективное преобразование d того же множества, при котором j = d-1×y×d.

Отношение подобия на множестве преобразований есть отношение эквивалентности.

Теорема 6.3.

Преобразования j и y множества X

подобны тогда и только тогда, когда графы G(j) и G(y)

изоморфны.

Доказательство. Если преобразования j и y множества X

подобны, то у=j(х) тогда и только тогда, когда d(у)=y(d(х)). Следовательно, графы G(j)

и G(y) изоморфны, так как отличаются лишь переобозначением вершин с помощью подстановки d. Обратное утверждение доказывается рассуждениями в обратном порядке.                                                                                                                                    ¨

6.3. Характеристики периодичности преобразования

Преобразованию j конечного множества X и элементу xÎX поставим в соответствие последовательность F={ji}




Содержание  Назад  Вперед