Graziöse Beschriftung
Eine graziöse Beschriftung eines Graphen mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} Kanten ist eine Beschriftung der Knoten mit unterschiedlichen Zahlen zwischen 1 und , 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} , sodass ein Knoten einer jeden Kante mit einer Zahl kleiner als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} und der andere mit einer Zahl größer oder gleich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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
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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1, n, 2, n-1, 3, n-2, \ldots} beschriftet werden.
Eine entsprechende graziöse Beschriftung für den linearen Graphen mit fünf Knoten zeigt die folgende Zeichnung.
Graphzerlegungen
Ausgangspunkt für die Betrachtung graziöser Graphen war die Untersuchung von Graphzerlegungen. Ein vollständiger Graph lässt sich zyklisch in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2m+1} Kopien eines graziösen Graphen mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} Kanten zerlegen, siehe dazu auch Ringel-Kotzig-Vermutung.
Einzelnachweise
- ↑ Virginia Vassilevska: Coding and Graceful Labeling of trees. SURF 2001. PostScript
- ↑ 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
