Graphe de de Bruijn
Un graphe de de Bruijn est un graphe orienté qui permet de représenter les chevauchements de longueur  entre tous les mots de longueur  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  d'ordre  sur un alphabet  à  lettres est construit comme suit. Les sommets de  sont en bijection avec (sont étiquetés par) les  mots de longueur  sur . Si  et  sont deux sommets,
il y a un arc de  à  si le mot obtenu en supprimant la première lettre de  est le même que le mot obtenu en supprimant la dernière lettre de ; en d'autres termes, s'il existe deux lettres  et , et un mot , tels que  et . La présence d'un arc signifie donc un chevauchement maximal entre deux mots de même longueur.

Exemples 

Le graphe  ci-contre est construit sur un alphabet binaire  pour des mots de longueur . Les  mots de longueur 3 sur l'alphabet binaire sont :
.
Il existe par exemple un arc allant du sommet  au sommet  car le suffixe de longueur 2 de  est égal au préfixe de longueur 2 de . De même, il existe un arc allant du sommet  au sommet  car le suffixe de longueur 2 de  est égal au préfixe de longueur 2 de .

Le graphe  est formé de  sommets, un pour chaque lettre. De chaque sommet partent  arcs, il y a donc  arcs.

Propriétés 

 Chaque sommet d'un graphe  a degré sortant  et degré entrant .

 Le graphe  d'ordre  est le line graph du graphe  d'ordre  :

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

 Les circuits eulériens de  et hamiltoniens de  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  est un modèle de décalage de Bernoulli

Le décalage de Bernoulli, (aussi appelé la fonction 2x mod 1 ou fonction dyadique pour ) 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  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 () issues d'un séquençage.
 Compression de graphes de de Bruijn.

Notes et références 
}}

De Bruijn
De Bruijn
Suite de nombres