作者mqazz1 (無法顯示)
站內Prob_Solve
標題[問題] MST跟direction
時間Thu Dec 22 19:11:28 2011
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
1F：→ firejox:1.這應該是找出無向環....DFS應該可以... 12/22 20:05
2F：→ suhorng:第一題是問這個圖是不是 2-connected 12/22 21:58
3F：→ suhorng:也就是說, 是否所有的點都在同一個BCC內 12/22 21:59
4F：推 springman:不是biconnected的圖形似乎也可能是strongly connected 12/23 05:36
5F：→ springman:我想用 DFS 找 cycles 應該真的做得到，只是要想清楚 12/23 05:37
6F：推 LPH66:維基百科上是說第一題等同於問這圖是否 2-edge-connected 12/23 07:31
7F：→ LPH66:ie. 移除一個 edge 還是連通 ie. 沒有橋 12/23 07:31
8F：→ LPH66:不過證明要想想... 12/23 07:31
9F：推 LPH66:有橋→沒有定向使其強連通 這個方向是顯然的 12/23 07:34
10F：推 LPH66:對了, 不是 biconnected 但存在定向使其強連通的例子存在 12/23 07:39
11F：→ LPH66:▽ 左邊這個圖形就是了 12/23 07:40
12F：→ LPH66:△ 12/23 07:40
13F：→ LPH66:也就是單單 articulation point 是不夠的 需要橋 12/23 07:41
14F：推 DJWS:這兩題好像都是前年碩士班考題 12/23 11:14
15F：→ DJWS:1. Robbins' theorem. 驗證方式是 O(V+E) find bridge 12/23 11:15
16F：→ DJWS:2. 其實就是 Prim's Algorithm 最後一步。 O(V)加入最短的邊 12/23 11:16
17F：→ suhorng:不好意思,是我對名詞的了解不夠清楚 12/23 17:08