de.wikipedia.org

Sterngraph – Wikipedia

Die Sterngraphen {\displaystyle S_{3}}, {\displaystyle S_{4}}, {\displaystyle S_{5}} und {\displaystyle S_{6}}

Ein Sterngraph, kurz Stern, ist in der Graphentheorie eine Klasse von Graphen einfacher Struktur. In einem Sterngraph ist ein zentraler Knoten mit allen anderen Knoten durch Kanten verbunden, während die anderen Knoten neben diesem zentralen Knoten keine weiteren Nachbarn besitzen. Sterngraphen mit {\displaystyle n} Kanten werden mit {\displaystyle S_{n}} oder {\displaystyle K_{1,n}} bezeichnet. Eine Netzwerktopologie in Form eines Sterngraphen wird Stern-Topologie genannt.

Ein Sterngraph {\displaystyle S_{n}}, auch {\displaystyle n}-Stern genannt, ist ein ungerichteter Graph {\displaystyle (V,E)} bestehend aus den {\displaystyle n+1} Knoten

{\displaystyle V=\{v_{0},\ldots ,v_{n}\}}

und den {\displaystyle n} Kanten

{\displaystyle E=\{\{v_{0},v_{1}\},\{v_{0},v_{2}\},\ldots ,\{v_{0},v_{n}\}\}},

wobei meist {\displaystyle n\geq 2} angenommen wird. Der Knoten {\displaystyle v_{0}} wird Zentrum des Sterns, zentraler Knoten oder Sternknoten genannt. Gelegentlich wird ein Sterngraph mit {\displaystyle n+1} Knoten auch mit {\displaystyle S_{n+1}} bezeichnet.[1]

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

  • Peter Tittmann: Graphentheorie: Eine anwendungsorientierte Einführung. Hanser Verlag, 2003, ISBN 3-446-22343-6.
  • Walter D. Wallis: A Beginner's Guide to Graph Theory. 2. Auflage. Springer, 2007, ISBN 0-8176-4484-9.
  1. ↑ Eric W. Weisstein: CRC Concise Encyclopedia of Mathematics. 2. Auflage. CRC Press, 2010, S. 2838.
  2. ↑ Wallis: A Beginner's Guide to Graph Theory. 2007, S. 53.
  3. ↑ Tittmann: Graphentheorie: Eine anwendungsorientierte Einführung. 2003, S. 23.
  4. ↑ Robert Sedgewick, Kevin Wayne, Kevin Wayne: Einführung in die Programmierung mit Java. Pearson, 2011, S. 693–694.
  5. ↑ Tittmann: Graphentheorie: Eine anwendungsorientierte Einführung. 2003, S. 69.
  6. ↑ Wallis: A Beginner's Guide to Graph Theory. 2007, S. 94.
  7. ↑ Wallis: A Beginner's Guide to Graph Theory. 2007, S. 126.
  8. ↑ Tittmann: Graphentheorie: Eine anwendungsorientierte Einführung. 2003, S. 61.