Author |
Topic: NEW PUZZLE: SPANNING TREE (Read 3396 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
 |
NEW PUZZLE: SPANNING TREE
« on: Sep 24th, 2002, 1:20pm » |
 Quote  Modify
|
Let S be a set of n distinct points in the plane. Let G = (V, E) be the undirected complete graph such that there is a 1:1 correspondence between the vertices in V and the points in S. Besides, suppose that for every edge (u,v) in E, there is an associated cost c(u,v) equal to the euclidean distance between the two corresponding points in S. For instance, if (3,0) and (0,4) are in S, and the corresponding vertices are A and B, then c(A,B) = 5.
Prove that the problem of finding the minimal spanning tree for G has a lower bound omega(n log n).
|
|
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PUZZLE: SPANNING TREE
« Reply #1 on: Sep 24th, 2002, 1:26pm » |
Quote Modify
|
What is this "minimal spanning tree"?
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: NEW PUZZLE: SPANNING TREE
« Reply #2 on: Sep 27th, 2002, 6:15am » |
Quote Modify
|
The structure termed TREE is an undirected graph with the following properties:
- T is connected;
- T contains no loops.
All trees of n vertices have n-1 edges, as you should have no trouble proving. A spanning tree T for a graph G is a subgraph of G that is both a tree and contains all vertices of G.
In other words, it's a tree whose vertices are all G's vertices and whose edges are included in the set of G's edges. For example, consider a triangle ABC, and suppose that A, B and C are nodes, while the sides are edges. Any two sides of ABC form a spanning tree for the triangle. For a tetrahedron, any three edges leaving the same vertex form a spanning tree.
If there is a cost function associated with the edges of G (like euclidean distance, as in my problem), then the weight of a spanning tree is the sum of the weights in its edges. So for the unit equilateral triangle, the cost of any generating tree is 2. The minimal spanning tree for a graph is defined as the spanning tree of least weight.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PUZZLE: SPANNING TREE
« Reply #3 on: Sep 27th, 2002, 9:58am » |
Quote Modify
|
I feared as much. I've been thinking about the problem, and it seems to me that Djikstra's algorithm will find the minimal spanning tree (starting with any node), but it will take O(n2) time (since there are n(n-1)/2 connections). I've come up with a bunch of ways of looking for the minimal spanning tree, but none of them work in O(n log n) in every case.
I just had a thought, though: the question isn't asking for a way to find it in O(n log n), but a reason that you can't find it any faster. Therefore, an O(n log n) solution won't even help ... guess I should think some more. Maybe this is a job for the platypus-hole principle.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: NEW PUZZLE: SPANNING TREE
« Reply #4 on: Sep 27th, 2002, 11:31am » |
Quote Modify
|
I've read somewhere that they DO make holes, it seems. 
How would you go about using Dijkstra's algorithm for this problem? The one I know of finds least paths between vertices, but this is trivial in this case; all vertices are connected, and because of the triangle inequality the least path between any two is just the edge connecting them. I don't see how to use this to solve the problem.
There exist algorithms for finding least spanning trees, the best-known of which are Kruskal's and Prym's, with complexities O(m log m) and O(n2), respectively, where n is the number of vertices and m is the number of edges. See more at
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Graph/Undirected.html
You're right, though, I'm asking for a theoretical lower bound. Good luck!
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PUZZLE: SPANNING TREE
« Reply #5 on: Sep 27th, 2002, 11:46am » |
Quote Modify
|
Right, I'm sure I've misrepresented Djikstra's algorithm. I was thinking of something similar in its greediness:
0) Pick any node
1) Consider all the edges out of the tree you have already formed.
2) Pick the edge with the smallest cost, and add the node on it which isn't already in your tree.
3) Repeat 1)-3) until all nodes are in your tree. Now it is a spanning tree, and, I believe, a minimal one!
However, this runs in O( E ), which is O( n2 ).
What I think we need to do is consider the number of possible spanning trees, and show that there are at least O(nn) of them. Then we need O(n log n) bits to enumerate them. I'm thinking along the lines of the "indistinguishability" argument for O(n log n) searches using comparisons.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Yournamehere
Guest
|
|
Re: NEW PUZZLE: SPANNING TREE
« Reply #6 on: Sep 27th, 2002, 3:21pm » |
Quote Modify
 Remove
|
on Sep 27th, 2002, 11:46am, James Fingas wrote:Right, I'm sure I've misrepresented Djikstra's algorithm. I was thinking of something similar in its greediness:
0) Pick any node
1) Consider all the edges out of the tree you have already formed.
2) Pick the edge with the smallest cost, and add the node on it which isn't already in your tree.
3) Repeat 1)-3) until all nodes are in your tree. Now it is a spanning tree, and, I believe, a minimal one!
|
|
This is called Prim's Algorithm, and does have the properties you suggest.
Addressing the original question, consider the problem of sorting a list of distinct real numbers. One can transform the problem to a MST problem of the suggested form: for each real x_i in the list, add a point P_i = (x_i, 0) to the set of points.
Now, when one solves the MST problem, one obtains a solution of the following form: every vertex P_i must have two edges, one to the closest vertex to the left of P_i and one to the closest vertex to the right of P_i, except for the leftmost and rightmost vertices, which only have one neighbor in the MST. Call this solution T. To see why this is the solution, note that this construct is indeed a spanning tree. To prove that it is minimum, note that all edges must lie on the x-axis. If another spanning tree U is constructed, then it can be shown that some two edges must overlap for some non-zero distance: if an edge e from a vertex does not go to the nearest point on either side, some other edge must visit that nearest point, and thus overlap with e. Since T has size (x_max - x_min), then we must conclude that either the size of U is larger than (x_max - x_min), in which case U cannot be minimum, or there is some interval of non-zero length between (x_min,0) and (x_max,0) which is not covered by any edge, in which case U is not a spanning tree (U is disconnected).
Now note that T gives a solution to the original sorting problem: one can take the leftmost point and traverse T to find the order of the points in the sorted list. We know sorting has a lower bound of Omega(n log n). Thus, MST must have a lower bound of Omega(n log n) as well: if it did not, then the above transformation (which, it must be noted for completeness, runs in O(n)) yields an algorithm for sorting which is not lower bounded by Omega(n log n), which is impossible.
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: NEW PUZZLE: SPANNING TREE
« Reply #7 on: Sep 27th, 2002, 3:29pm » |
Quote Modify
|
Yeah, that's Prim's (thanks Yournamehere - I had called it Kruskal's) algorithm, and it indeed gets you a minimal spanning tree.
I'm still thinking on this one but I'll toss in a few things that I know:
A spanning tree on n nodes has exactly n-1 edges.
I believe that it's Cayley's Theorem that says that there are nn-2 spanning trees on n nodes (well, I looked it up, and it looks like that's right at least).
So, yeah, I think this is the right track.
|
| « Last Edit: Sep 27th, 2002, 4:56pm by S. Owen » |
IP Logged |
|
|
|
Yournamehere
Guest
|
|
Re: NEW PUZZLE: SPANNING TREE
« Reply #8 on: Sep 27th, 2002, 3:32pm » |
Quote Modify
Remove
|
Looking back at the original question, I hope you meant to say the lower bound is uppercase Omega(n log n), rather than lowercase omega(n log n). Otherwise some other approach would be necessary.
|
|
IP Logged |
|
|
|
Yournamehere
Guest
|
|
Re: NEW PUZZLE: SPANNING TREE
« Reply #9 on: Sep 27th, 2002, 3:42pm » |
Quote Modify
Remove
|
on Sep 27th, 2002, 3:29pm, S. Owen wrote:Yeah, that's Kruskal's algorithm, and it indeed gets you a minimal spanning tree.
|
|
Actually, Kruskal's algorithm is to add any edges of lowest weight which do not create cycles, regardless of where those edges are located. During the running of Kruskal's, one may have several disconnected trees existing all at the same time, only to be joined later on.
Prim's algorithm, in contrast, grows a single tree from a starting vertex, always adding edges which connect to the growing tree. As I understood it, this was what was proposed.
Both algorithms give correct results, but simply go about the problem in a different fashion. With appropriate data structures, the run times of the two are asymptotically the same.
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: NEW PUZZLE: SPANNING TREE
« Reply #10 on: Sep 27th, 2002, 4:52pm » |
Quote Modify
|
Oops, you're exactly right. I got them mixed up.
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: NEW PUZZLE: SPANNING TREE
« Reply #11 on: Sep 27th, 2002, 5:17pm » |
Quote Modify
|
Yay! Such smart people. I actually did mean to say upper case OMEGA(n log n), and Yournamehere's solution is the exact one I found.
I must add for completeness (and this aspect almost tripled the time I required to solve this) that any algorithm that gives a spanning tree must return the specific edges in some appropriate data structure, which can then be used to traverse the tree in O(n) time. If the algorithm simply returned a set containing the MST edges as ordered pairs (u,v) of vertices, but without any underlying structure, we would have no means to quickly find an ordering of the original set of numbers.
However, this is a necessary requirement, because if, given a vertex v, x(v) time were required to go from it to an adjacent one, and the whole algorithm were not OMEGA(n log n), then
sum x(v) < n log n
(sum over all v)
since at least n edge traversals are necessary. Therefore, given the least element in the MST, sum x(v) < n log n time would be required to traverse the MST, and the result would still hold.
Now get going on the other spanning tree problem! 
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print