Graphe de de Bruijn
# 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 $1946^,.$

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.

## 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 kx\ {\bmod {\ }}1$

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 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^,^,.$
* Compression de graphes de de Bruijn.
