Kautz-Graph

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

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

$\{(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 $K_{M}^{N+1}$ mit $s_{0}s_{1}\cdots s_{N+1}$, wodurch man eine 1:1-Entsprechung zwischen Kanten des Kautz-Graphen $K_{M}^{N+1}$ und Ecken des Kautz-Graphen $K_{M}^{N+2}$ erhält.

Kautz-Graphen sind eng verwandt mit De-Bruijn-Graphen.

Eigenschaften

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