Examples of optimal automata: (The updating rule is given as a set of integers, specifying how many of the neighbors of a node and the node itself must be ON for the node to be ON in the next generation.)
n = 1: Path graph; rule {0}; any initial state.
n = 2: Path graph; rule {0}; both nodes equal.
n = 3: Path graph; rule {1}; one of the end nodes ON.
n = 4: Path graph; rule {0,2}; one node ON.
n = 5: Spider graph with two legs of length 1 and one leg of length 2; rule {1}; one of the end nodes of the short legs ON.
n = 6: 2 X 3 grid with an additional diagonal edge; rule {0,1,3,5}; one degree 2 node (with neighbors of degree 2 and 3) ON.
n = 7: Graph 21244 in House of Graphs ('F@Unw' in graph6 format); rule {0,2,4,5,6}; one node of degree 3 and the node of degree 6 ON.
n = 8: Graph 'G?Dlvw' in graph6 format; rule {0,2,4}; one of the degree 4 nodes adjacent to the degree 6 node ON.
|