Topology of the State Transition Graph

The following lemma shows that the tree structure of the state transition graph Q is very regular. Notice, in particular, that since the proof makes no assumption on the form of T, the result is generally valid for ail additive rules. 

Lemma 5 The trees rooted on each node of alt cycles of Q are identical. 

Proof We prove this statement by showing that all trees rooted on cycles are equal to the tree rooted on the null configuration. Let A(x) represent the configuration that evolves into the null state after exactly t iterations i.e. T x)YA x) = 0 mod x — 1). Let R x) and be two states on the same cycle so that 

This says that all conliguratioiis evolve to the state R x) after t 

Since if is therefore an isomorphism, we have proven that any tree rooted on a cyclic state is identical to the tree rooted on the null configuration. I 

---

Table 5.2 Number of topologically distinct connected graphs ) ), number of cyclic equivalence classes Q, maximal numbers of possible cycle sets Cot and Ct for OT and T rules, respectively, and the maximal number of possible distinct topologies of the state transition graph, calculated for graphs with size fV=5,6,..., 12 in T 2. ...

---