Gráfico de De Bruijn

En teoría de grafos , un grafo de De Bruijn n -dimensional de m símbolos es un grafo dirigido que representa superposiciones entre secuencias de símbolos. Tiene m ⁿ vértices , que consisten en todas las secuencias de longitud n posibles de los símbolos dados; el mismo símbolo puede aparecer varias veces en una secuencia. Para un conjunto de m símbolos S = { s ₁ , …, s _m }, el conjunto de vértices es:

${\displaystyle V=S^{n}=\{(s_{1},\puntos ,s_{1},s_{1}),(s_{1},\puntos ,s_{1},s_{2}),\puntos ,(s_{1},\puntos ,s_{1},s_{m}),(s_{1},\puntos ,s_{2},s_{1}),\puntos ,(s_{m},\puntos ,s_{m},s_{m})\}.}$

Si uno de los vértices puede expresarse como otro vértice desplazando todos sus símbolos un lugar hacia la izquierda y añadiendo un nuevo símbolo al final de este vértice, entonces este último tiene una arista dirigida hacia el vértice anterior. Por lo tanto, el conjunto de arcos (es decir, aristas dirigidas) es

${\displaystyle E=\{((t_{1},t_{2},\puntos ,t_{n}),(t_{2},\puntos ,t_{n},s_{j})):t_{i}\en S,1\leq i\leq n,1\leq j\leq m\}.}$

Aunque los gráficos de De Bruijn llevan el nombre de Nicolaas Govert de Bruijn , fueron inventados de forma independiente tanto por De Bruijn ^[1] como por IJ Good . ^[2] Mucho antes, Camille Flye Sainte-Marie ^[3] utilizó implícitamente sus propiedades.

• Si n = 1 , entonces la condición para que dos vértices formen una arista se cumple vacíamente y, por lo tanto, todos los vértices están conectados, formando un total de m ² aristas.
• Cada vértice tiene exactamente m aristas entrantes y m aristas salientes.
• Cada gráfico de De Bruijn n -dimensional es el dígrafo lineal del gráfico de De Bruijn ( n – 1) -dimensional con el mismo conjunto de símbolos. ^[4]
• Cada grafo de De Bruijn es euleriano y hamiltoniano . Los ciclos de Euler y los ciclos hamiltonianos de estos grafos (equivalentes entre sí mediante la construcción del grafo lineal) son secuencias de De Bruijn .

A continuación se muestra la construcción del gráfico lineal de los tres grafos binarios de De Bruijn más pequeños. Como se puede ver en la ilustración, cada vértice del grafo de De Bruijn de n dimensiones corresponde a una arista del grafo de De Bruijn de ( n – 1) dimensiones , y cada arista del grafo de De Bruijn de n dimensiones corresponde a una trayectoria de dos aristas en el grafo de De Bruijn de ( n – 1) dimensiones .

Los gráficos binarios de De Bruijn se pueden dibujar de tal manera que se asemejen a objetos de la teoría de sistemas dinámicos , como el atractor de Lorenz :

Esta analogía puede hacerse rigurosa: el gráfico de De Bruijn de dimensión n y símbolo m es un modelo del mapa de Bernoulli.

${\displaystyle x\mapsto mx\ {\bmod {\ }}1.}$

El mapa de Bernoulli (también llamado mapa 2 x mod 1 para m = 2 ) es un sistema dinámico ergódico , que puede entenderse como un único desplazamiento de un número m -ádico . ^[5] Las trayectorias de este sistema dinámico corresponden a los paseos en el grafo de De Bruijn, donde la correspondencia se da al mapear cada x real en el intervalo [0,1) al vértice correspondiente a los primeros n dígitos en la representación base - m de x . Equivalentemente, los paseos en el grafo de De Bruijn corresponden a trayectorias en un subdesplazamiento unilateral de tipo finito .

Se pueden utilizar incrustaciones similares a ésta para demostrar que los gráficos binarios de De Bruijn tienen un número de cola 2 ^[6] y que tienen un grosor de libro de como máximo 5. ^[7]

• Algunas topologías de redes grid son gráficos de De Bruijn.
• El protocolo de tabla hash distribuida Koorde utiliza un gráfico de De Bruijn.
• En bioinformática , los gráficos de De Bruijn se utilizan para el ensamblaje de novo de lecturas de secuenciación en un genoma . ^{[8] [9] [10] [11] [12]}

• El toro de Bruijn
• Gráfico de Hamming
• Gráfico de Kautz

• Weisstein, Eric W. "Gráfico de De Bruijn". MundoMatemático .
• Tutorial sobre el uso de los gráficos de De Bruijn en bioinformática por Homolog.us