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=\{s_1,\dots ,s_m\}$ l'alfabeto di simboli e sia $S^n=V=\{(s_1,\dots ,s_1),(s_1,\dots ,s_2),\dots ,(s_m,\dots ,s_m)\}$ il dizionario delle sequenze di de Bruijn di lunghezza $n$.

L'insieme degli archi del grafo di de Bruijn è definito da $E=\{((v_1,v_2,\dots ,v_m),(v_2,\dots ,v_m,s_i)):i=1,\dots ,m\}$.

Bibliografia

• Template:Cita pubblicazione
• Template:Cita libro

Collegamenti esterni

• Template:Collegamenti esterni
• Template:FOLDOC