www.wikidata.de-de.nina.az

Sterngraph Ein kurz Stern ist in der Graphentheorie eine Klasse von Graphen einfacher Struktur In einem ist ein zentrale

Sterngraph

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 Kanten werden mit oder bezeichnet. Eine Netzwerktopologie in Form eines Sterngraphen wird Stern-Topologie genannt.

Die Sterngraphen , , und

Definition Bearbeiten

Ein Sterngraph , auch -Stern genannt, ist ein ungerichteter Graph bestehend aus den Knoten

und den Kanten

wobei meist angenommen wird. Der Knoten wird Zentrum des Sterns, zentraler Knoten oder Sternknoten genannt. Gelegentlich wird ein Sterngraph mit Knoten auch mit bezeichnet.

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.
  • Ein Sterngraph ist ein vollständig bipartiter Graph , bei dem die eine Partitionsklasse aus dem zentralen Knoten und die andere Partitionsklasse aus den übrigen Knoten besteht.
  • Der Durchmesser ist zwei und der mittlere Abstand zwischen zwei Knoten mit etwas kleiner als zwei.
  • Der Kantengraph des Sterngraphen ist der vollständige Graph . Umgekehrt gibt es keinen Graphen, dessen Kantengraph ein Sterngraph mit mehr als drei Knoten ist.
  • 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 ist .
  • Jeder Sterngraph besitzt zwei graziöse Beschriftungen: bei der einen wird der zentrale Knoten mit , bei der anderen mit beschriftet; die übrigen Knoten erhalten jeweils die verbleibenden Zahlen zwischen und .
  • Die peripheren Knoten eines Sterngraphen bilden eine maximale stabile Menge des Graphen. Die Stabilitätszahl des Sterngraphen ist daher .

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-8176-4484-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

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 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 wahrend die anderen Knoten neben diesem zentralen Knoten keine weiteren Nachbarn besitzen Sterngraphen mit n displaystyle n Kanten werden mit S n displaystyle S n oder K 1 n displaystyle K 1 n bezeichnet Eine Netzwerktopologie in Form eines Sterngraphen wird Stern Topologie genannt Die Sterngraphen S 3 displaystyle S 3 S 4 displaystyle S 4 S 5 displaystyle S 5 und S 6 displaystyle S 6 Inhaltsverzeichnis 1 Definition 2 Eigenschaften 3 Siehe auch 4 Literatur 5 Einzelnachweise 6 WeblinksDefinition BearbeitenEin Sterngraph S n displaystyle S n nbsp auch n displaystyle n nbsp Stern genannt ist ein ungerichteter Graph V E displaystyle V E nbsp bestehend aus den n 1 displaystyle n 1 nbsp Knoten V v 0 v n displaystyle V v 0 ldots v n nbsp und den n displaystyle n nbsp Kanten E v 0 v 1 v 0 v 2 v 0 v n displaystyle E v 0 v 1 v 0 v 2 ldots v 0 v n nbsp wobei meist n 2 displaystyle n geq 2 nbsp angenommen wird Der Knoten v 0 displaystyle v 0 nbsp wird Zentrum des Sterns zentraler Knoten oder Sternknoten genannt Gelegentlich wird ein Sterngraph mit n 1 displaystyle n 1 nbsp Knoten auch mit S n 1 displaystyle S n 1 nbsp bezeichnet 1 Eigenschaften BearbeitenIm Folgenden werden nur Sterngraphen bestehend aus mindestens drei Knoten betrachtet Ein Sterngraph ist ein Baum also ein zusammenhangender azyklischer ungerichteter Graph ohne Mehrfachkanten Meist wird als Wurzel des Baums der zentrale Knoten gewahlt der Baum hat dann die Hohe eins 2 Ein Sterngraph ist ein vollstandig bipartiter Graph K 1 n displaystyle K 1 n nbsp bei dem die eine Partitionsklasse aus dem zentralen Knoten und die andere Partitionsklasse aus den ubrigen n displaystyle n nbsp Knoten besteht 3 Der Durchmesser ist zwei und der mittlere Abstand zwischen zwei Knoten mit 2 n n 1 displaystyle tfrac 2n n 1 nbsp etwas kleiner als zwei 4 Der Kantengraph des Sterngraphen S n displaystyle S n nbsp ist der vollstandige Graph K n displaystyle K n nbsp Umgekehrt gibt es keinen Graphen dessen Kantengraph ein Sterngraph mit mehr als drei Knoten ist 5 Die chromatische Zahl eines Sterngraphen ist zwei Eine zulassige Farbung erhalt man indem man den zentralen Knoten in einer Farbe und die ubrigen Knoten in der anderen Farbe farbt Das chromatische Polynom des Sterngraphen S n displaystyle S n nbsp ist l l 1 n displaystyle lambda lambda 1 n nbsp 6 Jeder Sterngraph besitzt zwei graziose Beschriftungen bei der einen wird der zentrale Knoten mit 0 displaystyle 0 nbsp bei der anderen mit n displaystyle n nbsp beschriftet die ubrigen Knoten erhalten jeweils die verbleibenden Zahlen zwischen 0 displaystyle 0 nbsp und n displaystyle n nbsp 7 Die peripheren Knoten eines Sterngraphen bilden eine maximale stabile Menge des Graphen Die Stabilitatszahl des Sterngraphen S n displaystyle S n nbsp ist daher n displaystyle n nbsp 8 Siehe auch BearbeitenKreisgraph Linearer Graph LeitergraphLiteratur BearbeitenPeter Tittmann Graphentheorie Eine anwendungsorientierte Einfuhrung 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 Einzelnachweise Bearbeiten Eric W Weisstein CRC Concise Encyclopedia of Mathematics 2 Auflage CRC Press 2010 S 2838 Wallis A Beginner s Guide to Graph Theory 2007 S 53 Tittmann Graphentheorie Eine anwendungsorientierte Einfuhrung 2003 S 23 Robert Sedgewick Kevin Wayne Kevin Wayne Einfuhrung in die Programmierung mit Java Pearson 2011 S 693 694 Tittmann Graphentheorie Eine anwendungsorientierte Einfuhrung 2003 S 69 Wallis A Beginner s Guide to Graph Theory 2007 S 94 Wallis A Beginner s Guide to Graph Theory 2007 S 126 Tittmann Graphentheorie Eine anwendungsorientierte Einfuhrung 2003 S 61 Weblinks BearbeitenEric W Weisstein Star Graph In MathWorld englisch Abgerufen von https de wikipedia org w index php title Sterngraph amp oldid 171195620