Kreisgraph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Die Kreisgraphen C_3, C_4, C_5 und C_6

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 n Knoten werden mit C_n bezeichnet. Eine Netzwerktopologie in Form eines Kreisgraphen wird Ring-Topologie genannt.

Definition[Bearbeiten]

Ein Kreisgraph C_n ist ein ungerichteter Graph (V,E) bestehend aus den n Knoten

V=\{ v_1, \ldots , v_n \}

und den n Kanten

E=\{ \{ v_1, v_2 \}, \{ v_2, v_3 \}, \ldots , \{ v_{n-1}, v_n \}, \{ v_n, v_1 \} \},

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

Eigenschaften[Bearbeiten]

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

Eigenschaften spezieller Kreisgraphen sind:

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

  •  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 8-122-41737-X.
  •  Walter D. Wallis: A Beginner's Guide to Graph Theory. 2. Auflage. Springer, 2007, ISBN 0-817-64484-9.

Einzelnachweise[Bearbeiten]

  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[Bearbeiten]