| Copyright | Copyright (C) 2021 Yoo Chung |
|---|---|
| License | GPL-3.0-or-later |
| Maintainer | dev@chungyc.org |
| Safe Haskell | Safe-Inferred |
| Language | GHC2021 |
Problems.P92
Description
Part of Ninety-Nine Haskell Problems. Some solutions are in Solutions.P92.
Documentation
gracefulTree :: G -> Maybe (Map Vertex Int) Source #
It has been conjectured that if graph \(G=(V,E)\) is a tree with \(n\) vertexes, which necessarily means that it has \(n-1\) edges, then there is a graceful labeling of the tree. This means that there is a way to label each vertex with integers from 1 to \(n\) such that for every integer \(m\) from 1 to \(n-1\), there is an edge whose difference in vertex labels is \(m\). I.e., there is a bijection \(l : V \rightarrow \{ k \,|\, 1 \leq k \leq n \}\) such that \(\{ |l(v)-l(v')| \,|\, \{v,v'\} \in E \} = \{ k \,|\, 1 \leq k \leq n-1 \}\). There is no known counterexample, but neither is it proven that this is true for all trees.
For example, the following is a graceful labeling of the tree graph tree92:
Write a function which will gracefully label a tree graph.
If there is no graceful labeling for a particular tree,
return Nothing, and write up the counterexample for publication.
Examples
>>>gracefulTree tree92Just (fromList [(1,5),(2,2),(3,1),(4,7),(5,3),(6,6),(7,4)])
>>>gracefulTree tree92'Just (fromList [(1,1),(2,10),(3,7),(4,3),(5,5),(6,6),(7,14),(8,13),(9,12),...
Notes
Problem 92 in the original list referred to this conjecture as "Von Koch's conjecture". However, I could not find any reference confirming that von Koch actually made this conjecture. From the style the problem was written in, it seems likely this was an imaginary scenario to make the problem feel more personal and fun, rather than something which actually happened.
It is too unbelievable for me to have met the mathematician in question, so this was rewritten to a more dry presentation.
Tree graph used for the example in gracefulTree.
A 14-vertex tree graph to try gracefulTree on.
