Results 1 to 15 of 15

Math Help - Euclidean Minimum spanning tree and an extra edge

  1. #1
    Junior Member
    Joined
    Jun 2013
    From
    United States
    Posts
    28
    Thanks
    5

    Euclidean Minimum spanning tree and an extra edge

    Consider n points randomly distributed in space. The goal is to find the graph that has the smallest Euclidean length that connects these points. The answer is clearly the minimum spanning tree G_0 which has n-1 edges. Now suppose we are required to use exactly n edges and find the smallest length graph G_1. Clearly, G_1 will contain exactly one cycle. Now suppose we remove the longest edge from this cycle and obtain graph G_1'. I am wondering if G_1' = G_0 for any configuration of points. My intuition is that it is true, and I'm not able to find a counter example. However, I am not able to prove it. Can someone help?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Sep 2009
    Posts
    40
    Thanks
    5

    Re: Euclidean Minimum spanning tree and an extra edge

    If we are given n randomly selected edges, we are not guaranteed that removing one such edge will produce a minimum spanning tree (note that there may be multiple MSTs for a graph). We are simply guaranteed that it is a spanning tree of minimal weight given the edges.

    In Euclidean space, we can model the graph as K_{n}. I will start with vertex v_{1} and take the edge with maximum weight incident to v_{1}. I then go to the vertex on the other side of the edge, call it v_{2} and pick its largest edge not incident to v_{1}. I continue this process such that no vertex on an iteration picks an edge incident to a vertex selected from any previous iteration. We are left with a spanning tree. Now for v_{n}, pick the edge incident to v_{1} and we have a cycle. Remove the edge on this cycle with the maximum weight. We have a spanning tree that is clearly not minimal.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2013
    From
    United States
    Posts
    28
    Thanks
    5

    Re: Euclidean Minimum spanning tree and an extra edge

    If we are given n randomly selected edges, we are not guaranteed that removing one such edge will produce a minimum spanning tree (note that there may be multiple MSTs for a graph). We are simply guaranteed that it is a spanning tree of minimal weight given the edges.
    The n edges of G_1 are NOT randomly selected and neither is the removed edge (it is the longest edge that is removed). G_1 is the unique graph that minimizes the total length among all graphs with n edges over the given n points.
    Once the configuration of points is given G_0, G_1, G_1' are all unique (well to be more precise, the set of configurations that have non-unique G_0, G_1, G_1' has measure zero).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Sep 2009
    Posts
    40
    Thanks
    5

    Re: Euclidean Minimum spanning tree and an extra edge

    Thank you for clarifying.

    So in other words, G_{1} is the Traveling Salesman solution of K_{n} on the n points, and we take G_{1} \setminus e, where e = max \{ w(e) : e \in E(G_{1}) \}. In this case, I would use an exchange argument to transform G_{1}^{\prime} = G_{1} \setminus e into G_{0}, the MST. Swap out edges from G_{1}^{\prime} and G_{0} such that the weight is non-decreasing from G_{1}^{\prime} to G_{0}. If you are familiar with the proof of correctness of Kruskal's algorithm, the portion proving that the spanning tree is minimal does so using such an exchange argument.

    A bit of intuition as well. The Held-Karp algorithm is the most efficient algorithm to compute the TSP solution. It operates by examining each vertex. For each vertex, it looks at the two lowest-cost edges and adds them up. The vertex with the lowest sum from this analysis is pulled out and its two lowest weight edges are chosen. We then compute an MST on the graph, limiting degree 2 on each vertex. Finally, we connect the two vertices of degree 1 after the MST algorithm terminates. So the intuition is that G_{1} is constructed by using an MST algorithm.

    Does this help?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jun 2013
    From
    United States
    Posts
    28
    Thanks
    5

    Re: Euclidean Minimum spanning tree and an extra edge

    So in other words, G_{1} is the Traveling Salesman solution of K_{n} on the n points,
    No. G_1 is not (necessarily) the solution to the TSP. The TSP requires every "city" to be visited exactly once. There is no such restriction for G_1.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Sep 2009
    Posts
    40
    Thanks
    5

    Re: Euclidean Minimum spanning tree and an extra edge

    If a city isn't visited at all, then G_{1} minus an edge cannot be an MST. Also, if you don't have the assumption that G_{1} is connected, G_{1} \setminus e won't be a spanning tree.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jun 2013
    From
    United States
    Posts
    28
    Thanks
    5

    Re: Euclidean Minimum spanning tree and an extra edge

    Quote Originally Posted by macosxnerd101 View Post
    If a city isn't visited at all, then G_{1} minus an edge cannot be an MST. Also, if you don't have the assumption that G_{1} is connected, G_{1} \setminus e won't be a spanning tree.
    Of course G_0, G_1, G_1' are all spanning graphs. What I meant earlier is that in G_1, vertices can have degree greater than 2, but not so in the TSP solution. Therefore G_1 is not necessarily the TSP solution.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Sep 2009
    Posts
    40
    Thanks
    5

    Re: Euclidean Minimum spanning tree and an extra edge

    Okay. That makes sense. You still need to assume connectivity to prove that G_{1} \setminus e is an MST. I'd still go with the exchange argument to show that a sequence of edge swaps removing edges from G_{1} \setminus e and replacing them with edges from G_{0} whose weights are at least as large as the ones removed from G_{1} \setminus e will satisfy the minimality portion. Once you have connectivity and $n-1$ edges, you have a spanning tree.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Jun 2013
    From
    United States
    Posts
    28
    Thanks
    5

    Re: Euclidean Minimum spanning tree and an extra edge

    Quote Originally Posted by macosxnerd101 View Post
    Okay. That makes sense. You still need to assume connectivity to prove that G_{1} \setminus e is an MST. I'd still go with the exchange argument to show that a sequence of edge swaps removing edges from G_{1} \setminus e and replacing them with edges from G_{0} whose weights are at least as large as the ones removed from G_{1} \setminus e will satisfy the minimality portion. Once you have connectivity and $n-1$ edges, you have a spanning tree.
    The connectivity of the graphs G_0, G_1 , G_1' is not an assumption. The graphs are all connected/spanning by construction. Note that G_1 contains exactly 1 cycle, and to get G_1' from G_1, we remove the longest edge from the cycle. So there is no loss of connectivity.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Sep 2009
    Posts
    40
    Thanks
    5

    Re: Euclidean Minimum spanning tree and an extra edge

    That's good to know. So did you figure it out then from my suggestions about an exchange argument?

    Also- in the future, I would suggest spelling out your assumptions in your question. I've been doing a lot of guessing at your assumptions because they weren't listed (such as connectivity), and you've been correcting them. Part of mathematics is specifying your definitions and assumptions quite clearly. You will get better help this way, too.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Jun 2013
    From
    United States
    Posts
    28
    Thanks
    5

    Re: Euclidean Minimum spanning tree and an extra edge

    Quote Originally Posted by macosxnerd101 View Post
    Also- in the future, I would suggest spelling out your assumptions in your question. I've been doing a lot of guessing at your assumptions because they weren't listed (such as connectivity), and you've been correcting them. Part of mathematics is specifying your definitions and assumptions quite clearly. You will get better help this way, too.
    Thanks for pointing that out and sorry for the confusion. I should have explicitly stated that G_1 is connected (I thought it is obvious from the context). Anyway, here is a better version of the problem statement:

    Consider n points randomly distributed in space. The goal is to find the graph that has the smallest Euclidean length that connects these points. The answer is clearly the minimum spanning tree G_0 which has n-1 edges. Now suppose we are required to use exactly n edges and find the smallest length connected graph G_1. Clearly, G_1 will contain exactly one cycle. Now suppose we remove the longest edge from this cycle and obtain graph G_1'. Is G_1' = G_0 for all configurations of the n points?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Sep 2009
    Posts
    40
    Thanks
    5

    Re: Euclidean Minimum spanning tree and an extra edge

    You should also explicitly define G_{1} in your problem statement as: G_{1} is the unique, connected graph that minimizes the total length among all graphs with n edges over the given n points.

    Now- are the weights equal for G_{1}^{\prime} and G_{0}? Yes. You prove it with an exchange argument. Are the graphs equal? Not necessarily. Remember- you can have multiple MSTs for a given graph.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Jun 2013
    From
    United States
    Posts
    28
    Thanks
    5

    Re: Euclidean Minimum spanning tree and an extra edge

    Quote Originally Posted by macosxnerd101 View Post
    Now- are the weights equal for G_{1}^{\prime} and G_{0}? Yes. You prove it with an exchange argument. Are the graphs equal? Not necessarily. Remember- you can have multiple MSTs for a given graph.
    So G_1' = G_0 for almost all configurations? (The set of of configurations that have multiple MSTs has measure zero).
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Sep 2009
    Posts
    40
    Thanks
    5

    Re: Euclidean Minimum spanning tree and an extra edge

    I'm not an analyst and am not familiar with measure theory, sorry. If you can clarify what you mean by that, perhaps I can give a better explanation.

    I think if you said that G_{1} \setminus e \in \{ T : T is an MST of G\} is a valid claim (specifying the constraint on the edge e, of course). In other words, there exist an MST isomorphic to G_{1} \setminus e.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Junior Member
    Joined
    Jun 2013
    From
    United States
    Posts
    28
    Thanks
    5

    Re: Euclidean Minimum spanning tree and an extra edge

    Quote Originally Posted by macosxnerd101 View Post
    I'm not an analyst and am not familiar with measure theory, sorry. If you can clarify what you mean by that, perhaps I can give a better explanation.
    I meant that there exist multiple MSTs only for some carefully chosen configuration of points, for eg: arranging the points in a regular grid, etc. For a general distribution of n points in, say,  [0,1]^2 , the MST will be unique.
    If this is confusing, just assume that we are only interested in configuration of points for which G_0, G_1, G_1' are all unique.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Minimum spanning tree According to graph kruskal
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 20th 2012, 03:18 AM
  2. Minimum Cost Spanning Tree
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 25th 2011, 10:54 AM
  3. Replies: 0
    Last Post: February 20th 2011, 04:03 AM
  4. minimum spanning tree
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 21st 2010, 08:21 AM
  5. minimum spanning tree/shortest route problem
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: January 7th 2010, 02:30 AM

Search Tags


/mathhelpforum @mathhelpforum