基本介紹
- 中文名：入度
- 外文名：indegree
- 適用範圍：數理科學
簡介,引入,定義,入度的常見情況,相關定理,有向圖,
簡介
引入
如果
則稱 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)。
