Diagrama de subconjuntos

Otro diagrama que se puede obtener a partir del diagrama de Bruijn es el diagrama de subconjuntos. Para construir el diagrama de subconjuntos de la regla 54 el primer paso es tomar las vecindades parciales las cuales etiquetan a los nodos del diagrama mostrado en la figura 3.24 en notación decimal (ver figura 3.23 (b)). Posteriormente, se construye una relación de las conexiones entre nodos tomando como criterio de clasificación el estado al que evolucionan las células centrales de las vecindades que se forman de acuerdo a los nodos que se conectan.

Tabla 3.2: Conexiones entre nodos para la regla 54.

Nodo de	Nodo de llegada con	Nodo de llegada con
partida	evolución a 0	evolución a 1
0	0	1
1	3	2
2	$\emptyset$	0,1
3	2,3	$\emptyset$

En la tabla 3.2 se puede observar que existen dos casos en los cuales se incluye al conjunto vacío. Esta inclusión se da debido a que el nodo etiquetado con el número 2 no tiene establecida ninguna liga por medio de la cual la célula central de la vecindad resultante de la conexión a través de la misma evolucione al estado 0. El mismo caso se da en el nodo 3 para el otro estado. La incorporación del conjunto vacío garantiza que los nodos van a estar ligados hacía algún lado, lo que nos permitirá establecer las relaciones que generan el diagrama de subconjuntos.

Tabla 3.3: Relaciones entre subconjuntos para la regla 54.

Subconjunto	Valor en	Subconj. de llegada	Subconj. de llegada
de partida	decimal	con evolución a 0	con evolución a 1
{ 0,1,2,3 }	15	13	7
{ 0,1,2 }	7	9	7
{ 0,1,3 }	11	13	6
{ 0,2,3 }	13	13	3
{ 1,2,3 }	14	12	7
{ 0,1 }	3	9	6
{ 0,2 }	5	1	3
{ 0,3 }	9	13	2
{ 1,2 }	6	8	7
{ 1,3 }	10	12	4
{ 2,3 }	12	12	3
{ 0 }	1	1	2
{ 1 }	2	8	4
{ 2 }	4	0	3
{ 3 }	8	12	0
{ $\emptyset$ }	0	0	0

Una vez que se tiene la relación de conexiones entre nodos, el siguiente paso es obtener todos los subconjuntos de $N$ y relacionarlos a partir de la tabla 3.2. Los subconjuntos de $N$ están determinados por $2^{\char93 (N)}$, para este caso sería $2^4 = 16$ subconjuntos de $N$ incluyendo al conjunto vacío.

En la tabla 3.3 se muestran los 16 subconjuntos del conjunto $N$ y se representan con un valor decimal el cual es obtenido sumando el resultado de elevar la base 2 a la potencia que indique el elemento del subconjunto. Por ejemplo, el subconjunto { 0,1,2,3 } tiene un valor decimal 15 puesto que $2^0 + 2^1 + 2^2 + 2^3 = 1 + 2 + 4 + 8 = 15$. En el caso del conjunto vacío se asume que éste tiene como valor decimal 0. Los subconjuntos de las columnas 3 y 4 también están expresados en términos de su valor decimal. La manera de relacionar a los subconjuntos es la siguiente: tomemos el subconjunto { 0,1,2 } cuyo valor decimal es 7, el subconjunto con evolución a 0 con el cual va a establecer una liga estará constituido por elementos de la columna 2 de la tabla 3.2 que correspondan con los elementos del subconjunto 7 sin repetirlos. En este caso el subconjunto de llegada con evolución a 0 sería { 0,3 } el cual tiene como valor decimal 9. De igual manera se obtiene, aunque tomando la columna 3 de la tabla 3.2, el subconjunto con evolución a 1 con el cual establece una liga el subconjunto 7, el cual en este caso sería el subconjunto { 0,1,2 } cuyo valor decimal es 7.

A partir de la tabla 3.3 se puede trazar el diagrama de subconjuntos, este diagrama es mostrado en la figura 3.25.

Figura 3.25: Diagrama de subconjuntos de la regla 54.

En la figura 3.25 se observa que los subconjuntos de $N$ representan nodos los cuales están interconectados de acuerdo a la relación de la tabla 3.3. Además, las ligas están etiquetadas de acuerdo al estado de evolución que va relacionando a las parejas de nodos.

Una aplicación importante del diagrama de subconjuntos la podemos encontrar al querer indentificar configuraciones las cuales son Jardines del Edén. Un ejemplo de una configuración de este tipo se da cuando existe una secuencia de conexiones del subconjunto máximo al subconjunto mínimo; en este caso el subconjunto máximo sería 15 y el mínimo sería $\emptyset$. La configuración que resulta se obtiene de acuerdo al estado de evolución que relaciona a las parejas de nodos. Por ejemplo, si el nodo 15 evoluciona al estado 0 con el nodo 14, y el nodo 14 evoluciona al estado 1 con el nodo 13 y así sucesivamente hasta llegar al $\emptyset$, los estados de evolución que se obtienen a partir de las conexiones constituirán una configuración Jardín del Edén.