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

圖 - 圖的概念(四)

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

  連通圖和連通分量

  頂點間的連通性

  在無向圖G中若從頂點v i 到頂點v j 有路徑(當然從v j 到v i 也一定有路徑)則稱v i 和v j 是連通的

  連通圖

  若V(G)中任意兩個不同的頂點v i 和v j 都連通(即有路徑)則稱G為連通圖(Connected Graph)

  【例】圖G 和G 是連通圖

  

  連通分量

  無向圖G的極大連通子圖稱為G的連通分量(Connected Component)

  注意

  ① 任何連通圖的連通分量只有一個即是其自身

  ② 非連通的無向圖有多個連通分量

  【例】下圖中的G 是非連通圖它有兩個連通分量H 和H

  

  強連通圖和強連通分量

  強連通圖

  有向圖G中若對於V(G)中任意兩個不同的頂點v i 和v j 都存在從v i 到v j 以及從v j 到v i 的路徑則稱G是強連通圖

  強連通分量

  有向圖的極大強連通子圖稱為G的強連通分量

  注意

  ① 強連通圖只有一個強連通分量即是其自身

  ② 非強連通的有向圖有多個強連分量

  【例】下圖中的G 不是強連通圖因為v 到v 沒有路徑但它有兩個強連通分量如右圖所示

  

  網絡(Network)

  若將圖的每條邊都賦上一個權則稱這種帶權圖為網絡(Network)

  注意

  權是表示兩個頂點之間的距離耗費等具有某種意義的數

  【例】下圖就是一個網絡的例子

  


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