8
\$\begingroup\$

A Graceful Graph is a type of Simple Graph. Graceful graphs are special because there is a way to label all their nodes with positive integers so that when the edges are also labeled with the differences of the nodes they connect, no two edges have the same label and every label up to the number of edges is used.

Worked Out Example

Here is a Simple graph that we suspect is a Graceful graph

Simple Graph

Let us try the following labeling:

Labeled

Note we are permitted to skip integers in our node labeling. Now we label every edge with the positive difference between the nodes it connects. For increased visibility I have labeled these in red.

Doubly labeled

Each edge has a unique number and no number between between 1 and 7 (the number of edges we have) is left out. Thus our graph is graceful.

Task

Given a graph, via any reasonable method of input, output a truthy value if it is graceful and a falsy value otherwise.

This is so the objective is to minimize your byte count.

Test Cases

Here graphs are represented as an array of edges:

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
\$\endgroup\$
  • \$\begingroup\$ I think algorithms to check gracefulness are only known for certain classes of graphs (e.g. trees) \$\endgroup\$ – ngenisis Feb 17 '17 at 2:56
  • 2
    \$\begingroup\$ @ngenisis It can certainly be brute forced. There are more efficient algorithms for certain classes but you can use restraints on the edge sizes to create a maximum node label difference. \$\endgroup\$ – Wheat Wizard Feb 17 '17 at 3:00
  • \$\begingroup\$ [(0,1),(1,2),(2,3),(3,4)] is probably a noteworthy edge case. \$\endgroup\$ – Dennis Feb 17 '17 at 4:03
  • \$\begingroup\$ Unless I'm missing something, graphs of the form {(k-1,k) : 0 < k < n} require the highest labels of all graphs with the same number of nodes. \$\endgroup\$ – Dennis Feb 17 '17 at 4:16
  • \$\begingroup\$ @Dennis Oh yes. That is certainly true they should require n(n+1)/2 as their highest label. I have added your test case. \$\endgroup\$ – Wheat Wizard Feb 17 '17 at 4:19
6
\$\begingroup\$

Jelly, 12 bytes

FSŒ!ị@€ḅ-AċJ

Takes an array of edges as 1-indexed node pairs.

Try it online! (Horrendously inefficient. Don't bother with the actual test cases.)

How it works

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.
\$\endgroup\$
  • 2
    \$\begingroup\$ ḅ- is one of my favorite Jelly tricks :-) \$\endgroup\$ – ETHproductions Feb 17 '17 at 15:07
4
\$\begingroup\$

Mathematica, 121 116 bytes

Edit: Saved 5 bytes thanks to JungHwan Min and Martin Ender

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

Explanation

enter image description here

Pure function which takes a Mathematica Graph object with vertices {1, 2, ..., k} for some nonnegative integer k. In the worst case, we will only need vertex labels ranging from 1 to 1 + (1 + 2 + ... EdgeCount@#). Since it saves us some bytes later, we will let e be the list of edges and n be the list {1, 2, ..., EdgeCount@#}, so the vertex weights will be drawn from Range[1+Tr[n=Range@Length[e=EdgeList@#]]]. We generate a list of all Tuples of length VertexCount@#, then we choose the Cases which give graceful labelings and check to see that the result is Unequal to the empty list {}. Gracefulness of the list of vertex weights w is checked by Mapping the function Abs[#-#2]&@@w[[List@@#]]& over the list of edges e, Sorting the result, and checking whether the result is Equal to n. Here is a breakdown of that function:

               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. 
\$\endgroup\$
  • 1
    \$\begingroup\$ save a byte by messing with some precedence: VertexCount[#]->VertexCount@# \$\endgroup\$ – JungHwan Min Feb 17 '17 at 4:45
  • 1
    \$\begingroup\$ Btw, the Tr trick for Length no longer saves bytes if you need to add parentheses. Length[e=EdgeList@#] is the same length. But it's shorter to avoid that altogether and rewrite the triangular number there as Tr@Range@EdgeCount@# (and then replace e at the end with EdgeList@#. Second, the function operator rarely saves bytes, in this case I think it's shorter to use Cases instead of Select and then w_/; instead of w. \$\endgroup\$ – Martin Ender Feb 17 '17 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.