Next: Diagrama de subconjuntos Up: Teoria de gr�ficas Previous: Teoria de gr�ficas

Diagramas de Bruijn

Vamos a encontrar que cualquier trabajo con un aut�mata celular lineal la posibilidad de que sus vecindades se traslapen, para ello se revisa la teoria de la disiplina basada en el tratamiento de secuencias que se traslapan, y es cuando surga la utilidad en la teoria de aut�mata de manejar los diagramas de Bruijn, esto es explicado por Solomon Golomb [5].
Los nodos en un diagrama de Bruijn son una secuencia de s�mbolos, similar a una expresi�n regular, los cuales llevan una secuencia espec�fica en la gr�fica, las ligas del diagrama describen como es que se traslapan estas secuencias, estos diferentes grados de traslape, definen al diagrama, as� las ligas pueden ser etiquetadas deacuerdo al sitio desplazado como secuencia de otros caminos.
podemos citar el diagrama gen�rico de un aut�mata (2,1), dos estados tres vecinos, el cual consta de cuatro nodos con ocho logas representando las tres vecindaes llenas y se puede notar en el siguiente diagrama:

 
Figura 3.1: Diagrama de Bruijn para un Aut�mata Celular (2,1).

Ahora podemos particualrizar a cierta regla de un aut�mata, tomaremos un aut�mata (4,h), con sus respectivos subdiagramas, diferenciando los distintos estados con un color respectivo que le corresponde a su estado dentro de la evoluci�n.

 
Figura 3.2: Diagrama de Bruijn para un aut�mata celular (4,h).