澳门理工大学团队解开高德纳经典数学谜题 填补图论与组合算法空白

记者17日从澳门理工大学获悉，该校研究团队成功解开由著名电脑科学家高德纳(Donald Knuth)于2011年提出的经典数学谜题。研究成果成功入选全球计算机科学领域顶级学术会议——ACM-SIAM离散算法研讨会(SODA 2026)，填补了图论与组合算法领域的空白。

据介绍，在澳门理工大学校长严肇基与应用科学学院院长林灿堂的指导下，该校副教授黄智谦联同计算机应用技术博士研究生柳博文组成的研究团队，提出首个完全图生成树的枢轴格雷码(Pivot Gray code for spanning trees of complete graphs)，成功解答了高德纳在其经典巨著《电脑程序设计艺术》(The Art of Computer Programming)中提出的公开习题——“有没有简单的格雷码把完全图K_n的所有 n^{n-2}个生成树列出来？”。该习题被评为难度46分(满分50)，被视为图论与组合算法领域最具挑战性的谜题之一。

该校研究团队设计了一种简单高效的递归算法，其特点是列出的每两个相邻生成树之间仅有一条边发生变化，成功生成完全图生成树的格雷码。同时，研究团队提出了一种崭新的方式来证明凯莱公式(Cayley's formula)，即完全图的生成树数量为n^{n-2}，研究成果具有创新性与实用价值。

中新社澳门电 记者 郑嘉伟