Sterngraph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Die Sterngraphen S_3, S_4, S_5 und S_6

Ein Sterngraph, kurz Stern, ist in der Graphentheorie ein 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 n Kanten werden mit S_n oder K_{1,n} bezeichnet. Eine Netzwerktopologie in Form eines Sterngraphen wird Stern-Topologie genannt.

Definition[Bearbeiten]

Ein Sterngraph S_n, auch n-Stern genannt, ist ein ungerichteter Graph (V,E) bestehend aus den n+1 Knoten

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

und den n Kanten

E=\{ \{ v_0, v_1 \}, \{ v_0, v_2 \}, \ldots , \{ v_0, v_n \} \},

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

Eigenschaften[Bearbeiten]

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

  • Ein Sterngraph ist ein Baum, also ein zusammenhängender azyklischer ungerichteter Graph ohne Mehrfachkanten. Meist wird als Wurzel des Baums der zentrale Knoten gewählt; der Baum hat dann die Höhe eins.[2]
  • Ein Sterngraph ist ein vollständig bipartiter Graph K_{1,n}, bei dem die eine Partitionsklasse aus dem zentralen Knoten und die andere Partitionsklasse aus den übrigen n Knoten besteht.[3]
  • Der Durchschnittsgrad der Knoten in einem Sterngraphen ist zwei, der Durchmesser ist ebenfalls zwei und der mittlere Abstand zwischen zwei Knoten mit \tfrac{2n}{n+1} etwas kleiner als zwei.[4]
  • Der Kantengraph des Sterngraphen S_n ist der vollständige Graph K_n. Umgekehrt gibt es keinen Graphen, dessen Kantengraph ein Sterngraph mit mehr als drei Knoten ist.[5]
  • Die chromatische Zahl eines Sterngraphen ist zwei. Eine zulässige Färbung erhält man, indem man den zentralen Knoten in einer Farbe und die übrigen Knoten in der anderen Farbe färbt. Das chromatische Polynom des Sterngraphen S_n ist \lambda (\lambda-1)^n.[6]
  • Jeder Sterngraph besitzt zwei graziöse Beschriftungen: bei der einen wird der zentrale Knoten mit 0, bei der anderen mit n beschriftet; die übrigen Knoten erhalten jeweils die verbleibenden Zahlen zwischen 0 und n.[7]
  • Die peripheren Knoten eines Sterngraphen bilden eine maximale stabile Menge des Graphen. Die Stabilitätszahl des Sterngraphen S_n ist daher n.[8]

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

  •  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-817-64484-9.

Einzelnachweise[Bearbeiten]

  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.

Weblinks[Bearbeiten]