作者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