www.wikidata.de-de.nina.az

Kreisgraph Ein kurz Kreis ist in der Graphentheorie eine Klasse von Graphen einfacher Struktur Ein besitzt immer gleich

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 Bearbeiten

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 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 81-224-1737-X.
  • Walter D. Wallis: A Beginner's Guide to Graph Theory. 2. Auflage. Springer, 2007, ISBN 0-8176-4484-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

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 displaystyle n Knoten werden mit C n displaystyle C n bezeichnet Eine Netzwerktopologie in Form eines Kreisgraphen wird Ring Topologie genannt Die Kreisgraphen C 3 displaystyle C 3 C 4 displaystyle C 4 C 5 displaystyle C 5 und C 6 displaystyle C 6 Inhaltsverzeichnis 1 Definition 2 Eigenschaften 3 Siehe auch 4 Literatur 5 Einzelnachweise 6 WeblinksDefinition BearbeitenEin Kreisgraph C n displaystyle C n nbsp ist ein ungerichteter Graph V E displaystyle V E nbsp bestehend aus den n displaystyle n nbsp Knoten V v 1 v n displaystyle V v 1 ldots v n nbsp und den n displaystyle n nbsp Kanten E v 1 v 2 v 2 v 3 v n 1 v n v n v 1 displaystyle E v 1 v 2 v 2 v 3 ldots v n 1 v n v n v 1 nbsp wobei meist n 3 displaystyle n geq 3 nbsp angenommen wird Ein Kreisgraph mit n displaystyle n nbsp Knoten wird auch n displaystyle n nbsp Kreis oder n displaystyle n nbsp Zyklus genannt Eigenschaften BearbeitenIm Folgenden werden nur Kreisgraphen bestehend aus mindestens drei Knoten betrachtet Alle Kreisgraphen sind zusammenhangend planar zyklisch eulersch und hamiltonsch 1 Alle Kreisgraphen sind 2 regular das heisst jeder Knoten hat den Grad zwei 2 Der Kantengraph des Kreisgraphen C n displaystyle C n nbsp ist isomorph zu seinem Ausgangsgraph also wieder ein Kreisgraph mit n displaystyle n nbsp Knoten 3 Der Durchmesser und die Stabilitatszahl des Kreisgraphen C n displaystyle C n nbsp betragt n 2 displaystyle lfloor tfrac n 2 rfloor nbsp 4 Die chromatische Zahl des Kreisgraphen C n displaystyle C n nbsp ist zwei wenn n displaystyle n nbsp gerade ist und drei wenn n displaystyle n nbsp ungerade ist 5 Das chromatische Polynom des Kreisgraphen C n displaystyle C n nbsp ist 1 n l 1 l 1 n displaystyle 1 n lambda 1 lambda 1 n nbsp 6 Alle Kreisgraphen sind fur n 2 displaystyle n geq 2 nbsp zueinander homoomorph Eigenschaften spezieller Kreisgraphen sind Der Kreisgraph C 3 displaystyle C 3 nbsp ist ein spezieller Dreiecksgraph Der Kreisgraph C 4 displaystyle C 4 nbsp ist ein spezieller Gittergraph Der Kreisgraph C 5 displaystyle C 5 nbsp ist der bis auf Isomorphie eindeutige selbstkomplementare Graph mit 5 Knoten Der Kreisgraph C 6 displaystyle C 6 nbsp ist der kleinste regulare Graph der nicht stark regular ist Siehe auch BearbeitenLinearer Graph Sterngraph LeitergraphLiteratur BearbeitenPeter Tittmann Graphentheorie Eine anwendungsorientierte Einfuhrung 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 Bearbeiten Vasudev Graph theory with applications 2006 S 76 Vasudev Graph theory with applications 2006 S 50 Vasudev Graph theory with applications 2006 S 458 Tittmann Graphentheorie Eine anwendungsorientierte Einfuhrung 2003 S 35 60 Wallis A Beginner s Guide to Graph Theory 2007 S 94 Robert A Wilson Graphs Colourings and the Four Colour Theorem Oxford University Press 2002 S 101 Weblinks BearbeitenEric W Weisstein Cycle Graph In MathWorld englisch Abgerufen von https de wikipedia org w index php title Kreisgraph amp oldid 224144597