Kreisgraph

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.

Die Kreisgraphen , , und

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 n​ur Kreisgraphen bestehend a​us mindestens d​rei 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]
  • Der Kantengraph des Kreisgraphen ist isomorph zu seinem Ausgangsgraph, also wieder ein Kreisgraph mit Knoten.[3]
  • Der Durchmesser und die Stabilitätszahl des Kreisgraphen beträgt .[4]
  • Die chromatische Zahl des Kreisgraphen ist zwei, wenn gerade ist und drei, wenn ungerade ist.[5]
  • Das chromatische Polynom des Kreisgraphen ist .[6]
  • 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.

Siehe auch

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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.