當前位置:編程學習大全網 - 圖片素材 - 什麽叫:強連通 單向連通 弱連通 不連通

什麽叫:強連通 單向連通 弱連通 不連通

下面是這強連通、單向連通、弱連通、不連通的定義:

連通分量:無向圖 G的壹個極大連通子圖稱為 G的壹個連通分量(或連通分支)。連通圖只有壹個連通分量,即其自身;非連通的無向圖有多個連通分量。

強連通圖:有向圖 G=(V,E) 中,若對於V中任意兩個不同的頂點 x和 y,都存在從x到 y以及從 y到 x的路徑,則稱 G是強連通圖。相應地有強連通分量的概念。強連通圖只有壹個強連通分量,即是其自身;非強連通的有向圖有多個強連分量。

單向連通圖:設G=<V,E>是有向圖,如果u->v意味著圖G至多包含壹條從u到v的簡單路徑,則圖G為單連通圖。

弱連通圖:將有向圖的所有的有向邊替換為無向邊,所得到的圖稱為原圖的基圖。如果壹個有向圖的基圖是連通圖,則有向圖是弱連通圖。

初級通路:通路中所有的頂點互不相同。初級通路必為簡單通路,但反之不真。

在圖論中,連通圖基於連通的概念。在壹個無向圖 G 中,若從頂點i到頂點j有路徑相連(當然從j到i也壹定有路徑),則稱i和j是連通的。如果 G 是有向圖,那麽連接i和j的路徑中所有的邊都必須同向。

如果圖中任意兩點都是連通的,那麽圖被稱作連通圖。如果此圖是有向圖,則稱為強連通圖(註意:需要雙向都有路徑)。圖的連通性是圖的基本性質。

擴展資料:

強連通圖的邊問題:

有n個頂點的強連通圖最多有n(n-1)條邊,最少有n條邊。

1、最多的情況:即n個頂點中兩兩相連,若不計方向,n個點兩兩相連有n(n-1)/2條邊,而由於強連通圖是有向圖,故每條邊有兩個方向,n(n-1)/2×2=n(n-1),故有n個頂點的強連通圖最多有n(n-1)條邊。

2、最少的情況:即n個頂點圍成壹個圈,且圈上各邊方向壹致,即均為順時針或者逆時針,此時有n條邊。

求無向圖的連通分量:

作為遍歷圖的應用舉例,下面我們來討論如何求圖的連通分量。無向圖中的極大連通子圖稱為連通分量。求圖的連通分量的目的,是為了確定從圖中的壹個頂點是否能到達圖中的另壹個頂點,也就是說,圖中任意兩個頂點之間是否有路徑可達。

對於連通圖,從圖中任壹頂點出發遍歷圖,可以訪問到圖的所有頂點,即連通圖中任意兩頂點間都是有路徑可達的。

百度百科-連通圖

  • 上一篇:形容中秋月圓的詩句
  • 下一篇:菜刀是夾鋼刀好還是包鋼刀好?
  • copyright 2024編程學習大全網