優美標號(或優美編號)是對具有 條邊的圖的特殊圖示記法,其中節點用從 0 到
的不同非負整數的子集標記,並且圖的邊用節點值之間的絕對差值標記。如果得到的圖的邊的編號從 1 到
(包含 1 和 m),則該標記是優美標號,並且該圖被稱為優美圖。
並非所有圖都具有優美標號;那些不具有優美標號的圖被稱為非優美的。
上面展示了一些優美編號的圖。
頂點標籤必須包括 0 和 。這是因為邊標籤必須包含
,但從兩個頂點標籤(每個標籤都在 0 到
之間,包括 0 和 m)形成絕對差值
的唯一方法是其中一個為 0,另一個為
。此外,出於同樣的原因,帶有標籤 0 和
的頂點必須相鄰。
如果標籤集合 形成圖的優美標號,那麼標籤
也形成優美標號。因此,除了單點圖
之外,所有優美圖都具有偶數個優美標號。
“根本不同的”或“本質上不同的”優美標號(參見 Gardner 1983, p. 164)指的是在減法互補和圖的對稱性(即圖自同構群)下不同的標號。考慮星圖 。這裡有 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,因為這可以透過兩種方式完成:中心為 0 或中心為 3)。由於所有尖端透過圖的對稱性是等價的,並且交換 0 和 3 對應於減法互補,因此對於
存在唯一的根本優美標號。實際上,星圖
通常透過與上述類似的論證是唯一優美的。
對於除了 和
之外的圖,標號的總數
與圖
的根本不同的標號數
之間的關係為:
其中 是圖自同構群的階。例如,雖然二十面體圖存在大量的(5760 個)無限制的優美標號,但只有 24 個根本不同的標號(修正了 Gardner 1983, pp. 163-164 報告的 5 個計數)。
E. Weisstein 於 2020 年 4 月 3 日和 7 月 30 日計算了所有簡單圖在 , 2, ..., 8 個節點上的所有(不僅僅是根本的)優美標號的總數。Knuth(2024,問題 97)給出了相應的根本不同的標號的總計數。這些計數,以及所有簡單圖的根本優美標號的總計數,在下表中給出。
| OEIS | 所有在 | 總型別 |
| A333727 | 1, 2, 16, 144, 1428, 25328, 631026, 25087224, ... | 所有(不僅僅是根本的)優美標號 |
| A379576 | 1, 1, 2, 14, 174, 3655, 122439, 6470268, ... | 根本優美標號 |
| A379575 | 0, 1, 2, 13, 157, 3292, 110578, 5903888, ... | 沒有孤立點的圖的根本優美標號 |
優美標號可以使用稀疏標尺生成(參見 Pegg 2019)。
對於在 圖的邊上且沒有孤立點的圖,存在
個優美標號,這對應於
的
種排列的 Lehmer 編碼(Sheppard 1976;Knuth 2024, p. 23),儘管其中一些對應於同一圖的備用標號。對於
條邊的非同構優美圖的數量,對於
, 2, ... 分別是 1, 1, 3, 5, 12, 37, 112, 340, 1078, 3620, 12737, ... (OEIS A308544),而 連通優美圖在
條邊上的數量分別是 1, 1, 3, 5, 11, 28, 79, 227, 701, 2302, 8071, ... (OEIS A308545)。
Golomb 表明,連線偶數編號和奇數編號的節點集的圖的邊的數量是 ,其中
是圖的邊的數量。
下表總結了一些索引圖族的根本不同的優美標號的數量。Arumugam 和 Bagga (2011) 給出了迴圈圖 直到
的(總)計數,儘管
和 23 存在印刷錯誤。
| 類別 | OEIS | 計數 |
| 反稜柱圖 | A000000 | X, X, 1, 26, 20, ... |
| 阿波羅尼安網路 | 1, 33, ... | |
| 啞鈴圖 | X, X, 1, 0, 0, ... | |
| 書圖 | 1, 16, 0, 417, ... | |
| 蜈蚣圖 | A000000 | 1, 1, 4, 30, 232, 2058, 26654, ... |
| 完全二部圖 | A335619 | 1, 1, 1, 4, 1, 7, 2, 10, 3, 8, 1, 42, 2, 7, 7, ... |
| 完全圖 | 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, ... | |
| 完全三部圖 | A000000 | 1, 4, 7, 12, 20, 34, 74, 131, 260, ... |
| 完全三部圖 | 1, 1, 0, 0, 0, 0, 0, ... | |
| 皇冠圖 | A000000 | 0, 0, 0, 27, 69, X, 0, ... |
| 圈圖 | A000000 | X, X, 1, 1, 0, 0, 6, 12, 0, 0, 104, 246, 0, 0, 3882, ... |
| 雙稜錐圖 | X, X, 4, 1, 7, 0, 22, X, X, 0, ... | |
| 空圖 | 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... | |
| 齒輪圖 | A000000 | X, X, 34, 358, 6781, 231758, 10575203, 695507601, ... |
| 網格圖 | A000000 | 1, 1, 358, 47428572, ... |
| 網格圖 | 1, 27, ... | |
| 半立方體圖 | 1, 1, 1, 0, ... | |
| 河內圖 | 1, 140, ... | |
| 舵圖 | X, X, 109, 777, ... | |
| 超立方體圖 | A000000 | 1, 1, 27, 607173, ... |
| 1, 1, 154, ... | ||
| 1, 0, 12, ... | ||
| 梯子圖 | A000000 | 1, 1, 16, 177, 2242, 48068, ... |
| 莫比烏斯梯子 | A000000 | X, X, 1, 34, 750, 8451, 208882, 5371997, 207664885, ... |
| 平底鍋圖 | A000000 | X, X, X, 5, 8, 13, 30, 60, 160, 394, 924, 2434, 7178, 21446, ... |
| 路徑補圖 | A000000 | 1, 0, 0, 1, 13, 34, 45, 18, 1, ... |
| 路徑圖 | A000000 | 1, 1, 1, 1, 2, 6, 8, 10, 30, 74, 162, 332, 800, 2478, 6398, 13980, ... |
| 稜柱圖 | A000000 | X, X, 4, 27, 444, ... |
| 星圖 | A000000 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... |
| 太陽圖 | A000000 | X, X, 0, 204, 4765, ... |
| 小太陽圖 | A000000 | X, X, 9, 42, 255, 2283, 27361, ... |
| 三角形蛇圖 | 1, 1, 0, 0, 368, ... | |
| 網狀圖 | X, X, 894, ... | |
| 輪圖 | A000000 | X, X, 1, 4, 12, 23, 67, 251, 1842, 10792, ... |
包含單個根本不同的優美標號(即,在圖自同構群下以及關於減法互補的唯一標號)的圖可以稱為唯一優美圖,並且具有最大可能數量的根本不同的標號(可能受制於一些附加條件,例如不具有孤立頂點)的圖可以稱為最大優美圖。