Kreisgraph

Ein Kreisgraph, kurz Kreis, ist in der Graphentheorie ein Graph mit einfacher Struktur. Ein Kreisgraph besitzt immer gleich viele Knoten und Kanten, wobei alle Knoten im Kreis miteinander verbunden sind. Kreisgraphen mit ${\displaystyle n}$ Knoten werden mit ${\displaystyle C_{n}}$ bezeichnet. Eine Netzwerktopologie in Form eines Kreisgraphen wird Ring-Topologie genannt.

Die Kreisgraphen ${\displaystyle C_{3}}$, ${\displaystyle C_{4}}$, ${\displaystyle C_{5}}$ und ${\displaystyle C_{6}}$

Definition

Ein Kreisgraph ${\displaystyle C_{n}}$ ist ein ungerichteter Graph ${\displaystyle (V,E)}$ bestehend aus den ${\displaystyle n}$ Knoten

${\displaystyle V=\{v_{1},\ldots ,v_{n}\}}$

und den ${\displaystyle n}$ Kanten

${\displaystyle E=\{\{v_{1},v_{2}\},\{v_{2},v_{3}\},\ldots ,\{v_{n-1},v_{n}\},\{v_{n},v_{1}\}\}}$,

wobei meist ${\displaystyle n\geq 3}$ angenommen wird. Ein Kreisgraph mit ${\displaystyle n}$ Knoten wird auch ${\displaystyle n}$-Kreis oder ${\displaystyle n}$-Zyklus genannt.

Eigenschaften

Im Folgenden werden nur Kreisgraphen bestehend aus mindestens drei Knoten betrachtet.

• Alle Kreisgraphen sind zusammenhängend, planar, zyklisch, eulersch und hamiltonsch.^[1]
• Alle Kreisgraphen sind 2-regulär, das heißt jeder Knoten hat den Grad zwei.^[2]
• Alle Kreisgraphen haben die Baumweite zwei.
• Der Kantengraph des Kreisgraphen ${\displaystyle C_{n}}$ ist isomorph zu seinem Ausgangsgraph, also wieder ein Kreisgraph mit ${\displaystyle n}$ Knoten.^[3]
• Der Durchmesser und die Stabilitätszahl des Kreisgraphen ${\displaystyle C_{n}}$ beträgt ${\displaystyle \lfloor {\tfrac {n}{2}}\rfloor }$.^[4]
• Die chromatische Zahl des Kreisgraphen ${\displaystyle C_{n}}$ ist zwei, wenn ${\displaystyle n}$ gerade ist und drei, wenn ${\displaystyle n}$ ungerade ist.^[5]
• Das chromatische Polynom des Kreisgraphen ${\displaystyle C_{n}}$ ist ${\displaystyle (-1)^{n}(\lambda -1)+(\lambda -1)^{n}}$.^[6]
• Alle Kreisgraphen sind für ${\displaystyle n\geq 2}$ zueinander homöomorph.

Eigenschaften spezieller Kreisgraphen sind:

• Der Kreisgraph ${\displaystyle C_{3}}$ ist ein spezieller Dreiecksgraph.
• Der Kreisgraph ${\displaystyle C_{4}}$ ist ein spezieller Gittergraph.
• Der Kreisgraph ${\displaystyle C_{5}}$ ist der bis auf Isomorphie eindeutige selbstkomplementäre Graph mit 5 Knoten.
• Der Kreisgraph ${\displaystyle C_{6}}$ ist der kleinste reguläre Graph, der nicht stark regulär ist.

Siehe auch

• Linearer Graph
• Sterngraph
• Leitergraph

Literatur

• Peter Tittmann: Graphentheorie: Eine anwendungsorientierte Einführung. Hanser Verlag, 2003, ISBN 3-446-22343-6.
• C. Vasudev: Graph theory with applications. New Age International, 2006, ISBN 81-224-1737-X.
• Walter D. Wallis: A Beginner's Guide to Graph Theory. 2. Auflage. Springer, 2007, ISBN 0-8176-4484-9.

Einzelnachweise

1. Vasudev: Graph theory with applications. 2006, S. 76.
2. Vasudev: Graph theory with applications. 2006, S. 50.
3. Vasudev: Graph theory with applications. 2006, S. 458.
4. Tittmann: Graphentheorie: Eine anwendungsorientierte Einführung. 2003, S. 35,60.
5. Wallis: A Beginner's Guide to Graph Theory. 2007, S. 94.
6. Robert A. Wilson: Graphs, Colourings and the Four-Colour Theorem. Oxford University Press, 2002, S. 101.

Weblinks

• Eric W. Weisstein: Cycle Graph. In: MathWorld (englisch).