Functional graph trees for circulants with linear boolean functions at the vertices.pdf Пусть даны n ^ 3, {d1, d2,... , dk} С {0,1,... ,n — 1} и ориентированный граф Gn;d1,d2,...,dk с множествами вершин {0,1,... ,n — 1} и дуг {ij : (j — i) = dr (mod n), r = = 1, 2,... , k}. Матрица смежности таких графов называется циркулянтом. Эти графы также принято называть циркулянтами [1]. Рассмотрим следующую дискретную динамическую систему. В каждый момент времени вершины циркулянта Gn;d1,d2,..,dk помечены элементами v0,v1,... ,vn-1 из конечного поля Fq порядка q. Набор v = (v0,v1,... ,vn-1) G F™ назовём состоянием системы. В следующий момент времени (такт работы системы) состояние системы меняется, и динамика его изменения определяется отображением Af : Fn —> Fn где f = (fo, f1,..., fn-1) и новая метка каждой вершины i является значением функции fi : F^ ^ Fq, аргументы которой принимают значения старых меток в тех вершинах, дуги из которых входят в вершину i. Функциональным графом Gf,q называется ориентированный граф, вершинами которого являются элементы Fq1", причём дуга из вершины v идёт в вершину v тогда и только тогда, когда Af,q(v) = и. В работе рассматривается структура функционального графа в случае, когда q = 2, все функции fi равны между собой и линейны и отображение Af,2 действует следующим образом: Af,2(vo,v1, . . . ,vn-1) = (Щ,Щ,. . . ,Un-1), Ui = vi-1 + vi + vi+1, i = 0,1,...,n — 1, где v-1 = v™-1,v™ = vo. С использованием методов, изложенных в [2], доказаны следующие свойства функционального графа Gf,2: — если n не кратно 3, то отображение Af,2 обратимо и функциональный граф Gf}2 является дизъюнктивным объединением простых контуров; цикл Gi с количеством рогов p = — в функциональном графе Gf,2 при n = 3 • 2k(2m + 1) множество вершин, принадлежащих деревьям, разбивается на 2k уровней, причём каждая вершина дерева имеет ровно четырёх предков; — при чётном n функциональный граф Gf,2 содержит четыре неподвижные точки, при нечётном n — две неподвижные точки; — если n = 2k(2m + 1), то все длины циклов функционального графа Gf,2 являются делителями 2k(2s — 1), где s = min{j : j > 0, 2j = ±1 (mod 2m + 1)}.

Скачать электронную версию публикации