Graphe de de Bruijn

Un graphe de de Bruijn est un graphe orienté qui permet de représenter les chevauchements de longueur ${\displaystyle n-1}$ entre tous les mots de longueur ${\displaystyle 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^[1]. Les graphes ont déjà été décrits antérieurement, notamment par Camille Flye Sainte-Marie en 1894^[2] et par Irving J. Good en 1946^[3],[4].

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

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^{[réf. souhaitée]}.
• 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].

• Portail des mathématiques
• Portail de l'informatique théorique