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

中新社澳門3月17日電（記者鄭嘉偉）記者17日從澳門理工大學獲悉，該校研究團隊成功解開由著名電腦科學家高德納(Donald Knuth)於2011年提出的經典數學謎題。研究成果成功入選全球電腦科學領域頂尖學術會議－ACM-SIAM離散演算法研討會(SODA 2026)，填補了圖論與組合演算法領域的空白。

根據介紹，在澳門理工大學校長嚴肇基與應用科學學院院長林燦堂的指導下，該校副教授黃智謙聯同計算機應用技術博士研究生柳博文組成的研究團隊，提出首個完全圖生成樹的樞軸格雷碼(Pivot Gray code for spanning trees of complete graphs)，成功設計了高德納在其經典藝術解答》 Programming)中提出的公開習題－「有沒有簡單的格雷碼把完全圖K_n的所有n^{n-2}個生成樹列出來？」。此習題被評為難度46分(滿分50)，被視為圖論與組合演算法領域最具挑戰性的謎題之一。

該校研究團隊設計了一種簡單且高效的遞歸演算法，其特點是列出的每兩個相鄰生成樹之間僅有一條邊發生變化，成功產生完全圖生成樹的格雷碼。同時，研究團隊提出了一種嶄新的方式來證明凱萊公式(Cayley's formula)，即完全圖的生成樹數量為n^{n-2}，研究成果具有創新性與實用價值。

編輯：聞兵