[科普中國]-入度

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

簡介引入如果則稱 a 為從 u 到 v 的弧(arc)，u和 v 為 a 的端點，稱 u 是 a 的尾(tail)，v 是 a 的頭(head)。

定義頂點 v 的入度是指以 v 為頭的弧的數目；頂點v的出度(outdere) 是指以 v 為尾的弧的數目。

入度的常見情況當入度為 0 時，指有向圖中的點不作為任何邊的終點，也就是說，這一點所連接的邊都把這一點作為起點。

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

相關定理定理1

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

定理2

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

定理3

無論無向圖還是有向圖，頂點數 n ，邊數 e 和度之間又如下關系：E=(d[v1]+d[v2]+…+d[vn])/2。

有向圖[directed graph,digraph]

有向圖 D 是指一個有序三元組 (V(D),A(D),ψD) ，其中 V(D) 是非空的頂點集， A(D) 是與 V(D) 不交的弧集， ψD是關聯函數，它使 D 的每條弧對應于 D 的一個有序頂點對(不必相異)。

對應于每個有向圖 D，可以在相同頂點集上構造一個新圖 G，使得對于 D 的每條弧，G 有一條相同端點的邊與之對應。這樣的圖 G 稱為有向圖 D 的基礎圖(underlying graph)，換言之，將 D 中所有邊的方向去掉所得到的無向圖即為 D 的基礎圖。

反之，對應于每個無向圖G ，可以在相同頂點集上構造有向圖 D ，只需把 G 中的每條邊換成與該邊具有相同端點，但方向相反的兩條弧，由此得到的有向圖稱為 G 的伴隨有向圖(associated digraph)。特別地，完全圖的伴隨有向圖稱為完全有向圖(complete digraph)。

給無向圖 G 中的每條邊一個方向，由此得到的有向圖稱為 G 的一個定向 (orientation)。特別地，簡單圖的定向稱為定向圖 (oriented graph)，完全圖的定向稱為競賽圖 (tournament)。1

本詞條內容貢獻者為:

尚華娟 - 副教授 - 上海財經大學