入度

入度是圖論算法中重要的概念之一，常指有向圖中某點作為圖中邊的終點的次數之和。顧名思義，入度為0指有向圖中的點不作為任何邊的終點，也就是說，這一點所連線的邊都把這一點作為起點。在有向圖的拓撲排序中，每次都選取入度為0的點加入拓撲佇列中，再刪除與這一點連線的所有邊。定理1 無向圖中所有頂點的度之和等於邊數的2倍，有向圖中所有頂點的入度之和等於所有頂點的出度之和。定理2 任意一個無向圖一定有偶數個（或0個）奇點（度為奇數的頂點）。

簡介

入度是圖論算法中重要的概念之一。它通常指有向圖中某點作為圖中邊的終點的次數之和。

入度的常見情況

入度為0

顧名思義，入度為0指有向圖中的點不作為任何邊的終點，也就是說，這一點所連線的邊都把這一點作為起點。

在有向圖的拓撲排序中，每次都選取入度為0的點加入拓撲佇列中，再刪除與這一點連線的所有邊。

度的相關定理

定理1 無向圖中所有頂點的度之和等於邊數的2倍，有向圖中所有頂點的入度之和等於所有頂點的出度之和。

定理2 任意一個無向圖一定有偶數個（或0個）奇點（度為奇數的頂點）。

定理3 無論無向圖還是有向圖，頂點數n，邊數e和度之間又如下關係：

E=(d[v1]+d[v2]+…+d[vn])/2;