Problembeschreibung

Bei Graceful geht es darum, für einen Graphen ein graceful (schönes, hübsches) Labeling zu finden. Ein Labeling ist eine Abbildung von der Menge der Knoten in die Menge der natürlichen Zahlen.
Ein Labeling ist graceful, wenn gilt:

• Das kleinste Label ist die Zahl 0.
• Das grösste Label ist die Zahl $e$, wobei $e$ die Anzahl der Kanten ist
• Wenn sich das Label einer Kante als Absolutwert der Differenz der beiden durch die Kante verbundenen Knoten definiert,
  • muss das kleinste Label die Zahl 1 sein und
  • die Menge der Label muss gleich der Menge {1,2,..,e} sein.