澳門理工大學團隊解開高德納經典數學謎題 填補圖論與組合演算法空白

記者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}，研究成果具有創新性與實用價值。

中新社澳門電 記者 鄭嘉偉