出度

出度

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

基本介紹

  • 中文名:出度
  • 外文名: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中圖
是圖
的子圖,圖
是圖
的子圖。

相關詞條

熱門詞條

聯絡我們