Kreisgraph

Die
Kreisgraphen
,
,
und 
Ein Kreisgraph, kurz Kreis, ist in der Graphentheorie eine
Klasse von Graphen
einfacher Struktur. Ein Kreisgraph besitzt immer gleich viele Knoten wie Kanten,
wobei alle Knoten im Kreis
miteinander verbunden sind. Kreisgraphen mit
Knoten werden mit
bezeichnet. Eine Netzwerktopologie
in Form eines Kreisgraphen wird Ring-Topologie genannt.
Definition
Ein Kreisgraph
ist ein ungerichteter
Graph
bestehend aus den
Knoten
und den
Kanten
,
wobei meist
angenommen wird. Ein Kreisgraph mit
Knoten wird auch
-Kreis
oder
-Zyklus
genannt.
Eigenschaften
Im Folgenden werden nur Kreisgraphen bestehend aus mindestens drei Knoten betrachtet.
- Alle Kreisgraphen sind zusammenhängend, planar, zyklisch, eulersch und hamiltonsch.
- Alle Kreisgraphen sind 2-regulär, das heißt jeder Knoten hat den Grad zwei.
- Der Kantengraph
des Kreisgraphen
ist isomorph zu seinem Ausgangsgraph, also wieder ein Kreisgraph mit
Knoten.
- Der Durchmesser
und die Stabilitätszahl
des Kreisgraphen
beträgt
.
- Die chromatische
Zahl des Kreisgraphen
ist zwei, wenn
gerade ist und drei, wenn
ungerade ist.
- Das chromatische
Polynom des Kreisgraphen
ist
.
- Alle Kreisgraphen sind für
zueinander homöomorph.
Eigenschaften spezieller Kreisgraphen sind:
- Der Kreisgraph
ist ein spezieller Dreiecksgraph.
- Der Kreisgraph
ist ein spezieller Gittergraph.
- Der Kreisgraph
ist der kleinste reguläre Graph, der nicht stark regulär ist.
Literatur
- Peter Tittmann: Graphentheorie: Eine anwendungsorientierte Einführung. Hanser Verlag, 2003, ISBN 3-446-22343-6.



© biancahoegel.de
Datum der letzten Änderung: Jena, den: 14.10. 2020