熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

圖 - 圖的概念(二)

2013-11-15 15:43:28  來源: 數據結構 

  圖的邊和頂點的關系

  無向邊和頂點關系

  若(v i v j )是一條無向邊則稱頂點v i 和v j 互為鄰接點(Adjacent)或稱v i 和v j 相鄰接;並稱(v i v j )依附

  或關聯(Incident)於頂點v i 和v j 或稱(v i v j )與頂點v i 和v j 相關聯

  【例】下圖G

  ① 與頂點v 相鄰接的頂點是v v 和v

  ② 關聯於頂點v 的邊是(v v )(v v )和(v v )

  

  有向邊和頂點關系

  若是一條有向邊則稱頂點v i 鄰接到v j 頂點v i 鄰接於頂點v j ;並稱邊關聯於v i 和v j

  或稱與頂點v i 和v j 相關聯

  【例】在下圖G 關聯於頂點v 的弧是

  

  頂點的度(Degree)

  ()無向圖中頂點v的度(Degree)

  無向圖中頂點v的度(Degree)是關聯於該頂點的邊的數目記為D(v)

  【例】上圖G 中頂點v 的度為

  ()有向圖頂點v的入度(InDegree)

  有向圖中以頂點v為終點的邊的數目稱為v的入度(Indegree)記為ID(v)

  【例】上圖G 中頂點v 的人度為l

  ()有向圖頂點v的出度(Outdegree)

  有向圖中以頂點v為始點的邊的數目稱為v的出度(Outdegree)記為OD(v)

  【例】上圖G 中頂點v 的出度為

  注意

  ①有向圖中頂點v的度定義為該頂點的入度和出度之和即D(v)=ID(v)+OD(v)

  【例】上圖G 中頂點v 的人度為l出度為則度為

  ②無論有向圖還是無向圖頂點數n邊數e和度數之間有如下關系

  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23859.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.