出度

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

基本介紹

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

基本介紹

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

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

1" style="float: none; display: block; margin: 0px auto; clear: both;" picsrc="dc54564e9258d1095aa22d4cda58ccbf6d814d8f" data-layout="blockcenter" width="158" height="142" url="https://gss1.bdstatic.com/9vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D220/sign=2293c7c74036acaf5de091fe4cd88d03/dc54564e9258d1095aa22d4cda58ccbf6d814d8f.jpg" compressw="158" compressh="142" useredit="1" />

2" style="float: none; display: block; margin: 0px auto; clear: both;" picsrc="7aec54e736d12f2e0419219e44c2d56285356834" data-layout="blockcenter" width="206" height="183" url="https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D220/sign=dd789fe3df2a283447a631096bb4c92e/7aec54e736d12f2e0419219e44c2d56285356834.jpg" compressw="206" compressh="183" useredit="1" />

設無向圖有個頂點，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中圖是圖的子圖，圖是圖的子圖。