[其他] [圖論] 生成可以連接所有圖上點的定理

[WJAider (Aider)]

小弟跟朋友討論到這個問題

假設一個 Graph G(V, E), V = {v1, ..., vn}

需要生成一個 E 達成以下條件:

所有的 vi, vj in V 都存在一個 path 可以互相連通

那 E 應該有一個條件:

對所有 i in {1, ..., n}

存在 j in {1, ..., n} 使得 e(vi, vj) in E

原本是這樣想的

但是這樣會生成如下的 Graph:

v1-v2-v3

v4-v5-v6

這樣 v1 跟 v4 就不連通，但符合上述條件

我想應該是少了一個條件

想請問圖論之中有沒有相關定理闡述這件事情的?

跪求各位大大指點 Q_Q

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 219.68.246.149
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1489423806.A.0FA.html
推 LPH66       : 關鍵字: 生成樹 (spanning tree)
→ LPH66       : 咦等等, 你只要連通不一定要唯一...
→ LPH66       : 邊數至少是 n-1 是確定的, 不過這也是必要非充份
→ LPH66       : 不過如果是想要找個演算法生成連通圖的話
→ LPH66       : 維基百科上有個對「連通塊」(connected component)
→ LPH66       : 的一種定義, 用以邊定義的等價關係表示
→ LPH66       : 其實直觀上就是「加一條邊 = 把兩塊連起來」而已
→ LPH66       : http://tinyurl.com/nej6ys9
感謝大大回應

那應該可以這樣說，我在找 connected component 個數是 1 的 Graph

→ arthurduh1  : 由某個頂點 DFS 跑過一次，看能不能跑過所有頂點
→ arthurduh1  : 這樣時間複雜度 = O(|E|)
推 LPH66       : 我覺得原 PO 你要先講看看你的目的是什麼
→ LPH66       : 是數學上的條件還是單純程式上的判斷還是什麼應用
→ LPH66       : 也就是你要拿這個結果去做什麼
只是想找找有沒有相關的定理而已

當然原本遇到的問題是要生成這種 Graph

但這已經解決了，就用檢查 connected component 個數是不是一來生成即可

→ arthurduh1  : 唔  好像不是要判斷是否連通. 如果是要造出一個符合
→ arthurduh1  : 條件的邊集, 那是怎樣個連通法就很重要
可以再說得詳細一點嗎?

→ balista     : graph, not graphic
好的，已訂正

推 agga        : 不太清楚你的問題,照你原本所問,就v1一路連到vn就好
→ agga        : 再連回來形成一個cycle就一定有你要的path
那只是其中一個，有辦法找出所有的嗎

→ wohtp       : 原po你那個條件只是保證沒有孤立的點吧？
→ wohtp       : 只要每一塊都大於一點，圖要裂成多少塊都可以
對阿，我的條件給錯了，內文也有說，想請問大大有什麼高見把它弄對QQ
※ 編輯: WJAider (219.68.246.149), 03/16/2017 22:26:01
推 suhorng     : 要找到所有的話, 先把點全排列, 重新命名為
→ suhorng     : v1 到 vn, 然後從 v1 連到 vn, 接著再隨機加入 0 條
→ suhorng     : 或多條邊, 這樣可以嗎?
推 suhorng     : 仔細想了一下這樣沒辦法產生所有的圖QQ
→ arthurduh1  : connected graph enumeration 有現成 library
推 vacuityhu   : 你的問題看起來是只要找出一種E就好了…不過如果是
→ vacuityhu   : 要找出所有可能的E而且也不考慮計算複雜度的話
→ vacuityhu   : 應該可以從complete graph出發
→ vacuityhu   : 拆掉一條邊測一次連通
→ vacuityhu   : 這樣應該能找出所有…
→ vacuityhu   : 不過這根本暴力法= =a