主題
Search

優美樹定理


1965年,Kotzig 推測所有都是優美的(Bondy 和 Murty 1976;Knuth 2024,第 24 頁)。 儘管許多作者試圖證明這一點,並且儘管“GTC 幾乎肯定是正確的”(Knuth 2024,第 24 頁),但迄今為止尚未發現任何證明或反駁。

由於具有 n 個頂點的m=n-1 條邊,因此所有 0 到 m-1 的值都出現在其頂點的任何優美標號中。 因此,邊標籤 m-1 只能在所討論的邊與標籤為 0 和 m-1 的頂點關聯時出現,這意味著頂點標籤 0 和 m-1 必須在優美標號中的相鄰頂點出現(Hotron 2003,第 7 頁)。 Nikoloski等人(2002)發現了一種使用三角表來識別和忽略此類情況的演算法(Horton 2003,第 7 頁)。

下表總結了定理已驗證的頂點數 n 的上限。

n參考文獻
16Rosa(1965;引用於 Knuth 2024,第 24 頁)
27Aldred 和 McKay (1998)
28Horton (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.tw/GracefulTreeTheorem.html

主題分類