[科普中國]-出度

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

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

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

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

相關(guān)概念圖的定義一個圖由一個非空有限頂點集和一個邊的有限集組成。圖的頂點集和邊集分別用和表示，則圖G可表示成。

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

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

|| ||

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

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

本詞條內(nèi)容貢獻者為:

尚華娟 - 副教授 - 上海財經(jīng)大學