3
$\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$
4
  • $\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$ Feb 25, 2015 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, 2015 at 14:46
  • $\begingroup$ @DRF Ah that makes sense. But still my problem stays unsolved :-( $\endgroup$ Feb 25, 2015 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$ Feb 25, 2015 at 14:52

1 Answer 1

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$
9
  • $\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$ Feb 25, 2015 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, 2015 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, 2015 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, 2015 at 17:26
  • $\begingroup$ @wece Thank you very much. $\endgroup$ Feb 25, 2015 at 17:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .