# Euclidean Minimum spanning tree and an extra edge

• Apr 11th 2014, 10:50 AM
mnov
Euclidean Minimum spanning tree and an extra edge
Consider $\displaystyle 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 $\displaystyle G_0$ which has $\displaystyle n-1$ edges. Now suppose we are required to use exactly $\displaystyle n$ edges and find the smallest length graph $\displaystyle G_1$. Clearly, $\displaystyle G_1$ will contain exactly one cycle. Now suppose we remove the longest edge from this cycle and obtain graph $\displaystyle G_1'$. I am wondering if $\displaystyle 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.
• Apr 27th 2014, 11:53 AM
macosxnerd101
Re: Euclidean Minimum spanning tree and an extra edge
If we are given $\displaystyle 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 $\displaystyle K_{n}$. I will start with vertex $\displaystyle v_{1}$ and take the edge with maximum weight incident to $\displaystyle v_{1}$. I then go to the vertex on the other side of the edge, call it $\displaystyle v_{2}$ and pick its largest edge not incident to $\displaystyle 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 $\displaystyle v_{n}$, pick the edge incident to $\displaystyle 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.
• Apr 27th 2014, 04:11 PM
mnov
Re: Euclidean Minimum spanning tree and an extra edge
Quote:

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 $\displaystyle n$ edges of $\displaystyle G_1$ are NOT randomly selected and neither is the removed edge (it is the longest edge that is removed). $\displaystyle G_1$ is the unique graph that minimizes the total length among all graphs with $\displaystyle n$ edges over the given $\displaystyle n$ points.
Once the configuration of points is given $\displaystyle G_0, G_1, G_1'$ are all unique (well to be more precise, the set of configurations that have non-unique $\displaystyle G_0, G_1, G_1'$ has measure zero).
• Apr 27th 2014, 05:55 PM
macosxnerd101
Re: Euclidean Minimum spanning tree and an extra edge
Thank you for clarifying.

So in other words, $\displaystyle G_{1}$ is the Traveling Salesman solution of $\displaystyle K_{n}$ on the $\displaystyle n$ points, and we take $\displaystyle G_{1} \setminus e$, where $\displaystyle e = max \{ w(e) : e \in E(G_{1}) \}$. In this case, I would use an exchange argument to transform $\displaystyle G_{1}^{\prime} = G_{1} \setminus e$ into $\displaystyle G_{0}$, the MST. Swap out edges from $\displaystyle G_{1}^{\prime}$ and $\displaystyle G_{0}$ such that the weight is non-decreasing from $\displaystyle G_{1}^{\prime}$ to $\displaystyle 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 $\displaystyle G_{1}$ is constructed by using an MST algorithm.

Does this help?
• Apr 27th 2014, 06:44 PM
mnov
Re: Euclidean Minimum spanning tree and an extra edge
Quote:

So in other words, G_{1} is the Traveling Salesman solution of K_{n} on the n points,
No. $\displaystyle 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 $\displaystyle G_1$.
• Apr 27th 2014, 07:01 PM
macosxnerd101
Re: Euclidean Minimum spanning tree and an extra edge
If a city isn't visited at all, then $\displaystyle G_{1}$ minus an edge cannot be an MST. Also, if you don't have the assumption that $\displaystyle G_{1}$ is connected, $\displaystyle G_{1} \setminus e$ won't be a spanning tree.
• Apr 27th 2014, 07:24 PM
mnov
Re: Euclidean Minimum spanning tree and an extra edge
Quote:

Originally Posted by macosxnerd101
If a city isn't visited at all, then $\displaystyle G_{1}$ minus an edge cannot be an MST. Also, if you don't have the assumption that $\displaystyle G_{1}$ is connected, $\displaystyle G_{1} \setminus e$ won't be a spanning tree.

Of course $\displaystyle G_0, G_1, G_1'$ are all spanning graphs. What I meant earlier is that in $\displaystyle G_1$, vertices can have degree greater than 2, but not so in the TSP solution. Therefore $\displaystyle G_1$ is not necessarily the TSP solution.
• Apr 27th 2014, 08:10 PM
macosxnerd101
Re: Euclidean Minimum spanning tree and an extra edge
Okay. That makes sense. You still need to assume connectivity to prove that $\displaystyle 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 $\displaystyle G_{1} \setminus e$ and replacing them with edges from $\displaystyle G_{0}$ whose weights are at least as large as the ones removed from $\displaystyle G_{1} \setminus e$ will satisfy the minimality portion. Once you have connectivity and $n-1$ edges, you have a spanning tree.
• Apr 28th 2014, 05:16 AM
mnov
Re: Euclidean Minimum spanning tree and an extra edge
Quote:

Originally Posted by macosxnerd101
Okay. That makes sense. You still need to assume connectivity to prove that $\displaystyle 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 $\displaystyle G_{1} \setminus e$ and replacing them with edges from $\displaystyle G_{0}$ whose weights are at least as large as the ones removed from $\displaystyle 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 $\displaystyle G_0, G_1 , G_1'$ is not an assumption. The graphs are all connected/spanning by construction. Note that $\displaystyle G_1$ contains exactly 1 cycle, and to get $\displaystyle G_1'$ from $\displaystyle G_1$, we remove the longest edge from the cycle. So there is no loss of connectivity.
• Apr 28th 2014, 06:13 AM
macosxnerd101
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.
• Apr 28th 2014, 07:23 AM
mnov
Re: Euclidean Minimum spanning tree and an extra edge
Quote:

Originally Posted by macosxnerd101
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 $\displaystyle G_1$ is connected (I thought it is obvious from the context). Anyway, here is a better version of the problem statement:

Consider $\displaystyle 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 $\displaystyle G_0$ which has $\displaystyle n-1$ edges. Now suppose we are required to use exactly $\displaystyle n$ edges and find the smallest length connected graph $\displaystyle G_1$. Clearly, $\displaystyle G_1$ will contain exactly one cycle. Now suppose we remove the longest edge from this cycle and obtain graph $\displaystyle G_1'$. Is $\displaystyle G_1' = G_0$ for all configurations of the $\displaystyle n$ points?
• Apr 28th 2014, 07:29 AM
macosxnerd101
Re: Euclidean Minimum spanning tree and an extra edge
You should also explicitly define $\displaystyle G_{1}$ in your problem statement as: $\displaystyle G_{1}$ is the unique, connected graph that minimizes the total length among all graphs with $\displaystyle n$ edges over the given $\displaystyle n$ points.

Now- are the weights equal for $\displaystyle G_{1}^{\prime}$ and $\displaystyle 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.
• Apr 28th 2014, 07:52 AM
mnov
Re: Euclidean Minimum spanning tree and an extra edge
Quote:

Originally Posted by macosxnerd101
Now- are the weights equal for $\displaystyle G_{1}^{\prime}$ and $\displaystyle 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 $\displaystyle G_1' = G_0$ for almost all configurations? (The set of of configurations that have multiple MSTs has measure zero).
• Apr 28th 2014, 08:39 AM
macosxnerd101
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 $\displaystyle G_{1} \setminus e \in \{ T : T is an MST of G\}$ is a valid claim (specifying the constraint on the edge $\displaystyle e$, of course). In other words, there exist an MST isomorphic to $\displaystyle G_{1} \setminus e$.
• Apr 28th 2014, 09:13 AM
mnov
Re: Euclidean Minimum spanning tree and an extra edge
Quote:

Originally Posted by macosxnerd101
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 $\displaystyle n$ points in, say, $\displaystyle [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 $\displaystyle G_0, G_1, G_1'$ are all unique.