弱聯通演算法

⑴ 編程，什麼是強連通圖，弱連通圖

強連通圖（Strongly Connected Graph）是指一個有向圖（Directed Graph）中任意兩點v1、v2間存在v1到v2的路徑（path）及v2到v1的路徑的圖。 弱連通圖：如果不考慮有向圖中邊的方向所得到的無向圖是連通圖，則有向圖稱為弱連通圖可以從某一頂點起遍歷到子圖中所有的頂點，但並非從其他頂點也能做到的極大有向子圖。 這個不屬於電腦常識，你發錯地方了，應發到軟體版塊

⑵ 弱連通子集是什麼

數據結構的概念
應該說的是有向圖
對於無向圖來說，能連通所有結點的子集就叫做連通子集
對於有向圖來說，如果只能連通一個方向就叫弱連通，兩個方向都能連通就是強連通了

⑶ 弱連通圖的相關概念

在無向圖中, 若從頂點v1到頂點v2有路徑, 則稱頂點v1與v2是連通的。如果圖中任意一對頂點都是連通的,則稱此圖是連通圖。
強連通和弱連通的概念只在有向圖中存在。
一個無向圖G=(V,E) 是連通的，那麼邊的數目大於等於頂點的數目減一：|E|>=|V|-1，而反之不成立。
如果G=(V,E) 是有向圖，那麼它是強連通圖的必要條件是邊的數目大於等於頂點的數目：|E|>=|V|，而反之不成立。
沒有迴路的無向圖是連通的當且僅當它是樹，即等價於：|E|=|V|-1。 在有向圖中, 若對於每一對頂點v1和v2, 都存在一條從v1到v2和從v2到v1的路徑,則稱此圖是強連通圖。
即有向圖G=(V,E) 中，若對於V中任意兩個不同的頂點x和y，都存在從x到y以及從y到x的路徑，則稱G是強連通圖。相應地有強連通分量的概念。強連通圖只有一個強連通分量，即是其自身；非強連通的有向圖有多個強連分量。 如果有向圖中，對於任意節點v1和v2，至少存在從v1到v2和從v2到v1的路徑中的一條，則原圖為單向連通圖。
即設G=<V,E>是有向圖，如果u->v意味著圖G至多包含一條從u到v的簡單路徑，則圖G為單連通圖。
強連通圖、連通圖、單向連通圖三者之間的關系是，強連通圖必然是單向連通的，單向連通圖必然是弱連通圖。 有向圖D=(V,E)的每個點位於且僅位於D的某個強(弱)連通分支中。

⑷ 強連通圖一定是弱連通圖那麼為什麼要分強弱連通圖呢

我也是初學離散數學，我覺得分強弱連通圖和單向連通圖是為了所有的有向圖都有名字可以區分把，由強連通往下細分會覺得沒必要，但是反過來從所有圖往上分的話，命名可能就是必要的了。強連通圖的定義是針對有向圖，而連通圖的定義是對無向圖。歡迎討論，有錯誤的話還望指正

⑸ 弱連通圖的介紹

在圖論中，連通圖基於連通的概念。在一個無向圖G中，若從頂點到頂點有路徑相連（當然從到也一定有路徑），則稱和是連通的。如果G是有向圖，那麼連接和的路徑中所有的邊都必須同向。如果圖中任意兩點都是連通的，那麼圖被稱作連通圖。圖的連通性是圖的基本性質。1將有向圖的所有的有向邊替換為無向邊，所得到的圖稱為原圖的基圖。如果一個有向圖的基圖是連通圖，則有向圖是弱連通圖。

⑹ 什麼叫：強連通 單向連通 弱連通 不連通

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

連通分量：無向圖 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的路徑中所有的邊都必須同向。

如果圖中任意兩點都是連通的，那麼圖被稱作連通圖。如果此圖是有向圖，則稱為強連通圖（注意：需要雙向都有路徑）。圖的連通性是圖的基本性質。

(6)弱聯通演算法擴展閱讀：

強連通圖的邊問題：

有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條邊。

求無向圖的連通分量：

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

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

參考資料來源：網路-連通圖