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 è composto a partire da un alfabeto di cardinalità e un numero intero . Il grafo possiede vertici che contengono tutte le sequenze di lunghezza (denominate sequenze di de Bruijn).
Sia l'alfabeto di simboli e sia il dizionario delle sequenze di de Bruijn di lunghezza .
L'insieme degli archi del grafo di de Bruijn è definito da .
Bibliografia
Altri progetti
Collegamenti esterni
Categoria:Digrafi Categoria:Famiglie di grafi Categoria:Teoria degli automi