- Kautz-Graph
-
Der Kautz-Graph
ist ein Digraph (gerichteter Graph) vom Grad M und Dimension N + 1 mit (M + 1)MN Ecken. Die Ecken sind bezeichnet mit allen möglichen Zeichenketten
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 (
für
).
Der Kautz-Graph
hat (M + 1)MN + 1 gerichtete Kanten
Normalerweise markiert man diese Kanten von
mit
, wodurch man eine 1:1-Entsprechung zwischen Kanten des Kautz-Graphen
und Ecken des Kautz-Graphen
erhält.
Kautz-Graphen sind eng verwandt mit De-Bruijn-Graphen.
Eigenschaften
- Für festen Grad M und Anzahl der Ecken V = (M + 1)MN 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
Wikimedia Foundation.