[問題] MST跟direction
看板Prob_Solve (計算數學 Problem Solving)作者mqazz1 (無法顯示)時間13年前 (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
12/22 20:05, 1F
→
12/22 21:58, , 2F
12/22 21:58, 2F
→
12/22 21:59, , 3F
12/22 21:59, 3F
推
12/23 05:36, , 4F
12/23 05:36, 4F
→
12/23 05:37, , 5F
12/23 05:37, 5F
推
12/23 07:31, , 6F
12/23 07:31, 6F
→
12/23 07:31, , 7F
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
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
12/23 07:41, 13F
推
12/23 11:14, , 14F
12/23 11:14, 14F
→
12/23 11:15, , 15F
12/23 11:15, 15F
→
12/23 11:16, , 16F
12/23 11:16, 16F
→
12/23 17:08, , 17F
12/23 17:08, 17F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12
