text: 在圖論中，一個頂點在圖中的度 (degree)為與這個頂點相連線的邊的數目。在多重圖中，自環被計數兩次。 頂點 formula_1 的度記作formula_2或formula_3。圖"G"的最大度記作Δ("G")，最小度記作δ("G")，分別為圖中所有頂點度的最大值和最小值。 在右邊的多重圖中，最大度為5，最小度為0。 在正則圖中，所有度都是相同的，因為我們可以直接說該圖的度是多少。 完全圖是正則圖中的一種特殊情況，其任意兩個點均相連，若頂點數為p，則該圖的度為p-1。給定一個圖formula_4,其度求和公式為：formula_5該公式表明，在任意無向圖中，度為奇數的頂點的個數為偶數，即為握手定理。該定理名稱來自於一個熱門的數學問題，即證明在一個團體中與他人握手奇數次的人的數量為偶數個。對於有向圖：度序列.無向圖的度序列是指包含其頂點度的非遞增序列；前文的圖其序列為(5,3,3,2,2,1,0)。度序列是一個圖不變數，所以同構圖具有相同的度序列。但是，度序列一般不能惟一地識別一個圖；在某些情況下，異構圖具有相同的程度序列。度序列問題是尋找圖中包含頂點度的一個非遞增正整數序列的問題。(後面的零可以忽略，因為它們是透過向圖中新增適當數量的孤立頂點來實現的。)度序列中，能使度序列問題有解的序列被稱為圖序列。根據度序列公式，任何和為奇數的序列，如(3,3,1)，均不能用一個圖的度序列來實現。反之亦然：如果一個序列和為偶數，那麼它就是一個多重圖的度序列。這種圖可以很直接構造出來：將度為奇數的頂點進行匹配，並對剩下的頂點構造自環連線。一個給定的度序列是否可以用一個簡單圖來實現是一個很具挑戰性的。這個問題也被稱為圖列舉問題,可以透過Erdős-Gallai定理或Havel-Hakimi演算法來解決。找到或估測具有給定度序列圖的數目的問題圖列舉領域。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 度 (圖論)
metadata: https://zh.wikipedia.org/wiki?curid=6590825