Next: Mapeo Local induce Up: Teor�a de Gr�ficas Previous: Diagrama de parejas

Aut�mata celular binario

En este caso tomaremos un aut�mata celular con dos estados y un vecino por cada lado, es decir un aut�mata . La regla se representa de dos formas ya sea en notaci�n binaria o en notaci�n decimal. En este caso se tienen ocho vecindades de tama�o tres.

 
Figura 2.3: Regla de evoluci�n del aut�mata (2,1) regla 30.

Consecuentemente k=2 y s=2, tenemos nodos y ligas, que a su vez se pueden identificar los nodos como el n�mero de estados del aut�mata y las ligas el n�mero de vecindades del aut�mata. Los estados estan formados por las fracciones de vecindad: 00, 01, 10 y 11, que en notaci�n decimal se representan como los estados: 0, 1, 2 y 3. Como se hab�a mencionado en la secci�n anterior la naturaleza de los estados no es muy importante si no m�s bien la regla de evoluci�n que afectan a las vecindades. Para mayor ilustraci�n los estados se representar�n a trav�s de colores. La funci�n de transici�n , indica el mapeo de la vecindad en el tiempo t al nuevo estado de evoluci�n en el tiempo t+1.

 
Figura 2.4: Diagrama de de Bruijn para la regla 30.

Para obtener el diagrama de subconjuntos emplearemos la tabla de relaciones de la Secci�n 2.3, entonces tenemos nodos en el diagrama de subconjuntos, que son exactamente todos los subconjuntos que se formaron en esa misma secci�n, ahora bien estos subconjuntos se representaran en notaci�n decimal como se ilustra en el siguiente cuadro:

 
Tabla 2.2: Conectando subconjuntos.

en este cuadro podemos observar perfectamente las cuatro clases unitarias que existen dentro del diagrama empezando por el conjunto m�ximo hasta llegar al conjunto m�nimo, las columnas tres y cuatro muestran a que subconjunto se liga el subconjunto de la primera columna y con que estado. De esta manera se obtienen todas las ligas en el diagrama de subconjuntos.

 
Figura 2.5: Diagrama de subconjuntos para la regla 30.

Para construir el diagrama de parejas efectuaremos el producto carteseano de las matrices de conectividad del diagrama de de Bruijn. En este caso tendremos parejas ordenadas que a su vez son el n�mero de nodos del diagrama de parejas. Esta matriz recibe el nombre de la matriz T y sus sub�ndices estan formados por todas las parejas posibles , donde a y b pertenecen a ,

es claro notar que los sub�ndices de la primera submatriz son las parejas ordenadas (0,0), (0,1), (0,2) y (0,3). Como ejemplo, el sub�ndice (0,0) contiene un ciclo consigo mismo ya que el estado cero evoluciona en el mismo cero y as� para toda la matriz. A continuaci�n se mostrara el diagrama de parejas completo, cabe se�alar que de este diagrama se pueden producir dos diagramas m�s, uno de ellos puede ser el diagrama ordenado donde la simetr�a mostrada en el diagrama original se pierde y el otro diagrama es el que nos muestra exclusivamente los ciclos que se forman a trav�s de ciertas secuencias dadas. Para estos diagramas los ciclos autocontenidos se representan como un radio dentro del nodo.

 
Figura 2.6: Diagrama de parejas para la regla 30.

Next: Mapeo Local induce Up: Teor�a de Gr�ficas Previous: Diagrama de parejas