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\ne s_{i+1}$ für $i=0,\dots ,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\ne 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