Kautz-Graph
Der Kautz-Graph <math>K_M^{N + 1}</math>, benannt nach William H. Kautz (* 1924), ist ein Digraph (gerichteter Graph) vom Grad <math>M</math> und Dimension <math>N + 1</math> mit <math>(M + 1)M^{N}</math> Ecken. Die Ecken sind bezeichnet mit allen möglichen Zeichenketten <math>s_0 \cdots s_N</math> der Länge <math>N + 1</math> aus Zeichen des Alphabets <math>A</math>, das <math>M + 1</math> unterschiedliche Symbole enthält, mit der Einschränkung, dass nebeneinander gelegene Zeichen in der Zeichenkette nicht gleich sein dürfen (<math>s_i \neq s_{i+1}</math> für <math>i = 0,\ldots,N-1</math>).
Der Kautz-Graph <math>K_M^{N + 1}</math> hat <math>(M + 1)M^{N+ 1}</math> gerichtete Kanten
<math>\{(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}\}</math>
Normalerweise markiert man diese Kanten von <math>K_M^{N + 1}</math> mit <math>s_0s_1 \cdots s_{N + 1}</math>, wodurch man eine 1:1-Entsprechung zwischen Kanten des Kautz-Graphen <math>K_M^{N + 1}</math> und Ecken des Kautz-Graphen <math>K_M^{N + 2}</math> erhält.
Kautz-Graphen sind eng verwandt mit De-Bruijn-Graphen.
Eigenschaften
- Für festen Grad <math>M</math> und Anzahl der Ecken <math>V = (M + 1) M^N</math> hat der Kautz-Graph den kleinsten möglichen Durchmesser eines gerichteten Graphen mit <math>V</math> Ecken und Grad <math>M</math>.
- Alle Kautz-Graphen haben gerichtete Eulerkreise
- Alle Kautz-Graphen haben einen gerichteten Hamiltonschen Kreis
- Ein Grad-<math>k</math> Kautz-Graph hat <math>k</math> unverbundene gerichtete Wege von beliebigem Knoten <math>x</math> zu beliebigem anderen Knoten <math>y</math>.
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.