Kautz-Graph

Der Kautz-Graph $K_M^{N + 1}$ 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_0s_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.

Weblinks

• Kautz graph bei planetmath.org