next up previous contents
Next: Third level diagrams Up: De Bruijn diagrams Previous: De Bruijn matrix

Second level diagrams

Once acceptable strips extending along one dimension have been found, they can be stacked in some orthogonal direction - along a second dimension. The same procedure applies as before; each ring is split into two overlapping subrings, following which a diagram (or its connectivity matrix) is prepared showing how to combine them into longer entities.

Here there is an overt problem which is only implicit in the first level diagram, namely that links ought to be eliminated which terminate in dead ends; since they cannot participate in arbitrarily large configurations. Although dead ends occur at the first level, they get discarded whenever closed loops are extracted from the diagram.

At the second, or final level, it is likely that only a finite representative of the infinite plane will be exhibited, so it is necessary to know in advance if some path will eventually be blocked. The solution is to program a recursive scan of the proposed second level diagram, in which all nodes are eliminated which have no incoming arrows, as well as those which have no outgoing arrows.

The final product will contain only loops joined to each other. There is no guarantee that there will be global loops; in Life this lack produces the phenomenon known as ``fuses.'' It is possible to circulate in one part of a graph for an arbitrarily long time, later crossing over to another part, from which there is no return; but where there are new loops in which to continue circulating.

Of course this can happen several times, producing composite fuses. In the terminology of matrix theory, such connectivity matrices have block triangular form.



Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx