Kreisgraph

Graphentheorie

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

DefinitionBearbeiten

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.

EigenschaftenBearbeiten

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]
  • 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 bis auf Isomorphie eindeutige selbstkomplementäre Graph mit 5 Knoten.
  • Der Kreisgraph   ist der kleinste reguläre Graph, der nicht stark regulär ist.

Siehe auchBearbeiten

LiteraturBearbeiten

  • 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.

EinzelnachweiseBearbeiten

  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.

WeblinksBearbeiten