Graphe de de Bruijn

Le graphe ${\displaystyle B(2,3)}$ ci-contre est construit sur un alphabet binaire ${\displaystyle A=\{0,1\}}$ pour des mots de longueur ${\displaystyle n=3}$. Les ${\displaystyle 2^{3}=8}$ mots de longueur 3 sur l'alphabet binaire sont :

${\displaystyle 000,\ 001,\ 010,\ 011,\ 111,\ 110,\ 101,\ 100}$.

Il existe par exemple un arc allant du sommet ${\displaystyle 000}$ au sommet ${\displaystyle 001}$ car le suffixe de longueur 2 de ${\displaystyle 000}$ est égal au préfixe de longueur 2 de ${\displaystyle 001}$. De même, il existe un arc allant du sommet ${\displaystyle 100}$ au sommet ${\displaystyle 000}$ car le suffixe de longueur 2 de ${\displaystyle 100}$ est égal au préfixe de longueur 2 de ${\displaystyle 000}$.

Le graphe ${\displaystyle B(n,1)}$ est formé de ${\displaystyle n}$ sommets, un pour chaque lettre. De chaque sommet partent ${\displaystyle n}$ arcs, il y a donc ${\displaystyle n^{2}}$ arcs.

• Chaque sommet d'un graphe ${\displaystyle B(k,n)}$ a degré sortant ${\displaystyle k}$ et degré entrant ${\displaystyle k}$.

• Le graphe ${\displaystyle B(k,n)}$ d'ordre ${\displaystyle n}$ est le line graph du graphe ${\displaystyle B(k,n-1)}$ d'ordre ${\displaystyle n-1}$ :

• Un graphe de de Bruijn est eulérien et hamiltonien.

• Les circuits eulériens de ${\displaystyle B(k,n-1)}$ et hamiltoniens de ${\displaystyle B(k,n)}$ se correspondent par la construction du line graph. Ces circuits sont des suites de de Bruijn.

On peut dessiner un graphe de de Bruijn binaire comme sur la partie gauche de la figure, de telle sorte qu'il ressemble à un objet de la théorie des systèmes dynamiques, comme l'attracteur de Lorenz affiché à droite.

Cette analogie s'explique simplement : le graphe de de Bruijn ${\displaystyle B(k,n)}$ est un modèle de décalage de Bernoulli

${\displaystyle x\mapsto kx\ {\bmod {\ }}1}$

Le décalage de Bernoulli, (aussi appelé la fonction 2x mod 1 ou fonction dyadique pour ${\displaystyle k=2}$) est un système dynamique ergodique que l'on peut voir comme un opérateur de décalage sur un nombre k-adique. Les trajectoires de ce système dynamique correspondent aux chemins dans le graphe de de Bruijn, avec la correspondance qui associe à chaque réel x de l'intervalle semi-ouvert [0,1[ le somme du graphe qui correspond aux n premiers chiffres dans la représentation de x en base k. De manière équivalente, les chemins dans le graphe de de Bruijn correspondent aux trajectoires d'un système dynamique de type fini.

• Les topologies de réseaux sont parfois des graphes de de Bruijn.
• Le protocole Koorde (en) de table de hachage distribuée utilise un graphe de de Bruijn.
• Les graphes de de Bruijn ont été utilisés en bioinformatique pour l'assemblage de fragments de lecture (reads) issues d'un séquençage[5] - [6] - [7].
• Compression de graphes de de Bruijn[8].