Graceful Trees: Statistics and Algorithms
Graceful Trees: Statistics and Algorithms
复制标题
优雅的树：统计和算法
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
M. Horton
中科院分区：
文献类型：
--
作者：
M. Horton
优美树猜想是图论中的一个问题，可以追溯到1967年。它建议n个结点上的每一棵树都可以用整数[1..n]来标号，这样当用它们的端点节点标号之间的差值标号时，边可以唯一地标号为整数[1..n-1]。到目前为止，还没有找到这个猜想的证明或反证，但所有多达28个顶点的树都被证明是优雅的。这个猜想还导致了有效地寻找树的优美标号的算法设计中的一个问题。本文描述了一种新的优美标号算法，并用它证明了29个顶点上的所有树都是优美的。还对优雅的树木标签比例的统计趋势进行了研究。这些趋势提供了有力的补充证据，证明每棵树都是优雅的。
The Graceful Tree Conjecture is a problem in graph theory that dates back to 1967. It suggests that every tree on n nodes can be labelled with the integers [1..n] such that the edges, when labelled with the difference between their endpoint node labels, are uniquely labelled with the integers [1..n-1]. To date, no proof or disproof of the conjecture has been found, but all trees with up to 28 vertices have been shown to be graceful. The conjecture also leads to a problem in algorithm design for efficiently finding graceful labellings for trees. In this thesis, a new graceful labelling algorithm is described and used to show that all trees on 29 vertices are graceful. A study is also made of statistical trends in the proportion of tree labellings that are graceful. These trends offer strong additional evidence that every tree is graceful.