Grafo di de Bruijn
{{S|teoria dei grafi}}
[[File:De bruijn graph-for binary sequence of order 4.svg|thumb|Grafo di de Bruijn (2, 3)]]
Un '''grafo di de Bruijn''' è un tipo di [[digrafo (matematica)|digrafo]] utilizzato nella [[teoria dei sistemi]] e in [[bioinformatica]].

Scoperto in maniera indipendente da [[Nicolaas Govert de Bruijn|de Bruijn]] e [[Irving John Good|Good]], un grafo <math>dB(m, n)</math> è composto a partire da un [[alfabeto (teoria dei linguaggi formali)|alfabeto]] di [[cardinalità]] <math>m</math> e un numero intero <math>n</math>. Il grafo possiede <math>m^n</math> [[vertice (teoria dei grafi)|vertici]] che contengono tutte le sequenze di lunghezza <math>n</math> (denominate sequenze di de Bruijn).

Sia <math>S = \left \{ s_1, \ldots, s_m \right \}</math> l'alfabeto di simboli e sia <math>S^{n} = V =  \left \{ (s_1, \ldots, s_1), (s_1, \ldots, s_2), \ldots, (s_m, \ldots, s_m) \right \}</math> il dizionario delle sequenze di de Bruijn di lunghezza <math>n</math>.

L'insieme degli [[arco (teoria dei grafi)|archi]] del grafo di de Bruijn è definito da <math>E = \left \{ \left ( (v_1, v_2, \ldots, v_m), (v_2, \ldots, v_m, s_i) \right ) : i = 1, \ldots, m \right \}</math>.

== Bibliografia ==
* {{cita pubblicazione|nome=Anthony|cognome=Ralston|titolo=De Bruijn Sequences-A Model Example of the Interaction of Discrete Mathematics and Computer Science|url=https://archive.org/details/sim_mathematics-magazine_1982-05_55_3/page/131|rivista=Mathematics Magazine|volume=55|numero=3|mese=maggio|anno=1982|pp=131-143|doi=10.2307/2690079}}
* {{cita libro|nome=Michel|cognome=Raynal|capitolo=De Bruijn Graphs|titolo=Distributed Algorithms for Message-Passing Systems|url=https://archive.org/details/distributedalgor00rayn|editore=Springer|anno=2013|pp=[https://archive.org/details/distributedalgor00rayn/page/73 73]-75|ISBN=978-3-642-38122-5|doi=10.1007/978-3-642-38123-2}}

== Altri progetti ==
{{interprogetto|preposizione=sul}}

== Collegamenti esterni ==
* {{Collegamenti esterni}}
* {{FOLDOC|De Bruijn graph|De Bruijn graph}}

{{portale|matematica}}

[[Categoria:Digrafi]]
[[Categoria:Famiglie di grafi]]
[[Categoria:Teoria degli automi]]