Gráfico de Kautz

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.

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 están compuestas por 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}}$ ${\displaystyle M}$ ${\displaystyle N+1}$ ${\displaystyle (M+1)M^{N}}$ ${\displaystyle s_{0}\cdots s_{N}}$ ${\displaystyle N+1}$ ${\displaystyle s_{i}}$ ${\displaystyle A}$ ${\displaystyle M+1}$ ${\displaystyle s_{i}\neq s_{i+1}}$

El gráfico de Kautz tiene aristas ${\displaystyle K_{M}^{N+1}}$ ${\displaystyle (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}\in A\;s_{i}\neq s_{i+1}\}\,}$

Es natural etiquetar cada uno de estos bordes como , dando una correspondencia uno a uno entre los bordes del gráfico de Kautz y los vértices del gráfico de Kautz . ${\displaystyle K_{M}^{N+1}}$ ${\displaystyle s_{0}s_{1}\cdots s_{N+1}}$ ${\displaystyle K_{M}^{N+1}}$ ${\displaystyle K_{M}^{N+2}}$

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

Propiedades

• Para un grado y número fijo de vértices , el grafo de Kautz tiene el diámetro más pequeño de cualquier grafo dirigido posible con vértices y grado . ${\displaystyle M}$ ${\displaystyle V=(M+1)M^{N}}$ ${\displaystyle V}$ ${\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 porque los grafos de Kautz tienen un grado de entrada igual al grado de salida para cada nodo)
• Todos los grafos de Kautz tienen un ciclo hamiltoniano (este resultado se desprende de la correspondencia descrita anteriormente entre los bordes del grafo de Kautz y los vértices del grafo de Kautz ; un ciclo hamiltoniano en está dado por un ciclo euleriano en ) ${\displaystyle K_{M}^{N}}$ ${\displaystyle K_{M}^{N+1}}$ ${\displaystyle K_{M}^{N+1}}$ ${\displaystyle K_{M}^{N}}$
• Un gráfico de grado Kautz tiene caminos disjuntos desde cualquier nodo a cualquier otro nodo . ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle x}$ ${\displaystyle y}$

En informática

El gráfico 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 red Kautz .

Notas

1. Li, Dongsheng; Xicheng Lu; Jinshu Su (2004). "Análisis de teoría de grafos de la topología de Kautz y los esquemas DHT". Computación en red y paralela: Conferencia internacional IFIP . Wuhan, China: NPC. págs. 308–315. ISBN 3-540-23388-1. Consultado el 5 de marzo de 2008 .

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