主題
Search

度序列


給定一個 無向圖,度序列是其 圖的頂點頂點度數 (化合價)的單調非增序列。給定階數的圖的度序列數量與 圖劃分 密切相關。由於每條邊連線兩個頂點,因此被計算兩次,所以圖的度序列的元素之和始終為偶數(Skiena 1990,第 157 頁)。

G 中的最小頂點度表示為 delta(G)最大頂點度表示為 Delta(G) (Skiena 1990, p. 157)。度序列僅包含單個整數的多個副本的稱為正則圖。可以使用 Wolfram 語言 構建與給定度序列 d 對應的圖,使用RandomGraph[DegreeGraphDistribution[d]]。

GraphicalPartitions22211

拓撲結構不同的圖可能具有相同的度序列。此外,兩個不同的凸多面體甚至可以具有相同的骨架度序列,例如 三角錐三側錐十二面體 約翰遜多面體,它們都具有 8 個面,9 個頂點,15 條邊,以及度序列 (3, 3, 3, 3, 3, 3, 4, 4, 4)。

具有唯一度序列的圖可以稱為單圖或“唯一圖”(Tyshkevich 2000,Barrus等人 2023)。

對於 n=1, 2, ... 個節點的圖,不同的度序列的數量由 1, 2, 4, 11, 31, 102, 342, 1213, 4361, ... 給出 (OEIS A004251),而具有 n圖的頂點的非同構簡單無向圖的總數為 1, 2, 4, 11, 34, 156, 1044, ... (OEIS A000088)。因此,度序列數量少於非同構圖數量的第一個階數為 n=5。對於上面說明的圖,度序列在下表中給出。

1{0}
2{0,0}, {1,1}
3{0,0,0}, {1,1,0}, {2,1,1}, {2,2,2}
4{0,0,0,0}, {1,1,0,0}, {2,1,1,0}, {2,2,2,0},
{3,2,2,1}, {3,3,2,2}, {3,3,3,3}, {1,1,1,1},
{2,2,1,1}, {2,2,2,2}, {3,1,1,1}

階數為 n 的度序列的元素可能總和為 0, 2, 4, 6, ..., n(n-1)

如果存在一些與度序列對應的 k-連通圖,則度序列被稱為 k-連通的。例如,雖然度序列 {1,2,1} 是 1-連通但不是 2-連通的,{2,2,2} 是 2-連通的。


另請參閱

度集合, 可圖序列, 圖劃分, k-連通圖, 正則圖, 單圖, 不可交換圖, 頂點度

使用 探索

參考文獻

Barrus, M. D.; Trenk, A. N.; 和 Whitman, R. "單圖的遺傳閉包。" 2023 年 8 月 23 日。 https://arxiv.org/abs/2308.12190Ruskey, F. "關於度序列的資訊。" http://www.theory.csc.uvic.ca/~cos/inf/nump/DegreeSequences.htmlRuskey, F.; Cohen, R.; Eades, P.; 和 Scott, A. "尋找好住所的 Alley CATs。" Congres. Numer. 102, 97-110, 1994.Skiena, S. "實現度序列。" §4.4.2 在 實現離散數學:使用 Mathematica 的組合數學和圖論。 Reading, MA: Addison-Wesley, pp. 157-160, 1990.Sloane, N. J. A. 序列 A004251/M1250 在 "整數序列線上百科全書" 中。Tyshkevich, R. "圖序列和單圖的分解。" Disc. Math. 220, 201-238, 2000.

在 上引用

度序列

請引用本文為

Weisstein, Eric W. "度序列。" 來自 Web 資源。 https://mathworld.tw/DegreeSequence.html

主題分類