Thank you! Does either Prim\'s or Kruskal\'s algorithm work if there are negativ
ID: 3687957 • Letter: T
Question
Thank you!
Does either Prim's or Kruskal's algorithm work if there are negative edge weights Explain. Give an algorithm to find a maximum spanning tree in a connected undirected graph. You are given a set of N sticks, which are lying on top of each other in some configuration. Each stick is represented by its two endpoints, which are ordered triple representing its x, y, and z coordinates. No stick is vertical, and a stick may be picked up only if there is no stick on top of it. Give an algorithm that determines whether it is possible to pick up all the sticks, and if so, provides a sequence of stick pickups that accomplishes this.Explanation / Answer
a) Both Prim’s and Kruskal’s algorithm work with negative edge weights. It is because the correctness of the algorithm does not depend on the weights being positive. Kruskal’s algorithm sorts the edges according to weights (which doesn’t change when negative weights are present) and chooses the best edge from it each time. In Prim’s algorithm the tree evolves by adding the least weight edge that connects a tree vertex to a non-tree vertex. The edge selection is not effected by negative weights.
b) Give an algorithm to find the maximum spanning tree in a connected undirected graph ?
Consider an undirected, connected, weighted graph ,
You can make a copy of G called G' in which the weight of every edge is replaced with its negation (i.e. w(u,v) becomes -w(u,v)) and compute the minimum spanning tree MST(G') of the resulting graph using Kruskal’s algorithm (or any other MST algorithm). The resulting tree corresponds to a maximum weight spanning tree for the original graph G. Note that if it were not a maximum weight spanning tree, then the actual maximum weight spanning tree of G corresponds to a minimum spanning tree with less weight than MST(G'), which is a contradiction.
c)
It is possible to use segment intersection in 2D to solve this problem.
Checking is one segment above the other is same as checking for there intersection in XY projection and if they intersect than compare Z coordinate of intersection point on each segment. E.g. for segments a=((0,0,0), (2,2,2)) and b=((0,2,3), (2,0,5)), projection on XY is ((0,0), (2,2)) and ((0,2), (2,0)). 2D intersection is (1,1), and Z value in (1,1) for ais 1, and for b is 4. That means b is above a.
So, use segment intersection in 2D to find which segments are in relation. To find in which order to remove segments use topological sorting.
It is possible to use segment intersection in 2D to solve this problem.
Checking is one segment above the other is same as checking for there intersection in XY projection and if they intersect than compare Z coordinate of intersection point on each segment. E.g. for segments a=((0,0,0), (2,2,2)) and b=((0,2,3), (2,0,5)), projection on XY is ((0,0), (2,2)) and ((0,2), (2,0)). 2D intersection is (1,1), and Z value in (1,1) for ais 1, and for b is 4. That means b is above a.
So, use segment intersection in 2D to find which segments are in relation. To find in which order to remove segments use topological sorting.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.