Ein anmutiger Graph ist eine Art einfacher Graph . Anmutige Diagramme sind etwas Besonderes, da es eine Möglichkeit gibt, alle ihre Knoten mit positiven Ganzzahlen zu kennzeichnen, sodass, wenn die Kanten auch mit den Unterschieden der Knoten gekennzeichnet sind, die sie verbinden, keine zwei Kanten dieselbe Beschriftung und jede Beschriftung bis zur Anzahl der Kanten haben wird genutzt.

Ausgearbeitetes Beispiel

Hier ist ein einfaches Diagramm, von dem wir vermuten, dass es ein anmutiges Diagramm ist

Versuchen wir die folgende Kennzeichnung:

Beachten Sie, dass wir Ganzzahlen in unserer Knotenbeschriftung überspringen dürfen. Jetzt beschriften wir jede Kante mit dem positiven Unterschied zwischen den Knoten, die sie verbindet. Zur besseren Sichtbarkeit habe ich diese rot beschriftet.

Jede Kante hat eine eindeutige Nummer und es wird keine Nummer zwischen 1 und 7 (die Anzahl der Kanten, die wir haben) ausgelassen. Somit ist unser Graph anmutig.

Aufgabe

Bei einem gegebenen Diagramm wird über eine vernünftige Eingabemethode ein wahrheitsgemäßer Wert ausgegeben, wenn er anmutig ist, und ansonsten ein falscher Wert.

Dies ist Code-Golf, daher besteht das Ziel darin, die Anzahl Ihrer Bytes zu minimieren.

Testfälle

Hier werden Diagramme als Array von Kanten dargestellt:

3 nodes:

[(0,1),(0,2),(1,2)]

True

Labeling:

Node 0 -> 0
Node 1 -> 2
Node 2 -> 3

5 nodes:

[(0,1),(0,4),(1,2),(2,3),(3,4)]

False

5 nodes:

[(0,1),(1,2),(2,3),(3,4)]

True

Labeling:

Node 0 -> 0
Node 1 -> 1
Node 2 -> 3
Node 3 -> 6
Node 4 -> 10

9 nodes

[(0,1),(1,2),(1,7),(1,8),(2,3),(2,6),(3,4),(4,5)]

True

Labeling:

Node 0 -> 0
Node 1 -> 1
Node 2 -> 3
Node 3 -> 6
Node 4 -> 10
Node 5 -> 15
Node 6 -> 11
Node 7 -> 7
Node 8 -> 8

5 nodes

[(0,1),(0,2),(1,2),(1,3),(1,4),(3,4)]

False

Gelee , 12 Bytes

FSŒ!ị@€ḅ-AċJ

Nimmt ein Array von Kanten als 1-indizierte Knotenpaare.

Probieren Sie es online aus! (Schrecklich ineffizient. Kümmern Sie sich nicht um die eigentlichen Testfälle.)

Wie es funktioniert

FSŒ!ị@€ḅ-AċJ  Main link. Argument: A (array of pairs)

FS            Flatten and sum, yielding s. This is an upper bound for the labels
              a graceful labeling (if one exists) would require.
  Œ!          Take all permutations of [1, ..., s].
      €       For each permutation P:
    ị@          Replace each integer in A with the element of P at that index.
       ḅ-     Convert all pairs from base -1 to integer, mapping (a,b) to b-a.
         A    Take absolute values.
           J  Yield the indices of A, i.e., [1, ..., len(A)].
          ċ   Count the occurrences of [1, ..., len(A)] in the result to the left.

Mathematica, 121 116 Bytes

Bearbeiten: 5 Bytes dank JungHwan Min und Martin Ender gespeichert

Cases[Range[1+Tr[n=Range@Length[e=EdgeList@#]]]~Tuples~VertexCount@#,w_/;Sort[Abs[#-#2]&@@w[[List@@#]]&/@e]==n]!={}&

Erläuterung

Reine Funktion, die ein Mathematica- GraphObjekt mit Eckpunkten {1, 2, ..., k}für eine nichtnegative Ganzzahl verwendet k. Im schlimmsten Fall benötigen wir nur Scheitelpunktbeschriftungen von 1bis 1 + (1 + 2 + ... EdgeCount@#). Da wir später einige Bytes sparen, werden wir edie Liste der Kanten und ndie Liste sein {1, 2, ..., EdgeCount@#}, sodass die Scheitelpunktgewichte daraus gezogen werden Range[1+Tr[n=Range@Length[e=EdgeList@#]]]. Wir generieren eine Liste mit der gesamten TuplesLänge VertexCount@#, wählen dann die Liste mit Casesden richtigen Beschriftungen aus und prüfen, ob das Ergebnis Unequalin der leeren Liste enthalten ist {}. Gracefulness der Liste der Vertex - Gewichte wwird durch kontrolliert Mapping die Funktion Abs[#-#2]&@@w[[List@@#]]&über die Liste der Kanten e, Sorting das Ergebnis, und zu prüfen , ob das ErgebnisEqualzu n. Hier ist eine Aufschlüsselung dieser Funktion:

               List@@#     Replace the Head of the edge with List; i.e., UndirectedEdge[a,b] becomes {a,b}.
            w[[       ]]&  Select the corresponding vertex weights from the list w.
          @@               Replace the Head of that expression (List) with the function
Abs[#-#2]&                   which returns the absolute difference between its first two arguments.
                           This effectively passes the vertex weights into the absolute difference function.