优美树定理

1965年，Kotzig 推测所有树都是优美的（Bondy 和 Murty 1976；Knuth 2024，第 24 页）。尽管许多作者试图证明这一点，并且尽管“GTC 几乎肯定是正确的”（Knuth 2024，第 24 页），但迄今为止尚未发现任何证明或反驳。

由于具有个顶点的树有条边，因此所有 0 到的值都出现在其顶点的任何优美标号中。因此，边标签只能在所讨论的边与标签为 0 和的顶点关联时出现，这意味着顶点标签 0 和必须在优美标号中的相邻顶点出现（Hotron 2003，第 7 页）。 Nikoloski等人（2002）发现了一种使用三角表来识别和忽略此类情况的算法（Horton 2003，第 7 页）。

下表总结了定理已验证的顶点数的上限。

	参考文献
16	Rosa（1965；引用于 Knuth 2024，第 24 页）
27	Aldred 和 McKay (1998)
28	Horton (2003)
35

另请参阅

优美图, 优美标号, 极大优美树, 树

使用探索

更多尝试

参考文献

Aldred, R. E. L. 和 McKay, B. "树的优美和谐标号。" Bull. Inst. Combin. Appl. 23, 69-72, 1998.Bondy, J. A. 和 Murty, U. S. R. 图论及其应用。 纽约：North Holland, p. 248, 1976.Cahit, I. "所有完全二叉树都是优美的吗？" Amer. Math. Monthly 83, 35-37, 1976.Delorme, C.; Maheo, M.; Thuillier, H.; Koh, K. M.; 和 Teo, H. K. "带弦的环是优美的。" J. Graph Theory 4, 409-415, 1980.Gallian, J. A. "调查：图标记的最新结果、猜想和开放问题。" J. Graph Th. 13, 491-504, 1989.Gallian, J. "图标记的动态调查。" Elec. J. Combin. DS6. 2018 年 12 月 21 日。 https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Horton, M. "优美树：统计和算法。" 计算机荣誉学士论文。塔斯马尼亚大学，2003 年。 https://eprints.utas.edu.au/19/1/GracefulTreesStatisticsAndAlgorithms.pdf.Knuth, D. E. §7.2.2.3 in 计算机程序设计艺术，第 4B 卷：组合算法，第 2 部分。 纽约：Addison-Wesley, 2022.Nikoloski, Z.; Deo, N.; 和 Suraweera, F. "优美树的生成。" 在第 33 届东南国际组合数学、图论和计算会议。 2002.Seoud, M. A. 和 Wilson, R. J. "一些不优美的图。" Int. J. Math. Educ. Sci. Tech. 24, 435-441, 1993.Snevily, H. S. "关于优美树猜想的评论。" 预印本。谢立同和刘桂真. "优美树问题综述。" 曲阜师院学报 1, 8-15, 1984.

请引用为

Weisstein, Eric W. "优美树定理。" 来自 Web 资源。 https://mathworld.net.cn/GracefulTreeTheorem.html