1073
Comment: Graceful Graphs added
|
1412
Example added
|
Deletions are marked like this. | Additions are marked like this. |
Line 2: | Line 2: |
<<TableOfContents>> |
|
Line 13: | Line 11: |
The edges of the graph are provided by instances of the predicate edge/2. 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. |
|
Line 26: | Line 20: |
The edges of the graph are provided by instances of the predicate {{{edge/2}}}. | |
Line 29: | Line 24: |
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. |
|
Line 31: | Line 29: |
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. |
Graceful Graphs
Problem Description
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 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.
Problem Peculiarities
Type: Search Competition: Both Complexity: NP
Notes and Updates
Author(s)
- Author: Christian Drescher
- Affiliation: NICTA, University of New South Wales, Australia