Sterne-

Kersten Ebert April 6, 2016 S 9 0
FONT SIZE:
fontsize_dec
fontsize_inc

In der Graphentheorie, ist ein Stern Sk der vollständige bipartite Graph K1, k: ein Baum mit einem internen Knoten und k Blättern. Alternativ können einige Autoren definieren Sk um den Baum der Ordnung k mit maximalen Durchmesser 2 sein; wobei in diesem Fall einen Stern von k & gt; 2 verfügt über k - 1 Blätter.

Ein Stern mit 3 Kanten wird als eine Klaue.

Der Stern Sk ist flanken anmutig, wenn k gerade und nicht, wenn k ungerade ist. Es ist Rand-transitive stick Graphen und hat Durchmesser 2, Umfang ∞, chromatische Index k und chromatische Zahl 2. Darüber hinaus hat der Stern große Automorphismengruppe, nämlich die symmetrische Gruppe auf k Buchstaben.

Sternen kann auch als die einzigen zusammenhängenden Graphen, in denen höchstens einer Ecke Grad größer als eins beschrieben werden.

Verhältnis zu anderen Graphen Familien

Claws zeichnen sich in der Definition von Klauenfreie Grafiken, Diagramme, keine Klaue als Untergraphen haben. Sie sind auch einer der Ausnahmefällen der Whitney Graphisomorphie Satz: im allgemeinen Graphen mit isomorph Liniendiagramme sind selbst isomorph, mit der Ausnahme von der Klaue und dem Dreieck K3.

Ein Stern ist eine besondere Art von Baum. Wie bei jedem Baum kann Sternen durch einen Prüfer Sequenz kodiert werden; die Prüfer-Code für einen Stern K1, k besteht aus k - 1 Kopien von der Mitte Scheitel.

Mehrere Grapheninvarianten werden in Form von Sternen festgelegt. Sterne Arborizität ist die minimale Anzahl der Wälder, die eine graphische Darstellung kann in solche unterteilt, dass jeder Baum in jeder Gesamtstruktur ist ein Stern, und der Stern chromatische Zahl eines Graphen ist die minimale Anzahl von Farben benötigt, um seine Ecken so zu färben, dass alle zwei Farbklassen bilden zusammen einen Untergraphen, in denen alle angeschlossenen Komponenten sind Sterne. Die Graphen der branchwidth 1 sind genau die Graphen in welchem ​​jede verbundene Komponente ein Stern ist.

Andere Anwendungen

Der Satz von Abständen zwischen den Scheitelpunkten von einer Klaue ist ein Beispiel einer endlichen metrischen Raum, der nicht isometrisch in einem euklidischen Raum jeder Dimension eingebettet werden können.

Der Stern-Netzwerk, ein Computernetzwerk nach dem Sterne-Graphen modelliert, ist in verteilten Rechen wichtig.

Eine geometrische Realisierung des Sterns Graph, durch die Identifizierung der Ränder mit Abstand von einigen festen Länge gebildet werden, wird als lokales Modell von Kurven in der tropischen Geometrie verwendet. Eine tropische Kurve definiert ist, um ein metrischer Raum, die lokal isomorph zu einem sternförmigen metrischen Graphen sein.

  Like 0   Dislike 0
Vorherige Artikel Der Prophet von Ephesus
Nächster Artikel Opendocument-Standardisierung
Bemerkungen (0)
Keine Kommentare

Fügen Sie einen Kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Zeichen übrig: 3000
captcha