Grafo de De Bruijn

Un grafo de De Bruijn es un grafo dirigido que permite representar los solapamientos de longitud

El nombre de los grafos deriva del matemático Nicolaas Govert de Bruijn quien los describió en 1946.

[1]​ Sin embargo, dichos grafos ya habían sido descritos por Camille Flye Santa-Casa en 1894[2]​ y por Irving J. Good en 1946.

letras está construido como se explica a continuación.

Los nodos (o vértices) de

palabras de longitud

son dos nodos, hay un arco de

cuando la palabra obtenida al suprimir la primera letra de

es la misma que la palabra obtenida al suprimir la última letra de

; dicho de otra manera, cuando existen dos letras

, y una palabra o cadena

u = a x

v = x b

La presencia de un arco significa entonces que existe una superposición entre dos palabras de la misma longitud.

Es común etiquetar ese arco con la cadena

de la figura a la derecha está construido mediante un alfabeto binario

con cadenas de longitud

cadenas de longitud 3 con el alfabeto binario son: Hay, por ejemplo, un arco que sale del nodo

que va al nodo

Ese arco queda marcado con la cadena

Asimismo, hay un arco que va del nodo

Ese arco queda marcado con la cadena

De cada nodo parten

Esta analogía se explica porque el grafo de De Bruijn

La aplicación de Bernoulli (también llamada la función 2x mod 1 o función diádica para

) es un sistema dinámico ergódico que puede ser visto como un operador de desplazamiento sobre un número k-ádico.

Las trayectorias de este sistema dinámico corresponden a los caminos en el grafo de De Bruijn, con la correspondencia que asocia a cada real

del intervalo semi-abierto

la suma del grafo que corresponde a las

primeras cifras en la representación de