|
Size: 1619
Comment:
|
← Revision 6 as of 2013-02-02 03:46:41 ⇥
Size: 1679
Comment: Problem Description updated
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 7: | Line 7: |
| A graph (V,E) is called a graceful graph if its vertices V can be labelled with distinct unsigned integers, its edges E can be labelled with the absolute differences between vertex labels, and the edge labels are in the range {1..|E|}. The task is to determine the |
A graph (V,E) is called a graceful graph if its vertices V can be labelled with distinct integers from 0 to |E| such that, when each edge is labelled with the absolute difference between its vertex labels, the resulting edge labels are all distinct. The task is to determine the |
| Line 57: | Line 57: |
| * Feb 2nd, 2013 - Problem Description updated |
Graceful Graphs
Problem Description
A graph (V,E) is called a graceful graph if its vertices V can be labelled with distinct integers from 0 to |E| such that, when each edge is labelled with the absolute difference between its vertex labels, the resulting edge labels are all distinct. The task is to determine the existence of a graceful labelling of a graph.
Predicates
Input: edge/2
Output: value/2
Input format
The edges of the graph are provided by instances of the predicate edge/2.
Output format
If a graceful labelling exists, a witness containing vertex labels encoded in the predicate value/2 has to be provided. value(X,I) means the vertex X is labelled with the unsigned integer I.
Example(s)
The example encodes a clique with 3 nodes:
edge(a,b). edge(b,c). edge(c,a).
It is graceful. An assignment of the values 0, 1, and 3 to the nodes provides a graceful labelling.
Thus, the output of the solver should look like:
value(a,0). value(b,1). value(c,3).
Other graceful labellings are also possible.
Additional sample instances: download
Problem Peculiarities
Type: Search Competition: Both Complexity: NP
Notes and Updates
- Feb 2nd, 2013 - Problem Description updated
Author(s)
- Author: Christian Drescher
- Affiliation: NICTA, University of New South Wales, Australia