digraf de De Brujin

m

Matemàtiques

digraf de De Brujin

Digraf B(d,D) que té per conjunt de vèrtexs totes les paraules de longitud D que es poden formar amb els d símbols diferents d’un alfabet i tal que una paraula és adjacent respecte a una altra si la primera sense el símbol inicial és igual a la segona sense el símbol final.

El digraf de De Bruijn és un digraf eulerià, d-regular, que té d elevat a D + 1 arcs. Els digrafs de De Bruijn són útils en el disseny de grans xarxes d’interconnexió.