圖的頂點度數

---

它是與頂點V相鄰的頂點數。

符號 − deg(V)。

在一個具有n個頂點的簡單圖中，任何頂點的度數為−

deg(v) = n – 1 ∀ v ∈ G

一個頂點可以與除自身以外的所有其他頂點形成邊。因此，頂點的度數最多為圖中頂點數減1。這個1是自頂點，因為它不能獨自形成環。如果任何頂點都有環，則它不是簡單圖。

頂點的度數可以在圖的兩種情況下考慮：

• 無向圖
• 有向圖

無向圖中頂點的度數

無向圖沒有有向邊。考慮以下示例。

示例1

看看下面的圖：

在上圖的無向圖中，

• deg(a) = 2，因為在頂點'a'處有2條邊相交。

• deg(b) = 3，因為在頂點'b'處有3條邊相交。

• deg(c) = 1，因為在頂點'c'處形成1條邊

  所以'c'是懸掛頂點。

• deg(d) = 2，因為在頂點'd'處有2條邊相交。

• deg(e) = 0，因為在頂點'e'處沒有形成邊。

  所以'e'是孤立頂點。

示例2

看看下面的圖：

在上圖中，

deg(a) = 2, deg(b) = 2, deg(c) = 2, deg(d) = 2, deg(e) = 0。

頂點'e'是孤立頂點。該圖沒有懸掛頂點。

有向圖中頂點的度數

在有向圖中，每個頂點都有一個入度和一個出度。

圖的入度

• 頂點V的入度是指進入頂點V的邊的數量。

• 符號 − deg⁻(V)。

圖的出度

• 頂點V的出度是指從頂點V出去的邊的數量。

• 符號 − deg⁺(V)。

考慮以下示例。

示例1

看看下面的有向圖。頂點'a'有兩條邊'ad'和'ab'指向外部。因此，它的出度為2。同樣，有一條邊'ga'指向頂點'a'。因此，'a'的入度為1。

其他頂點的入度和出度如下表所示：

頂點	入度	出度
a	1	2
b	2	0
c	2	1
d	1	1
e	1	1
f	1	1
g	0	2

示例2

看看下面的有向圖。頂點'a'有一條邊'ae'從頂點'a'指向外部。因此，它的出度為1。同樣，該圖有一條邊'ba'指向頂點'a'。因此，'a'的入度為1。

其他頂點的入度和出度如下表所示：

頂點	入度	出度
a	1	1
b	0	2
c	2	0
d	1	1
e	1	1