Kautz-Graph

Der Kautz-Graph ${\displaystyle K_{M}^{N+1}}$, benannt nach William H. Kautz (* 1924), ist ein Digraph (gerichteter Graph) vom Grad ${\displaystyle M}$ und Dimension ${\displaystyle N+1}$ mit ${\displaystyle (M+1)M^{N}}$ Ecken. Die Ecken sind bezeichnet mit allen möglichen Zeichenketten ${\displaystyle s_{0}\cdots s_{N}}$ der Länge ${\displaystyle N+1}$ aus Zeichen des Alphabets ${\displaystyle A}$, das ${\displaystyle M+1}$ unterschiedliche Symbole enthält, mit der Einschränkung, dass nebeneinander gelegene Zeichen in der Zeichenkette nicht gleich sein dürfen (${\displaystyle s_{i}\neq s_{i+1}}$ für ${\displaystyle i=0,\ldots ,N-1}$).

Der Kautz-Graph ${\displaystyle K_{M}^{N+1}}$ hat ${\displaystyle (M+1)M^{N+1}}$ gerichtete Kanten

${\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}\}}$

Normalerweise markiert man diese Kanten von ${\displaystyle K_{M}^{N+1}}$ mit ${\displaystyle s_{0}s_{1}\cdots s_{N+1}}$, wodurch man eine 1:1-Entsprechung zwischen Kanten des Kautz-Graphen ${\displaystyle K_{M}^{N+1}}$ und Ecken des Kautz-Graphen ${\displaystyle K_{M}^{N+2}}$ erhält.

Kautz-Graphen s​ind eng verwandt m​it De-Bruijn-Graphen.

Eigenschaften

• Für festen Grad ${\displaystyle M}$ und Anzahl der Ecken ${\displaystyle V=(M+1)M^{N}}$ hat der Kautz-Graph den kleinsten möglichen Durchmesser eines gerichteten Graphen mit ${\displaystyle V}$ Ecken und Grad ${\displaystyle M}$.
• Alle Kautz-Graphen haben gerichtete Eulerkreise
• Alle Kautz-Graphen haben einen gerichteten Hamiltonschen Kreis
• Ein Grad-${\displaystyle k}$ Kautz-Graph hat ${\displaystyle k}$ unverbundene gerichtete Wege von beliebigem Knoten ${\displaystyle x}$ zu beliebigem anderen Knoten ${\displaystyle y}$.

Literatur

• W. H. Kautz: Bounds on directed (d,k) graphs, Theory of cellular logic networks and machines, AFCRL-68-0668 SRI Project 7258 Final report, 1968, S. 20–28
• W. H. Kautz: Design of optimal interconnection networks for multiprocessors, Architecture and design of digital computers, Nato Advanced Summer Institute, 1969, S. 249–272.

Weblinks

• Kautz graph bei planetmath.org