Graziöse Beschriftung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Eine graziöse Beschriftung eines Graphen mit e Kanten ist eine Beschriftung der Knoten mit unterschiedlichen Zahlen zwischen 1 und e+1, sodass dadurch jede Kante eine eindeutige Beschriftungen erhält. Die Beschriftung einer Kante ergibt sich als Differenz der Beschriftungen ihrer beiden Endknoten.[1] Ein Graph, für den eine solche Beschriftung existiert, wird graziöser Graph genannt. Gibt es zusätzlich eine Zahl x, sodass ein Knoten einer jeden Kante mit einer Zahl kleiner als x und der andere mit einer Zahl größer oder gleich x beschriftet ist, dann handelt es sich um eine bipartite Beschriftung.

Die Bezeichnung graziöse Beschriftung geht zurück auf Solomon W. Golomb. Ursprünglich verwendete Alexander Rosa die Bezeichnung β-Bewertung in seinem 1967 veröffentlichten Aufsatz über Graphenbeschriftungen. Bipartite Beschriftungen nannte er α-Bewertungen.[2]

Eines der ungelösten Probleme der Mathematik ist die Graziöser-Baum-Vermutung, der zufolge es für alle Bäume eine graziöse Beschriftung gibt.

Graziöse Graphen[Bearbeiten]

Von einigen Klassen von Graphen ist bekannt, dass sie graziös sind. Ein Beispiel sind die linearen Graphen. Eine graziöse Beschriftung entsteht, wenn deren Knoten mit den Zahlen 1, n, 2, n-1, 3, n-2, \ldots beschriftet werden.

Graceful labeling of linear graphs.svg

Ein entsprechende graziöse Beschriftung für den linearen Graphen mit fünf Knoten zeigt die folgende Zeichnung.

Graceful labeling of P 5.svg

Graphzerlegungen[Bearbeiten]

Ausgangspunkt für die Betrachtung graziöser Graphen war die Untersuchung von Graphzerlegungen. Ein vollständiger Graph K_{2m+1} lässt sich zyklisch in 2m+1 Kopien eines graziösen Graphen mit m Kanten zerlegen, siehe dazu auch Ringel-Kotzig-Vermutung.

Einzelnachweise[Bearbeiten]

  1. Virginia Vassilevska: Coding and Graceful Labeling of trees. SURF 2001. PostScript
  2. Alexander Rosa: On certain valuations of the vertices of a graph. In: Theory of Graphs. International Symposium. Théorie des graphes. Journées internationales d'étude. Rome, juillet 1966. Gordon and Breach, New York und Dunod Paris, 1967, S. 349–355