Construcción de los diagramas

En la primer columna de izquierda a derecha de la figura 5.9 se muestran todas y cada una de las conexiones entre los nodos del diagrama de Bruijn de LCATRAFFICFLOWVMAX2. Estos nodos están representados por vecindades parciales de cuatro células, las vecindades parciales de la izquierda representan a los nodos fuente mientras que las vecindades parciales de la derecha representan a los nodos destino. Como se mencionó anteriormente, el incremento en el número de estados y en el radio de vecindad de un autómata celular hace que su tamaño crezca de manera exponencial. Por esta razón su nivel de complejidad también crece de manera exponencial y por consecuencia el análisis del mismo requiere una mayor cantidad de tiempo y esfuerzo.

La construcción del diagrama de Bruijn de LCATRAFFICFLOWVMAX2 es bastante laboriosa por los motivos ya expuestos, y aunque el programa NXLCAU lo proporciona de manera automática, lo muestra de forma desordenada, lo que hace prácticamente imposible analizarlo sin tener que invertir una buena cantidad de tiempo en darle forma legible. Por esta razón, se optó por construirlo de manera manual con el fin de llevar a cabo el análisis paso a paso. Por otra parte, en el caso del diagrama de subconjuntos no fue posible cons-truirlo manualmente debido a que la cantidad de nodos es demasiado grande, es decir, el número de nodos que contiene el diagrama de subconjuntos de este autómata es dado por $2^{256}$.

El diagrama de Bruijn de LCATRAFFICFLOWVMAX2 contiene un total de $4^{2(2)} = 256$ nodos y $4^{2(2) + 1} = 1024$ aristas las cuales representan las 1024 vecindades. En la figura 5.10 se muestra solo un fragmento del diagrama de Bruijn construido.

Figura 5.10: Fragmento del diagrama de Bruijn de LCATRAFFICFLOWVMAX2 el cual tiene un comportamiento equivalente al del modelo de Nagel con $V_{max} = 2$.

Como se puede observar en la figura 5.10, es difícil ubicar los diferentes ciclos los cuales están todos contenidos en el diagrama debido al tamaño y la cantidad de aristas que se cruzan unas con otras. Por esta razón se buscó una forma más práctica de localizar los anillos que contiene el diagrama para verificar si las secuencias que generan tienen desplazamientos constantes, tal y como se planteó para la regla 184 y la regla 43. Una manera alterna a la representación típica del diagrama de Bruijn es dibujarlo como una especie de árbol, donde cada una de las vecindades parciales de la primer columna de la figura 5.9 tiene una representación decimal. Estas vecindades están ordenadas de forma ascendente de acuerdo al número de estados y a las posibles combinaciones. Así pues, la raíz del árbol sería el nodo etiquetado con el número 0, sus ramas son los nodos 1,2 y 3 puesto que de acuerdo a la figura 5.9 son los nodos con los que se conecta el nodo 0, además de la conexión hacía sí mismo. Siguiendo esta mecánica las ramas del nodo 1 serían los nodos 4,5,6 y 7 y las del nodo 2 los nodos 8,9,10 y 11.

Figura 5.11: Árbol que representa las conexiones entre los nodos del diagrama de Bruijn. En esta figura el árbol está representado de manera resumida. Se puede observar que en algunos casos solo aparecen conectados los nodos que representan el inicio del rango de interconexión.

Como podemos notar, la conexión entre nodos sigue un patrón de 1 a 4 por la naturaleza del autómata que se está analizando y la forma en que se construyen los diagramas de Bruijn, es decir, cada nodo origen tiene 4 destinos y los orígenes y destinos están conectados en forma sucesiva de menor a mayor.

De esta manera, al llegar al nodo 63 tenemos que sus ramas son los nodos 252,253,254 y 255 con lo cual se llega al total de nodos del diagrama. De tal forma, al pasar al nodo 64 éste se ramificará o se conectará con los nodos 0,1,2 y 3 (los cuales ya serían hojas del árbol). Reiniciando nuevamente desde 0, con esto tenemos que cada 64 orígenes se repiten nuevamente los destinos con lo que se asegura la simetría del diagrama al tener cada nodo 4 aristas de salida y 4 aristas de llegada.

En la figura 5.11 se muestra el árbol ya elaborado de la manera antes descrita. En esta figura se representa el árbol de manera resumida por cuestiones de espacio. Por medio de este árbol es más fácil localizar los ciclos ya que sólamente hay que tomar como inicio del mismo algún nodo del árbol y seguir sus ramificaciones hasta encontrarlo nuevamente; si no es el caso, entonces la secuencia de nodos seleccionada no forma ningún ciclo. Como ejemplo de lo anterior está el ciclo formado de la siguiente manera: $0\rightarrow2\rightarrow8\rightarrow35\rightarrow142\rightarrow56\rightarrow226\rightarrow136\rightarrow32\rightarrow128\rightarrow0$. Este mismo ciclo, como otros, se muestran en las subsecuentes figuras en la notación original (vecindades parciales de cuatro céluas) que se mostró en la figura 5.9, de tal forma que el ciclo equivalente expresado en la otra notación es: $0000\rightarrow0002\rightarrow0020\rightarrow0203\rightarrow2032\rightarrow0320\rightarrow3202\rightarrow2020\rightarrow0200\rightarrow2000\rightarrow0000$.

