imported>Aka: https, Kleinkram

2021-05-16T14:13:22Z

https, Kleinkram

Neue Seite

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-Graph]]en.

== 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 [[Eulerkreisproblem|Eulerkreise]]
* Alle Kautz-Graphen haben einen gerichteten [[Hamiltonscher Kreis|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.

== Weblinks ==
* [https://planetmath.org/?op=getobj&from=objects&id=8526 Kautz graph bei planetmath.org]

[[Kategorie:Gerichteter Graph]]

Kautz-Graph - Versionsgeschichte

imported>Aka: https, Kleinkram