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

Теорема 2.2

«Нулевое» дерево – p-нарное дерево с точностью до петли в корне (0,0 ,0).

Доказательство:

По теореме 2.1 единственная цепь из висячей вершины в (0,0, 0) однозначным образом определяет все элементы дерева (различность определяемых вершин очевидна, и следует из простоты p).

Теорема 2.3

Каждое дерево притягиваемого каждой точкой каждого цикла графа Gy изоморфно нуле

вому» дереву.

Доказательство:

Для любых последовательностей k и l, находящихся на одном ярусе какого-то дерева, для которых выполняется условие:

верно равенство:

,

где ―одна из последовательностей «нулевого» дерева на n-ном ярусе (сумма в поле ) (Следует из теоремы 2.1).

Используя полученное соотношение можно достроить любое дерево до дерева изоморфного «нулевому».

§3 ACS-автомат

§3.1 Постановка задачи

В данной работе рассматривается клеточный автомат (одномерный), функционирование которого осуществляется по следующим правилам:

Дана полоска 1n (сам автомат), все клетки, которой находятся в состояниях «0» и «1». Изменение состояния клетки определяется следующим образом: данная клетка переходит в состояние «1», если её соседи находятся в разных состояниях, и в «0»,если её соседи находятся в одинаковых состояниях. Клетки, находящиеся по краям переходят в то же состояние, которое было у единственной соседней клетки в предыдущий момент времени.

По полоске длины n будем определять вектор , где :

Рассмотрим множество и отображение такое, что

(здесь и ниже – операция сложения по mod p=2, т.е. операция сложения в поле Z2).

Будем рассматривать граф состояний , для которого . Основной целью исследования является изучение структуры графа .

Для начала рассмотрим некоторые определения и обозначения, которые будут использоваться в дальнейшем в работе:

· Ориентированное дерево — это ориентированный граф без циклов, в котором из каждой вершины, кроме одной, называемой корнем ориентированного дерева, выходит ровно одно ребро (более подробно структуры дерева будет определена позже).

· m-й ярус – множество вершин дерева, находящихся на расстоянии m от корня.

· Частичный порядок на вершинах: , если вершины u и v различны и вершина u лежит на единственном элементарном пути, соединяющем вершиной v с корнем дерева.

· Корневое поддерево с корнем v — подграф .

· Множество назовем множеством висячих вершин графа .

§3.2 Краткий обзор предыдущих результатов

В прошлом году на ряде конференций (см. Используемые источники) была представлена работа по клеточным автоматам, в которой был исследован частный случай линейного оператора и найдены высоты деревьев для последовательностей, состоящих из 2n-1 элементов. В ней были представлены следующие утверждения, которые будут использоваться в дальнейшем:

Утверждение 3.2.1

.

Утверждение 3.2.2

1. ;

2. , причем

3. ;

4. .

Утверждение 3.2.3

; и .

Предисловие

В параграфе будет рассказано о свойствах графа состояний оператора j, а именно будет описана его структура.

§3.3 Структура Gj при p=2

§3.3.1 Исследование структуры

Пользуясь утверждением 3.2.2, мы получаем, что среди всех последовательностей можно выделить следующие:

1. которые невозможно получить не из каких других, например: (1,0,0) (они будут образовывать висячие вершины графа);

2. которые, спустя несколько итераций возвращаются в начальное положение, например:

(1,0,0,0) ® (0,1,0,0) ® (1,0,1,0) ® (0,0,0,1) ® (0,0,1,0) ® (0,1,0,1) ® (1,0,0,0)

(такие последовательности в графе будут соответствовать вершинам цикла)

Используя утверждение 3.2.2, можно сделать вывод:

Теорема 3.3.1.1

Каждая компонента связности графа является циклом (возможно длины 1), каждый элемент которого притягивает дерево (т.е. является корнем ориентированного дерева) (см. рис. 3.2.1).

Наша основная задача определить длины циклов и высоты деревьев, описать их структуру и найти их количество.

Теорема 3.3.1.2

Для любых последовательностей k и l, находящихся на одном ярусе какого-то дерева, для которых выполняется условие: верно равенство:

, где ―одна из последовательностей «нулевого» дерева на n-ном ярусе.

Более точно это можно сформулировать так:

Рис. 3.2.2

Для любого «полного» корневого поддерева g с корнем v дерева G (с корнем в ): , где и – подмножество такое, что: , при этом (см. рис. 3.2.2).

 Скачать реферат