Una vez que se localiza un ciclo se verifica si la secuencia generada tiene desplazamientos constantes de todas sus células al aplicar la regla de evolución. Recordemos que la secuencia está constituida por los estados de evolución de cada una de las células centrales las cuales forman parte de las vecindades que se obtienen al efectuar la operación de superposición, la cual se ve reflejada gráficamente en la conexión entre los nodos. A continuación se muestran tanto ciclos que producen secuencias sin acarreo hacia la derecha como ciclos que producen secuencias con diferentes tipos de acarreo.

Figura 5.12: Anillos que generan secuencias en las cuales las células no tienen desplazamientos uniformes hacia la derecha.

Figura 5.13: Anillos que generan secuencias en las cuales las células tienen desplazamientos uniformes hacia la derecha.

En la figura 5.12 se observan algunos de los anillos o ciclos contenidos en el diagrama de Bruijn que dan origen a diferentes secuencias las cuales no tienen un deplazamiento uniforme hacia la derecha de todas sus células a través de la evolución del autómata. Otro aspecto interesante que podemos resaltar y que se muestra también en la figura 5.12 es que anillos con diferentes estructuras generan la misma secuencia, es decir, podemos ubicar en el diagrama de Bruijn las diversas maneras en que es posible construir una determinada secuencia.

Aunque las secuencias mostradas en la figura 5.12 y muchas otras que se analizaron durante la investigación no tengan desplazamientos que permitan establecer con certeza cual será su comportamiento a través del tiempo, el análisis de las mismas nos permite encontrar otras secuencias que sí presentan diferentes acarreos, esto se da porque al analizar una secuencia lo que se hace es iterarla $n$ veces hasta que el proceso entra en un ciclo, una vez que se cierra el ciclo se verifica si existe acarreo o no, si no existe de cualquier forma la secuencia que inicia el ciclo sí presenta un acarreo, aunque ésta es generada por un anillo distinto al que originalmente se está analizando.

Para ejemplificar lo anterior tomemos el anillo que produce la secuencia 00111003, al iterarla observamos que entra en un ciclo en la tercera generación el cual es de periodo 8, si tomamos ahora la secuencia que inicia el ciclo encontraremos que las células tienen un co-rrimiento de 8 sitios a la derecha en 8 generaciones, esta secuencia es producida por el anillo formado por los nodos $0202\rightarrow2023\rightarrow0230\rightarrow2302\rightarrow3020\rightarrow0200\rightarrow2002\rightarrow0020\rightarrow0202$. Es natural pensar que si tomamos una secuencia que inicia un ciclo el corrimiento de las células va a ser igual al periodo del ciclo. El problema es que nuestro enfoque es conforme al análisis de flujo de tránsito y lo que a nosotros nos interesa es predecir el avance de las células o autos a determinados intervalos de tiempo. Por esta razón, aunque las secuencias se repitan esto no asegura que el avance va a ser constante para todas las células. Lo que si podemos determinar a través de los ciclos es el avance de los autos a nivel individual.

Es importante mencionar que al trabajar con un autómata celular de más estados y bajo la perspectiva de análisis que tenemos el alterar la estructura de una secuencia implica que el corrimiento también va a ser alterado, a diferencia de las secuencias generadas por los anillos de los autómatas de tipo (2,1) mostradas en los capítulos anteriores, donde mencionamos que dado un acarreo, éste se mantiene constante para la secuencia que lo presenta o cualquier permutación de la misma.

Lo anterior se puede comprobar observando la figura 5.13 en la cual se muestran diferentes tipos de corrimientos, en la parte inferior izquierda podemos ver dos anillos que construyen secuencias las cuales tienen un desplazamiento de dos posiciones a la derecha en una ge-neración, la secuencia producida por el anillo de la izquierda originalmente no presenta este tipo de desplazamiento, pero si hacemos una permutación colocando dos o tres ceros entre las células que están en los estados 2 y 3, entonces el corrimiento se produce. Otro punto importante es que la clasificación que hemos mostrado en las figuras 5.12 y 5.13 de los anillos con desplazamientos uniformes y no uniformes la hemos hecho en base a que básicamente los corrimientos que más nos interesa ubicar son hacia la derecha debido a la dinámica de los modelos para flujo de tránsito de autos, sin embargo, en prácticamente todos los anillos podemos observar un corrimiento de 1 sitio a la izquierda en una generación, esta característica es propia del fenómeno de tránsito vehicular y tiene su explicación en las ondas cinemáticas de acuerdo a la teoría de Lighthill-Whitham.

En la figura 5.14 se muestran algunos de los ciclos del LCATRAFFICFLOWVMAX2 obtenidos de las mismas secuencias analizadas para identificar acarreos, estos ciclos son de diferente longitud o periodo. En algunos ciclos de la figura 5.14 se muestran secuencias que tienen más de un ancestro, con lo que identificamos en el autómata celular características de sobreyectividad.

Figura 5.14: Algunos ciclos de diferentes periodos del LCATRAFFICFLOWVMAX2.