[問題] MST跟direction

看板Prob_Solve作者 (無法顯示)時間12年前 (2011/12/22 19:11), 編輯推噓5(5推 0噓 12→)
留言17則, 5人參與, 最新討論串1/1
Suppose you are asked to assign direction for each edge in the graph to make it a digraph such that each vertex can connect to each other vertex by some directed graph (i.e. strongly connected). How do you know whether such strongly connected orientation exists for an undirected graph G of n vertices and m edges. Explain your method and discuss its complexity. ==================== Suppose that a graph G has a minimum spanning tree already computed. How quickly can the minimum spanning be updated if a new vertex and incident edges are added to G? Please justify your answer. 請問這兩題應該怎麼解呢? 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.118.110.186
→
12/22 20:05, , 1F
1.這應該是找出無向環....DFS應該可以...
12/22 20:05, 1F
→
12/22 21:58, , 2F
第一題是問這個圖是不是 2-connected
12/22 21:58, 2F
→
12/22 21:59, , 3F
也就是說, 是否所有的點都在同一個BCC內
12/22 21:59, 3F
推
12/23 05:36, , 4F
不是biconnected的圖形似乎也可能是strongly connected
12/23 05:36, 4F
→
12/23 05:37, , 5F
我想用 DFS 找 cycles 應該真的做得到，只是要想清楚
12/23 05:37, 5F
推
12/23 07:31, , 6F
維基百科上是說第一題等同於問這圖是否 2-edge-connected
12/23 07:31, 6F
→
12/23 07:31, , 7F
ie. 移除一個 edge 還是連通 ie. 沒有橋
12/23 07:31, 7F
→
12/23 07:31, , 8F
不過證明要想想...
12/23 07:31, 8F
推
12/23 07:34, , 9F
有橋→沒有定向使其強連通 這個方向是顯然的
12/23 07:34, 9F
推
12/23 07:39, , 10F
對了, 不是 biconnected 但存在定向使其強連通的例子存在
12/23 07:39, 10F
→
12/23 07:40, , 11F
▽ 左邊這個圖形就是了
12/23 07:40, 11F
→
12/23 07:40, , 12F
△
12/23 07:40, 12F
→
12/23 07:41, , 13F
也就是單單 articulation point 是不夠的 需要橋
12/23 07:41, 13F
推
12/23 11:14, , 14F
這兩題好像都是前年碩士班考題
12/23 11:14, 14F
→
12/23 11:15, , 15F
1. Robbins' theorem. 驗證方式是 O(V+E) find bridge
12/23 11:15, 15F
→
12/23 11:16, , 16F
2. 其實就是 Prim's Algorithm 最後一步。 O(V)加入最短的邊
12/23 11:16, 16F
→
12/23 17:08, , 17F
不好意思,是我對名詞的了解不夠清楚
12/23 17:08, 17F
‣ 更多 mqazz1 的文章
文章代碼(AID): #1Eyn1Y-a (Prob_Solve)