Gráfico de Kautz

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

El gráfico de Kautz ${\displaystyle K_{M}^{N+1}}$tiene${\displaystyle (M+1)M^{N+1}}$bordes

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

Es natural etiquetar cada uno de esos bordes de ${\displaystyle K_{M}^{N+1}}$ como${\displaystyle s_{0}s_{1}\cdots s_{N+1}}$, lo que da lugar a una correspondencia biunívoca entre las aristas del grafo de Kautz. ${\displaystyle K_{M}^{N+1}}$ y vértices del grafo de Kautz ${\displaystyle K_{M}^{N+2}}$.

Los gráficos de Kautz están estrechamente relacionados con los gráficos de De Bruijn .

• Para un grado fijo${\displaystyle M}$y número de vértices${\displaystyle V=(M+1)M^{N}}$, el grafo de Kautz tiene el diámetro más pequeño de cualquier grafo dirigido posible con${\displaystyle V}$vértices y grado${\displaystyle M}$.
• Todos los grafos de Kautz tienen ciclos eulerianos . (Un ciclo euleriano es aquel que visita cada arista exactamente una vez; este resultado se deduce de que en los grafos de Kautz el grado de entrada es igual al grado de salida de cada nodo).
• Todos los grafos de Kautz tienen un ciclo hamiltoniano (Este resultado se deriva de la correspondencia descrita anteriormente entre las aristas del grafo de Kautz).${\displaystyle K_{M}^{N}}$y vértices del grafo de Kautz${\displaystyle K_{M}^{N+1}}$; un ciclo hamiltoniano en${\displaystyle K_{M}^{N+1}}$está dado por un ciclo euleriano en${\displaystyle K_{M}^{N}}$)
• Un título-${\displaystyle k}$El gráfico de Kautz tiene${\displaystyle k}$caminos disjuntos desde cualquier nodo${\displaystyle x}$a cualquier otro nodo${\displaystyle y}$.

El grafo de Kautz se ha utilizado como una topología de red para conectar procesadores en aplicaciones de computación de alto rendimiento y computación tolerante a fallos ^{[ 1 ]} : dicha red se conoce como una red de Kautz .

Este artículo incorpora material del gráfico de Kautz en PlanetMath , que está bajo la licencia Creative Commons Attribution/Share-Alike License .