6

I'm doing my research and stuck with a question:

I am having a minimum spanning tree (prim algorithm), now one node in my tree gets deleted, I wonder if there is a way i can re-organize my tree such that the optimality still maintains?

I'm looking for some suggestions here and I will appreciate your help.

Thank you!

Note: All edge weights are 1 (unit graph)

|improve this question
  • We are not smart enough here on PSE to answer this. Try SO. – Job Mar 23 '11 at 1:47
  • funny...SO refers me to PSE... lol – tlc Mar 23 '11 at 1:49
  • It is called volleyball. On this particular question? – Job Mar 23 '11 at 2:14
  • I'm not sure I understand what you are asking exactly. Can you be more specific? Are you asking if you can recalculate the MST quickly after removing the node? Also, if the edge weights are 1, I'm not understanding the significance of a MST. Please explain more and I would be happy to ponder it with you. – Chad La Guardia Mar 23 '11 at 3:51
  • Couple of questions: Have you read chapters 16 and 23 of "Introduction to Algorithms"? (I expect you have but just need to check) Also, if you delete a node does this still allow your graph to be represented as a single tree in all cases? If not then Prim is not going to be valid. – Gary Rowe Apr 26 '11 at 12:29
1

If all edge weights are 1, then any spanning tree is a minimum spanning tree. Thus we can forget the fact that we want a minimum spanning tree and only focus on spanning trees.

This means that using prim's algorithm to construct the original tree is a waste. Prim's algorithm requires that you add the least weight at each step. But since all the weights are the same it doesn't matter what edge you add as long as the edge doesn't cause a cycle.

If we remove a node, there are two possibilities. If the node was a leaf on the tree, the new tree will still be spanning the entire graph. In that case we are done. Otherwise we end up with two trees. It could be that the graph is now disconnected in which no spanning tree exists. Assuming that the graph is connected, then adding any edge to the spanning tree which connects two trees will work.

|improve this answer
  • If the removed node is not leaf node, we don't necessarily end up with two trees. The result can be multiple trees, right? – fstang Mar 24 '18 at 22:46
  • @fstang, good point. – Winston Ewert Mar 24 '18 at 22:52
0

If you remove a vertex from your graph (that is an MST) you may not necessarily be left with a tree:

  • If the vertex you remove is a cut vertex your graph will be disconnected and no longer a tree.

  • If removing a vertex leaves your graph connected then because you have stated all edge weights are equal it will remain an MST. Any spanning tree of a graph with equal edge weights is a minimum spanning tree.

|improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.