Grafo di de Bruijn

Grafo di de Bruijn (2, 3)

Un grafo di de Bruijn è un tipo di digrafo utilizzato nella teoria dei sistemi e in bioinformatica.

Scoperto in maniera indipendente da de Bruijn e Good, un grafo $dB(m,n)$ è composto a partire da un alfabeto di cardinalità $m$ e un numero intero $n$. Il grafo possiede $m^{n}$ vertici che contengono tutte le sequenze di lunghezza $n$ (denominate sequenze di de Bruijn).

Sia $S=\left\{s_{1},\ldots ,s_{m}\right\}$ l'alfabeto di simboli e sia $S^{n}=V=\left\{(s_{1},\ldots ,s_{1}),(s_{1},\ldots ,s_{2}),\ldots ,(s_{m},\ldots ,s_{m})\right\}$ il dizionario delle sequenze di de Bruijn di lunghezza $n$.

L'insieme degli archi del grafo di de Bruijn è definito da $E=\left\{\left((v_{1},v_{2},\ldots ,v_{m}),(v_{2},\ldots ,v_{m},s_{i})\right):i=1,\ldots ,m\right\}$.

Bibliografia

• Anthony Ralston, De Bruijn Sequences-A Model Example of the Interaction of Discrete Mathematics and Computer Science, in Mathematics Magazine, vol. 55, n. 3, maggio 1982, pp. 131-143, DOI:10.2307/2690079.
• Michel Raynal, De Bruijn Graphs, in Distributed Algorithms for Message-Passing Systems, Springer, 2013, pp. 73-75, DOI:10.1007/978-3-642-38123-2, ISBN 978-3-642-38122-5.

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sul grafo di de Bruijn

Collegamenti esterni

• (EN) Eric W. Weisstein, Grafo di de Bruijn, su MathWorld, Wolfram Research.
• (EN) De Bruijn graph, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL