度序列

若把圖G所有頂點的度數排成一個序列，則稱該序列稱為圖G的度序列。度序列通常表示為非遞增序列。度序列是圖結構的一個屬性，不會隨著圖的表示形式而變化，同構圖具有相同的度序列。

基本介紹

• 中文名：度序列
• 外文名：degree sequence
• 所屬學科：網路
• 性質：圖論中的專用術語

序列定義

若把無向圖V(G)={v₁,v₂,v₃,..,v_n}，相應的可以得到各頂點對應的度的序列(d(v₁),d(v₂),d(v₃),...,d(v_n))，稱之為圖G的度序列。比如右邊的無向圖，度序列為(2,3,2,3,3,1)。

無向圖

對於有向圖，度序列表示為入度和出度的序列，比如右邊的有向圖，序列為((0,2),(1,2),(2,2),(2,1),(2,0))。

有向圖

序列性質

給定一個圖，度序列是唯一確定的，所以同構圖具有相同的度序列。但是，度序列一般不能惟一地標識一個圖；在某些情況下，異構圖具有相同的度序列。

序列套用

度序列問題為找到度序列對應的圖。無向圖中的0與有向圖中的(0,0)可以忽略，因為他們是通過在圖中添加孤立點得到的。能使度序列問題有解的序列被稱為可圖的。任何和為奇數的非負整數序列，如(3,3,1)，均不能用一個圖的度序列來實現。度序列問題也被稱為圖枚舉問題，可以通過Havel定理得到。