主題
Search

優美標號


GracefulGraphs

優美標號(或優美編號)是對具有 m 條邊的圖的特殊圖示記法,其中節點用從 0 到 m 的不同非負整數的子集標記,並且圖的邊用節點值之間的絕對差值標記。如果得到的圖的邊的編號從 1 到 m (包含 1 和 m),則該標記是優美標號,並且該圖被稱為優美圖

並非所有圖都具有優美標號;那些不具有優美標號的圖被稱為非優美的

上面展示了一些優美編號的圖。

頂點標籤必須包括 0 和 m。這是因為邊標籤必須包含 m,但從兩個頂點標籤(每個標籤都在 0 到 m 之間,包括 0 和 m)形成絕對差值 m 的唯一方法是其中一個為 0,另一個為 m。此外,出於同樣的原因,帶有標籤 0 和 m 的頂點必須相鄰。

如果標籤集合 (l_1,l_2,...,l_k) 形成圖的優美標號,那麼標籤 (m-l_1,m-l_2,...,m-l_k) 也形成優美標號。因此,除了單點圖 K_1 之外,所有優美圖都具有偶數個優美標號。

GracefulLabelingsS4

“根本不同的”或“本質上不同的”優美標號(參見 Gardner 1983, p. 164)指的是在減法互補和圖的對稱性(即圖自同構群)下不同的標號。考慮星圖 S_4=K_(1,3)。這裡有 12 個優美標號:((0, 1, 2, 3), (0, 1, 3, 2), (0, 2, 1, 3), (0, 2, 3, 1), (0, 3, 1, 2), (0, 3, 2, 1), (3, 0, 1, 2), (3, 0, 2, 1), (3, 1, 0, 2), (3, 1, 2, 0), (3, 2, 0, 1), 和 (3, 2, 1, 0)。正如從上圖清楚地看到的那樣,這些情況發生在中心為 0 或 3,其餘數字可以在尖端之間以任何方式排列時,給出 3!·2 種可能性(3! 用於解釋 3 個數字在尖端之間的可能排列,以及因子 2,因為這可以透過兩種方式完成:中心為 0 或中心為 3)。由於所有尖端透過圖的對稱性是等價的,並且交換 0 和 3 對應於減法互補,因此對於 S_4 存在唯一的根本優美標號。實際上,星圖 S_n 通常透過與上述類似的論證是唯一優美的

對於除了 K_1K_2=P_2 之外的圖,標號的總數 N_T 與圖 G 的根本不同的標號數 N_F 之間的關係為:

 N_F=(N_T)/(2|Aut(G)|),

其中 |Aut(G)|圖自同構群的階。例如,雖然二十面體圖存在大量的(5760 個)無限制的優美標號,但只有 24 個根本不同的標號(修正了 Gardner 1983, pp. 163-164 報告的 5 個計數)。

E. Weisstein 於 2020 年 4 月 3 日和 7 月 30 日計算了所有簡單圖在 n=1, 2, ..., 8 個節點上的所有(不僅僅是根本的)優美標號的總數。Knuth(2024,問題 97)給出了相應的根本不同的標號的總計數。這些計數,以及所有簡單圖的根本優美標號的總計數,在下表中給出。

OEIS所有在 n=1, 2, ... 個頂點上的標號總數總型別
A3337271, 2, 16, 144, 1428, 25328, 631026, 25087224, ...所有(不僅僅是根本的)優美標號
A3795761, 1, 2, 14, 174, 3655, 122439, 6470268, ...根本優美標號
A3795750, 1, 2, 13, 157, 3292, 110578, 5903888, ...沒有孤立點的圖的根本優美標號

優美標號可以使用稀疏標尺生成(參見 Pegg 2019)。

對於在 m 圖的邊上且沒有孤立點的圖,存在 m! 個優美標號,這對應於 (0,1,...,m-1)m! 種排列的 Lehmer 編碼(Sheppard 1976;Knuth 2024, p. 23),儘管其中一些對應於同一圖的備用標號。對於 m 條邊的非同構優美圖的數量,對於 m=1, 2, ... 分別是 1, 1, 3, 5, 12, 37, 112, 340, 1078, 3620, 12737, ... (OEIS A308544),而 連通優美圖在 m 條邊上的數量分別是 1, 1, 3, 5, 11, 28, 79, 227, 701, 2302, 8071, ... (OEIS A308545)。

Golomb 表明,連線偶數編號和奇數編號的節點集的圖的邊的數量是 |_(m+1)/2_|,其中 m圖的邊的數量。

下表總結了一些索引圖族的根本不同的優美標號的數量。Arumugam 和 Bagga (2011) 給出了迴圈圖 C_n 直到 n=24 的(總)計數,儘管 n=16 和 23 存在印刷錯誤。

類別OEIS計數
反稜柱圖 Ci_(2n)(1,2)A000000X, X, 1, 26, 20, ...
阿波羅尼安網路1, 33, ...
啞鈴圖X, X, 1, 0, 0, ...
書圖1, 16, 0, 417, ...
蜈蚣圖A0000001, 1, 4, 30, 232, 2058, 26654, ...
完全二部圖 K_(n,n)A3356191, 1, 1, 4, 1, 7, 2, 10, 3, 8, 1, 42, 2, 7, 7, ...
完全圖 K_n1, 1, 1, 1, 0, 0, 0, 0, 0, 0, ...
完全三部圖 K_(1,1,n)A0000001, 4, 7, 12, 20, 34, 74, 131, 260, ...
完全三部圖 K_(n,n,n)1, 1, 0, 0, 0, 0, 0, ...
皇冠圖 K_2 square K_n^_A0000000, 0, 0, 27, 69, X, 0, ...
圈圖 C_nA000000X, X, 1, 1, 0, 0, 6, 12, 0, 0, 104, 246, 0, 0, 3882, ...
雙稜錐圖X, X, 4, 1, 7, 0, 22, X, X, 0, ...
空圖 K^__n1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
齒輪圖A000000X, X, 34, 358, 6781, 231758, 10575203, 695507601, ...
網格圖 P_n square P_nA0000001, 1, 358, 47428572, ...
網格圖 P_n square P_n square P_n1, 27, ...
半立方體圖1, 1, 1, 0, ...
河內圖1, 140, ...
舵圖X, X, 109, 777, ...
超立方體圖 Q_nA0000001, 1, 27, 607173, ...
n×n 國王圖1, 1, 154, ...
n×n 騎士圖1, 0, 12, ...
梯子圖 P_2 square P_nA0000001, 1, 16, 177, 2242, 48068, ...
莫比烏斯梯子 M_nA000000X, X, 1, 34, 750, 8451, 208882, 5371997, 207664885, ...
平底鍋圖A000000X, X, X, 5, 8, 13, 30, 60, 160, 394, 924, 2434, 7178, 21446, ...
路徑補圖 P^__nA0000001, 0, 0, 1, 13, 34, 45, 18, 1, ...
路徑圖 P_nA0000001, 1, 1, 1, 2, 6, 8, 10, 30, 74, 162, 332, 800, 2478, 6398, 13980, ...
稜柱圖 P_2 square C_nA000000X, X, 4, 27, 444, ...
星圖 S_nA0000001, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
太陽圖A000000X, X, 0, 204, 4765, ...
小太陽圖A000000X, X, 9, 42, 255, 2283, 27361, ...
三角形蛇圖 TS_(2n-1)1, 1, 0, 0, 368, ...
網狀圖X, X, 894, ...
輪圖 W_nA000000X, X, 1, 4, 12, 23, 67, 251, 1842, 10792, ...

包含單個根本不同的優美標號(即,在圖自同構群下以及關於減法互補的唯一標號)的圖可以稱為唯一優美圖,並且具有最大可能數量的根本不同的標號(可能受制於一些附加條件,例如不具有孤立頂點)的圖可以稱為最大優美圖


另請參閱

優美圖, 優美排列, 標記圖, 最大優美圖, 非優美圖, 唯一優美圖

使用 探索

參考文獻

Arumugam, S. 和 Bagga, J. “優美標號演算法和複雜性——綜述。”J. Indonesian Math. Soc., 特刊, 1-9, 2011.Gardner, M. “數學遊戲:Solomon Golomb 的優美圖,或如何簡約地編號圖。”Sci. Amer. 226, No. 3, 108-113, 1972 年 3 月。Gardner, M. “Golomb 的優美圖。”Ch. 15 in Wheels, Life, and Other Mathematical Amusements. New York: W. H. Freeman, pp. 152-165, 1983.Golomb, S. W. “如何編號圖。”In Graph Theory and Computing (Ed. R. C. Read). New York: Academic Press, pp. 23-37, 1972.Knuth, D. E. §7.2.2.3 in The Art of Computer Programming, Vol. 4B: Combinatorial Algorithms, Part 2. New York: Addison-Wesley, 2022.Knuth, D. E. “優美標號。”§7.2.2.3 in The Art of Computer Programming, Vol. 4. Pre-Fascicle 7A, pp. 16-24, 2024 年 12 月 5 日。Pegg, E. Jr. “價為 k 的優美圖。”2019 年 8 月。 https://math.stackexchange.com/questions/3246000/graceful-graphs-with-valence-k.Sheppard, D. A. “平衡標記圖的階乘表示。”Discr. Math. 15, 379-388, 1976.Sloane, N. J. A. 序列 A308544, A333727, A379575, 和 A379576 在“整數序列線上百科全書”中。

引用為

Weisstein, Eric W. “優美標號。”來自 Web 資源。 https://mathworld.tw/GracefulLabeling.html

主題分類