出度

一般來說，圖可分為有向圖和無向圖。有向圖的所有邊都有方向，即確定了頂點到頂點的一個指向；而無向圖的所有邊都是雙向的，即無向邊所連線的兩個頂點可以互相到達。在一些問題中，可以把無向圖當作所有邊都是正向和負向的兩條有向邊組成。頂點的度是指和該頂點相連的邊的條數。特別是對於有向圖來說，頂點的出邊條數稱為該頂點的出度，頂點的入邊條數稱為該項點的入度。

基本介紹

• 中文名：出度
• 外文名：out-degree
• 所屬學科：數據結構
• 相關概念：有向圖、度、出度等

基本介紹

在無向圖中，頂點所具有的邊的數目稱為頂點的度。如圖1(a)中．無向圖的頂點的度為3，頂點的度為2。

在有向圖中，以頂點為頭的邊的數目稱為該頂點的入度；以頂點為尾的邊的數目稱為該頂點的出度；一個頂點的入度與出度之和稱為該頂點的度。如圖1中，有向圖的頂點的入度為2，出度也是2，頂點的度則為4。

設無向圖有個頂點，e條邊，每個頂點的度為，則有：

相關概念

圖的定義

一個圖由一個非空有限頂點集和一個邊的有限集組成。圖的頂點集和邊集分別用和表示，則圖G可表示成。

在圖中，若每條邊都用箭頭指明了方向，則稱此圖為有向圖，否則為無向圖。有向圖中的邊用表示，其中是有向圖的兩個頂點，稱為尾，稱為頭，在有向圖中用從到的箭頭表示，見圖2(a)。無向圖中的邊用表示，為無向圖的兩個頂點。圖2(b)是無向圖。無向圖的邊是無序的，也就是說與表示同一條邊。

從圖2中可知，(b)是一棵樹，而(a)不是樹，所以說樹是圖的特例。具有n個頂點的無向圖，若有條邊，稱之為完全圖。圖2中(c)便是一個完全圖。具有n個頂點的無向圖，至多有條邊；具有n個頂點的有向圖，則至多有條邊。

圖1(a) G1	圖1(b) G2	圖1(c) G3
圖1（d）G4	圖1(d) G5	圖1（d） G6、G7

子圖

設圖的頂點集和邊集為和，圖的頂點集和邊集為和，若：

則稱圖是圖的子圖。例如，圖2中圖是圖的子圖，圖是圖的子圖。