digraf de Kautz

m

Matemàtiques

digraf de Kautz

Fototeca.cat

Digraf K(d, D) que té per conjunt de vèrtexs el de totes les paraules de longitud D que es poden formar amb els d + 1 símbols diferents d’un alfabet, de manera que dos símbols consecutius sempre siguin diferents.

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 Kautz K(d,D) té diàmetre D.