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

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

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

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

· Частичный порядок на вершинах:

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

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

.

· Множество

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

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

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

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

.

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

1.

;

2.

, причем

3.

;

4.

.

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

; и .

Предисловие

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

§3.3 Структура G_j при 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).

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

Воспользуемся методом математической индукции:

1. m = 1:

Пусть

, тогда . Тогда, учитывая утверждение 1.1, и , получим требуемое.

2. Пусть утверждение леммы верно для m = k, тогда:

3. Докажем теорему для m = k+1.

Мы имеем:

, тогда:

Если

и , то:

Из утверждения 3.2.1:

, но , т.е. , откуда , ч.т.д.

Теорема 3.3.1.3

«Нулевое» дерево ― бинарное дерево с точностью до петли в корне e_n.

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