Quelltext der Seite Graziöse Beschriftung

Eine '''graziöse Beschriftung''' eines [[Graph (Graphentheorie)|Graphen]] mit <math>e</math> Kanten ist eine Beschriftung der Knoten mit unterschiedlichen Zahlen zwischen 1 und <math>e+1</math>, sodass dadurch jede Kante eine eindeutige Beschriftung erhält. Die Beschriftung einer Kante ergibt sich als Differenz der Beschriftungen ihrer beiden Endknoten.<ref name="Vas2001">Virginia Vassilevska: ''Coding and Graceful Labeling of trees.'' SURF 2001. [http://www.cs.cmu.edu/~virgi/final1.ps PostScript].</ref> Ein Graph, für den eine solche Beschriftung existiert, wird '''graziöser Graph''' genannt. Gibt es zusätzlich eine Zahl <math>x</math>, sodass ein Knoten einer jeden Kante mit einer Zahl kleiner als <math>x</math> und der andere mit einer Zahl größer oder gleich <math>x</math> 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.<ref name="Ros1967">[[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.</ref>

Eines der [[Ungelöste Probleme der Mathematik|ungelösten Probleme der Mathematik]] ist die '''Graziöser-Baum-Vermutung''', der zufolge es für alle [[Baum (Graphentheorie)|Bäume]] eine graziöse Beschriftung gibt.

== Graziöse Graphen ==

Von einigen Klassen von Graphen ist bekannt, dass sie graziös sind. Ein Beispiel sind die [[Linearer Graph|linearen Graphen]]. Eine graziöse Beschriftung entsteht, wenn deren Knoten mit den Zahlen <math>1, n, 2, n-1, 3, n-2, \ldots</math> beschriftet werden.
:[[Datei:Graceful_labeling_of_linear_graphs.svg]]
Eine entsprechende graziöse Beschriftung für den linearen Graphen mit fünf Knoten zeigt die folgende Zeichnung.
:[[Datei:Graceful_labeling_of_P_5.svg]]

== Graphzerlegungen ==

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

== Einzelnachweise ==
<references />

[[Kategorie:Graphentheorie]]