Graphe de de Bruijn

Un graphe de de Bruijn est un graphe orienté qui permet de représenter les chevauchements de longueur $n-1$ entre tous les mots de longueur $n$ sur un alphabet donné. Les graphes sont nommés ainsi d'après le mathématicien Nicolaas Govert de Bruijn qui les a décrits en 1946. Les graphes ont déjà été décrits antérieurement, notamment par Camille Flye Sainte-Marie en 1894 et par Irving J. Good en 1946Modèle:,.

Le graphe de de Bruijn $B(k,n)$ d'ordre $n$ sur un alphabet $A$ à $k$ lettres est construit comme suit. Les sommets de $B(k,n)$ sont en bijection avec (sont étiquetés par) les $k^n$ mots de longueur $n$ sur $A$. Si $u$ et $v$ sont deux sommets, il y a un arc de $u$ à $v$ si le mot obtenu en supprimant la première lettre de $u$ est le même que le mot obtenu en supprimant la dernière lettre de $v$; en d'autres termes, s'il existe deux lettres $a$ et $b$, et un mot $x$, tels que $u=ax$ et $v=xb$. La présence d'un arc signifie donc un chevauchement maximal entre deux mots de même longueur.

Graphe de de Bruijn $B(2,3)$ construit sur l'alphabet binaire ($k=2$) pour des mots de longueur $n=3$.

Exemples

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

$000,001,010,011,111,110,101,100$.

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

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

Propriétés

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

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

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

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

Systèmes dynamiques

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 $B(k,n)$ est un modèle de décalage de Bernoulli

$x\mapsto kxmod1$

Le décalage de Bernoulli, (aussi appelé la fonction 2x mod 1 ou fonction dyadique pour $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.

Utilisation

• Les topologies de réseaux sont parfois des graphes de de BruijnModèle:Refsou.
• Le protocole Modèle:Lien 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 (Modèle:Lang) issues d'un séquençageModèle:,Modèle:,.
• Compression de graphes de de Bruijn.