2
$\begingroup$

I have given a set of points $S$ in $\mathbb{R}^2$. From the this points I create a mininum spanning tree MST.

  • The euclidean distance of the points is used as the weight for the edges.
  • The connecting edges between the points are straight.
  • The edges do not overlap in the MST.
  • By MST I mean that I want a spanning tree where the sum of the distances is minimal.
  • By spanning tree I mean that the it is a tree and all its vertices are connected.

I want to prove that for every MST like in the upper definition the vertex degree is in $\mathcal{O}(1)$.

Any ideas?

$\endgroup$
  • $\begingroup$ @DRF ok thanks for your time! but still i have to emphasize that the the resulting MST is not necassarily complete. It must be connected but not necassarily fully connected (complete). By connected I mean that you can reach every vertices on the MST (minimum spanning tree) via the undirected edges. By complete I mean that every vertices is connected with every vertices by an edge. $\endgroup$ – Tobias Thiel Feb 25 '15 at 14:32
  • $\begingroup$ @TobiasThiel Of course the MST is not complete. It wouldn't be a MST or even a T(ree) if it was complete. But the graph in which you searching for the MST is complete. $\endgroup$ – DRF Feb 25 '15 at 14:46
  • $\begingroup$ @DRF Ah that makes sense. But still my problem stays unsolved :-( $\endgroup$ – Tobias Thiel Feb 25 '15 at 14:51
  • $\begingroup$ The hashing out of the problem description has been moved to chat. It would clutter the comment area here, and now is of mostly historical interest if any. $\endgroup$ – Daniel Fischer Feb 25 '15 at 14:52
4
$\begingroup$

One can show that each vertex of your minimal spamming tree has less than 7 child.

Lets prove this by contradiction.

Assume that you have a minimal spamming tree $T=(V,E)$ and a vertex $v$ such that $v$ as 7 children, i.e. there exists $v_1$ ... $v_7$ all different such that $(v,v_i)\in E$ for all $i\in\{1...7\}$.

We denote $d(v',v'')$ the distance from $v'$ to $v''$, and $\measuredangle(v_i,v,v_j)$ the angle formed by the point $v_i,v,v_j$. Since $v$ has 7 children we know that there is to child (assume here that it is $v_1$ and $v_2$) such that $\measuredangle(v_1,v,v_2)<60°$. Assume that $d(v,v_1)\leq d(v,v_2)$.

We can deduce from $\measuredangle(v_1,v,v_2)<60 °$ and $d(v,v_1)\leq d(v,v_2)$ that $d(v_1,v_2)<d(v,v_2)$. Hence the tree $(V,E')$ with $E'=(E\setminus\{(v,v_2)\})\cup\{(v_1,v_2)\}$ is a smaller spamming tree. Contradiction with $T$ the minimal spamming tree.

I hope it's clear and it help.

EDIT: I missed the part: 'The edges do not overlap in the MST' in my last proof

We know from the previous part that if a Tree is a MST then each of it's vertex have less than 7 children. We now show that the edges of an MST do not overlap.

Again by contradiction. Assume we have an MST $T=(V,E)$ and two edges $(v_1,v_2)$ and $(v_1',v_2')$ that overlap.

Then considering the (may be flat) quadrilateral $v_1,v_1',v_2,v_2'$, $(v_1,v_2)$ and $(v_1',v_2')$ are the diagonals hence $d(v_1,v_2')+d(v_1',v_2)<d(v_1,v_2)+d(v_1,v_2')$ hence the tree $(V,E')$ with $E'=(E\setminus\{(v_1,v_2),(v_1',v_2')\})\cup\{(v_1,v_2'),(v_1',v_2) \}$ is smaller. Contradiction.

EDIT2 The edges $(v_1,v_1')$ and $(v_2,v_2')$ I chose in my previous answer may not preserve the tree property. I edited it in $(v_1,v_2'),(v_1',v_2)$ the do preserve the tree. (Thx DRF for the comment).

$\endgroup$
  • $\begingroup$ Thank you very much. I am not really good at geometry so how do you exactly deduce from $A(v_1,v,v_2)<60$ and $d(v,v_1)\leq d(v,v_2)$ that $d(v_1,v_2)<d(v,v_2)$ holds? $\endgroup$ – Tobias Thiel Feb 25 '15 at 16:18
  • $\begingroup$ Do you know that in a triangle denoting A and B two angles and a and b the length of their opposite side we have A>B iff a>b? Writing those inequalities for our case gives you the result. $\endgroup$ – wece Feb 25 '15 at 17:19
  • $\begingroup$ Very nice. One question is gnawing at me. How do you know that changing the spanning in this fashion doesn't introduce an edge which crosses another edge? I can sort of see how to make sure it doesn't cross any of the edges with the other 6 v_i but what edges between completely different vertices? It seems probable you can ensure it I just can't quite figure out how. $\endgroup$ – DRF Feb 25 '15 at 17:24
  • $\begingroup$ Ho right, I totally missed this part :D But don't worry It's an easy edit give me 5 minutes $\endgroup$ – wece Feb 25 '15 at 17:26
  • $\begingroup$ @wece Thank you very much. $\endgroup$ – Tobias Thiel Feb 25 '15 at 17:32

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.