度 (圖論)

在圖論中，一個頂點在圖中的度 (degree)為與這個頂點相連接的邊的數目。在多重圖中，自環被計數兩次。^[1] 頂點 ${\displaystyle v}$ 的度記作${\displaystyle \deg(v)}$或${\displaystyle \deg v}$。圖G的最大度記作Δ(G)，最小度記作δ(G)，分別為圖中所有頂點度的最大值和最小值。 在右邊的多重圖中，最大度為5，最小度為0。 在正則圖中，所有度都是相同的，因為我們可以直接說該圖的度是多少。 完全圖是正則圖中的一種特殊情況，其任意兩個點均相連，若頂點數為p，則該圖的度為p-1。

用度標記頂點的多重圖

給定一個圖${\displaystyle G=(V,E)}$,其度求和公式為：

${\displaystyle \sum _{v\in V}\deg(v)=2|E|\,.}$

該公式表明，在任意無向圖中，度為奇數的頂點的個數為偶數，即為握手定理。該定理名稱來自於一個熱門的數學問題，即證明在一個團體中與他人握手奇數次的人的數量為偶數個。

對於有向圖：

• 節點（頂點）的入度是指進入該節點（頂點）的邊的條數；
• 節點（頂點）的出度是指從該節點（頂點）出發的邊的條數。

度序列

兩個有相同度序列的異構圖 (3, 2, 2, 2, 2, 1, 1, 1).

無向圖的度序列是指包含其頂點度的非遞增序列；前文的圖其序列為(5,3,3,2,2,1,0)。^[2]度序列是一個圖不變量，所以同構圖具有相同的度序列。但是，度序列一般不能惟一地識別一個圖；在某些情況下，異構圖具有相同的程度序列。

度序列問題是尋找圖中包含頂點度的一個非遞增正整數序列的問題。(後面的零可以忽略，因為它們是通過向圖中添加適當數量的孤立頂點來實現的。)度序列中，能使度序列問題有解的序列被稱為圖序列。根據度序列公式，任何和為奇數的序列，如(3,3,1)，均不能用一個圖的度序列來實現。反之亦然：如果一個序列和為偶數，那麼它就是一個多重圖的度序列。這種圖可以很直接構造出來：將度為奇數的頂點進行匹配，並對剩下的頂點構造自環連接。一個給定的度序列是否可以用一個簡單圖來實現是一個很具挑戰性的。這個問題也被稱為圖枚舉問題,可以通過Erdős-Gallai定理或Havel-Hakimi算法來解決。找到或估測具有給定度序列圖的數目的問題來源於圖枚舉領域。

特殊值

一個包含4,5,6,7,10,11與12這些子節點的無向圖

• 度為0的頂點稱為孤立頂點。
• 度為1的頂點稱為葉節點或端點，與該頂點相關聯的邊稱為懸掛邊。在右圖中，{3,5}是一條懸掛邊。這個術語在資料結構與圖論中對樹的研究中很常見。
• 有n個頂點的圖中度為n-1的頂點稱為全連接頂點。

全局屬性

• 如果圖中每個頂點的度均為k，那麼這個圖被稱作k-正則圖，可稱該圖的度為k。類似地，在二分圖中，在同一側頂點的度相同的圖被稱作雙正則圖。
• 無向連通圖若且唯若它有0或2個奇數度的頂點時其有一個歐拉路徑。如果它有0個奇數度的頂點，歐拉路徑即為歐拉環路。
• 有向圖若且唯若每個頂點的出度都不超過1時為一個偽森林。函數圖是偽森林的一種特殊情況，其中每個頂點的出度都恰好為1。
• 根據布魯克斯定理，除了團和有奇數個頂點的循環圖以外的所有圖的最大著色數Δ，根據Vizing定理，所有圖的最大著色數為Δ+1。
• k-退化圖是一個所有子圖頂點的度最大為k的圖。

參見

• 度分布
• 二分圖的度序列
• 並行計算

注釋

1. Diestel p.5
2. Diestel p.278

參考文獻

• Diestel, Reinhard, Graph Theory 3rd, Berlin, New York: Springer-Verlag, 2005 [2019-04-23], ISBN 978-3-540-26183-4, （原始內容存檔於2011-07-28）.
• Erdős, P.; Gallai, T., Gráfok előírt fokszámú pontokkal (PDF), Matematikai Lapok, 1960, 11: 264–274 [2019-04-23], （原始內容 (PDF)存檔於2022-01-20） （匈牙利語）.
• Havel, Václav, A remark on the existence of finite graphs, Časopis pro pěstování matematiky, 1955, 80: 477–480 [2019-04-23], （原始內容存檔於2017-07-29） （捷克語）
• Hakimi, S. L., On realizability of a set of integers as degrees of the vertices of a linear graph. I, Journal of the Society for Industrial and Applied Mathematics, 1962, 10: 496–506, MR 0148049.
• Sierksma, Gerard; Hoogeveen, Han, Seven criteria for integer sequences being graphic, Journal of Graph Theory, 1991, 15 (2): 223–231, MR 1106533, doi:10.1002/jgt.3190150209.