標籤: 暫無標籤

1 入度 -簡介

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

2 入度 -入度的常見情況

  入度為0

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

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

3 入度 -度的相關定理

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

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

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

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

相關評論

同義詞:暫無同義詞