Структура графа состояний клеточных автоматов определённого типа — страница 5

  • Просмотров 352
  • Скачиваний 7
  • Размер файла 456
    Кб

представить длины последовательности в виде: , то 2-1k Ї высота дерева. Теорема доказана. §3.4 Структура G при p2 Введение В параграфе 2 мы рассматривали структуру графа состояний для произвольного линейного оператора над Zp. В данном параграфе пойдет речь о структуре графа G определенного в параграфе 3.1. По аналогии со случаем p=2, по состоянию числовой полоски длины n (т.е. самого автомата с состояниями 0,1,..p-1) будем определять

вектор, и рассматривать такое, что: Все остальные основные определения вводятся аналогичным образом, как и в случае p=2, основным предметом исследования является структура графа G. Одним из важных свойств оператора  является его аддитивность: которая следует из линейности оператора . В предыдущем параграфе было доказано утверждение о том, что для произвольного линейного оператора  «нулевое» дерево – p-нарное дерево с

точностью до петли в корне (0,0..,0) (теорема 2.2). В данном параграфе будет определена высота нулевого дерева, тем самым будут определена высота дерева притягиваемого каждой точкой каждого цикла графа G (теорема 2.3). Теорема 3.4.0 Вершина является висячей тогда и только тогда, когда n – нечётное и выполняется условие: Доказательство: Пусть у нас есть последовательности и Тогда Но тогда . Но по условию , т.е. для того чтобы вершина была

висячей необходимо и достаточно, чтобы , т.е. Теорема полностью доказана. Теорема 3.4.1 Если длина последовательности кратна двум, то граф Gφ ― дизъюнктное объединение циклов. Доказательство: Воспользуемся тем, что дерево, притягиваемое каждой точкой каждого цикла, изоморфно нулевому дереву. Рассмотрим нулевое дерево. Его высота при n=2k равна нулю. Это следует из того, что , но m=2s+1, противоречие. Теорема полностью доказана. Теорема

3.4.2 Если длину последовательности представить в виде pk(2l)-1, (p,l)=1, тогда pk есть высота «нулевого» дерева. Доказательство: Для начала докажем следующие леммы. Лемма 1 – висячая вершина причем, . Рис. 3.4.1 Пример для p = 5. Доказательство леммы 1: Для начала рассмотрим шахматную раскраску таблицы (2pk-1)(pk+1), строки которой есть последовательности , , …, (см. рис.). Тогда числа, стоящие на закрашенных позициях равны 0. Остальные координаты

образуют треугольник Паскаля с вершиной в 1 (см. пример на рис. 3.4.1 для p = 5). Тогда т.к. , то: , при этом (все значения биноминальных коэффициентов берутся по модулю p, так как мы рассматриваем вектор в пространстве ) Замечание: Здесь и ниже, все многочлены рассматриваются над полем  Докажем, что Действительно, т.к. (т.к. ), то: . Откуда , ч.т.д. Замечание Висячесть вершины следует из теоремы 3.4.0 Следствие – висячая вершина причем, . Для