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

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

Рис. 3.3.3

????? ?, ????? ?? ????? ????????? ???, ????????? ???????? 3.3.1.2 ?? ????????? ?????? ? ????????? ?? ????? ? ????? e_n (??. ???. 3.3.3) ???????, ??? n+1-?? ????? ???? ?? ????? ?.?. ????? ?? ??????????? ???? ???? ? ???????? ?????, ??? ?? ? ????????????.

Теорема 3.3.1.4

Все деревья (в том числе и примыкающие к каждой вершине произвольного цикла) будут иметь столько ярусов, сколько и «нулевое», причем будут иметь такую же структуру.

Более точно: дерево, притягиваемое каждой точкой каждого цикла графа состояний, изоморфно дереву, притягиваемому точкой e_n .

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

Предположим «нулевое» дерево состоит из n ярусов тогда:

1. Если наше дерево состоит менее чем из n ярусов, то, пользуясь теоремой 3.3.1.2, мы восстанавливаем его до дерева изоморфного «нулевому».

2. Если дерево имеет m ярусов, где n<m тогда , получается, что «нулевое» дерево состоит из m ярусов Ї противоречие.

§3.3.2 Исследование высоты деревьев

Теорема 3.3.2.1

Если длина последовательности равна 2^k -1, то высота деревьев будет равна 2^k -1.

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

Пример для k=1 и k=2 строятся довольно просто:

k=1 k=2

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

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

0 (1,0,1) 0

0 (0,0,0) 0

Докажем по индукции

1. База индукции:

Пусть k=3,тогда:

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

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

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

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

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

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

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

0 (0,0,0,0,0,0,0) 0