Graphs and Graph Theory

[Citation needed]

I'm sorry. I might have created a duplicate thread.

Let's discuss graphs and graph theory. Are there any notable CA-related graphs?

[pifricted]

https://conwaylife.com/wiki/File:OT_map_(non-Gray).png:
A map of outer-totalistic rules. Birth conditions iterate in binary over the x axis (the right half has B0), survival in the y axis (the bottom half has S8). Outside of the bottom-left quadrant (where only the all-off agar is considered space), it is symmetrical due to the duality of black/white reversal. Green rules have known explicit examples of spaceships within them, red ones have been proven not to support any. (See file description for more details.)

https://conwaylife.com/wiki/File:OT_spaceship_map.png:
A map of outer-totalistic rules. Birth conditions iterate in a Gray code over the x axis, survival in the y axis. Green rules have known explicit examples of spaceships within them, red ones have been proven not to support any. (See file description for more details.)

[May13]

I'm sorry. I might have created a duplicate thread.

I searched for "graph" in the Sandbox, but didn't see any similar thread.
Still lifes can be represented as graphs:

• Vertices = living cells,
• Edges = pairs of living neighbors.

It is known that if all the vertices of a graph have an odd degree, then the number of vertices in this graph is even. It follows that in cellular automata, where an odd number of neighbours is required for survival, still lifes will always have an even number of cells. For example, there are no 10001-bit still lifes in B3/S1357, B2/S13H and B2-ace/S1e3-c.

[pifricted]

Still lifes can be represented as graphs:

• Vertices = living cells,
• Edges = pairs of living neighbors.

We can use this making neiborhoods:

[confocaloid]

Let's discuss graphs and graph theory. Are there any notable CA-related graphs?

The following directed graph has seven vertices and thirteen arcs, and illustrates all cell states and all possible state-to-state transitions in LifeHistory:

lhgraph.png (36.02 KiB) Viewed 2697 times

Each vertex of the directed graph represents a cellstate of the CA.
Each arc (a directed edge) of the directed graph represents a transition of the CA.

By looking at the directed graph, one can immediately see that it is not connected (for example, the vertex 6 is isolated; the only arc from that vertex leads back to itself); vertices 0, 1, 2 form a weakly connected subgraph where there is an arc from 0 to 1 but there is no arc leading to 0 from any other vertex; likewise vertices 3, 4, 5 form a weakly connected subgraph where there is an arc from 5 to 4 but there is no arc leading to 5 from any other vertex; there are arcs in both directions between 1 and 2, and also between 3 and 4.

These observations correspond to observations that can be made about the CA. Marked cells always remain marked; unmarked cells always remain unmarked; state 6 is neither marked nor unmarked, and acts as a "permanent wall"; history envelope cannot be cleared; state-5 "start ON" cells can never form during evolution, except by surviving from the first generation.

The directed graph does not completely describe rules that govern evolution. There are many other 7-state cellular automata with the exact same directed graph of states and transitions. Nevertheless, all such cellular automata are related to each other in an interesting way. The directed graph is a way to explain that relationship.