Gráfico de Kautz

El gráfico de Kautz es un gráfico dirigido de grado y dimensión , que tiene vértices etiquetados por todas las posibles cadenas de longitud que se componen de caracteres elegidos de un alfabeto que contiene símbolos distintos, sujeto a la condición de que los caracteres adyacentes en la cadena no pueden ser iguales ( ) .${\displaystyle K_{M}^{N+1}}$${\ estilo de visualización M}$${\ estilo de visualización N+1}$${\ estilo de visualización (M + 1) M ^ {N}}$${\displaystyle s_{0}\cdots s_{N}}$${\ estilo de visualización N+1}$${\ estilo de visualización s_ {i}}$${\ estilo de visualización A}$${\ estilo de visualización M + 1}$${\displaystyle s_{i}\neq s_{i+1}}$

El gráfico de Kautz tiene aristas${\displaystyle K_{M}^{N+1}}$${\ estilo de visualización (M+1)M^{N+1}}$

${\displaystyle \{(s_{0}s_{1}\cdots s_{N},s_{1}s_{2}\cdots s_{N}s_{N+1})|\;s_{i}\ en A\;s_{i}\neq s_{i+1}\}\,}$

Ejemplo de gráfico de Kautz en 3 caracteres con longitud de cadena 2 (a la izquierda) y 3 (a la derecha); los bordes de la izquierda corresponden a los vértices de la derecha.