Graphique de De Bruijn - De Bruijn graph

Dans la théorie des graphes , un graphe de De Bruijn à dimension de symboles est un graphe orienté représentant des chevauchements entre des séquences de symboles. Il a des sommets , constitués de toutes les séquences de longueur possibles des symboles donnés ; le même symbole peut apparaître plusieurs fois dans une séquence. Pour un ensemble de symboles , l'ensemble des sommets est : ${\style d'affichage n}$${\style d'affichage m}$${\style d'affichage m^{n}}$ ${\style d'affichage n}$${\style d'affichage m}$${\displaystyle S=\{s_{1},\dots ,s_{m}\}}$

$${\displaystyle V=S^{n}=\{(s_{1},\dots ,s_{1},s_{1}),(s_{1},\dots ,s_{1},s_{2 }),\dots ,(s_{1},\dots ,s_{1},s_{m}),(s_{1},\dots ,s_{2},s_{1}),\dots ,( s_{m},\dots ,s_{m},s_{m})\}.}$$

Si l'un des sommets peut être exprimé comme un autre sommet en décalant tous ses symboles d'une place vers la gauche et en ajoutant un nouveau symbole à la fin de ce sommet, alors ce dernier a une arête dirigée vers le sommet précédent. Ainsi, l'ensemble des arcs (c'est-à-dire des arêtes dirigées) est

$${\displaystyle E=\{((t_{1},t_{2},\dots ,t_{n}),(t_{2},\dots ,t_{n},s_{j})):t_ {i}\in S,1\leq i\leq n,1\leq j\leq m\}.}$$

Bien que les graphes de De Bruijn portent le nom de Nicolaas Govert de Bruijn , ils ont été découverts indépendamment par De Bruijn et IJ Good . Bien plus tôt, Camille Flye Sainte-Marie utilisait implicitement leurs propriétés.

Propriétés

• Si alors la condition pour deux sommets quelconques formant une arête reste vide, et donc tous les sommets sont connectés formant un total d' arêtes.${\style d'affichage n=1}$${\style d'affichage m^{2}}$
• Chaque sommet a exactement des arêtes entrantes et sortantes.${\style d'affichage m}$${\style d'affichage m}$
• Chaque graphe de De Bruijn de dimension est le digraphe linéaire du graphe de De Bruijn de dimension avec le même ensemble de symboles.${\style d'affichage n}$${\style d'affichage (n-1)}$
• Chaque graphe de De Bruijn est eulérien et hamiltonien . Les cycles d'Euler et les cycles hamiltoniens de ces graphes (équivalents les uns aux autres via la construction du graphe linéaire) sont des suites de De Bruijn .

La construction du graphique linéaire des trois plus petits graphiques binaires de De Bruijn est illustrée ci-dessous. Comme on peut le voir dans l'illustration, chaque sommet du graphe de De Bruijn -dimensionnel correspond à une arête du graphe de De Bruijn -dimensionnel, et chaque arête du graphe de De Bruijn -dimensionnel correspond à un chemin à deux arêtes dans le graphe -dimensionnel Graphique de De Bruijn. ${\style d'affichage n}$${\style d'affichage (n-1)}$${\style d'affichage n}$${\style d'affichage (n-1)}$

Systèmes dynamiques

Les graphes binaires de De Bruijn peuvent être dessinés de telle manière qu'ils ressemblent à des objets de la théorie des systèmes dynamiques , tels que l' attracteur de Lorenz :

Graphique de De Bruijn binaire

attracteur de Lorenz

Cette analogie peut être rigoureuse: le -dimensionnelle graphique -symbol De Bruijn est un modèle de la carte Bernoulli${\style d'affichage n}$${\style d'affichage m}$

$${\displaystyle x\mapsto mx\ {\bmod {\ }}1.}$$

La carte de Bernoulli (également appelée carte 2x mod 1 pour ) est un système dynamique ergodique , qui peut être compris comme un simple décalage d'un nombre m- adique . Les trajectoires de ce correspondent de système dynamique de promenades dans le graphique De Bruijn, où la correspondance est donnée en mettant en correspondance chaque réel dans l'intervalle au sommet correspondant aux premiers chiffres du fond - représentation de . De manière équivalente, les marches dans le graphe de De Bruijn correspondent à des trajectoires dans un sous- shift unilatéral de type fini . ${\style d'affichage m=2}$${\style d'affichage x}$${\style d'affichage [0,1)}$${\style d'affichage n}$${\style d'affichage m}$${\style d'affichage x}$

Graphes orientés de deux séquences B  (2, 3) de Bruijn et d'une séquence B  (2, 4). Dans B(2,3). chaque sommet est visité une fois, alors que dans B (2,4), chaque arête est traversée une fois.

Des plongements ressemblant à celui-ci peuvent être utilisés pour montrer que les graphes binaires de De Bruijn ont le numéro de file d' attente 2 et qu'ils ont une épaisseur de livre au plus 5.

Les usages

• Certaines topologies de réseau en grille sont des graphes de De Bruijn.
• Le protocole de table de hachage distribué Koorde utilise un graphe de De Bruijn.
• En bioinformatique , les graphes de De Bruijn sont utilisés pour l' assemblage de novo de lectures de séquençage dans un génome .

Voir également

• De Bruijn tore
• Graphique de Hamming
• graphique de Kautz

Les références

Liens externes

• Weisstein, Eric W. "De Bruijn Graph" . MathWorld .
• Tutoriel sur l'utilisation des graphes De Bruijn en bioinformatique par Homolog.us