0
$\begingroup$

how can I make a proof of this property? I mean, given a weighted tree(with positive costs), how can I proof that the center of such a tree lies on the longest path?? I read to the first answer of this a short description of the proof but I cannot understand how to prove that v is more central than c...

$\endgroup$
  • $\begingroup$ I think you mean a weight-balanced tree, otherwise constructing a counterexample is pretty easy. So first things first, make sure that your description of the tree is accurate. $\endgroup$ – aaaaaaaaaaaa Dec 1 '13 at 11:00
  • $\begingroup$ @eBusiness actually the tree can be even unbalanced..i should prove the general case. in a general tree why the center always lies on the longest path?..for a general graph this is not always true. $\endgroup$ – bece Dec 1 '13 at 16:50
  • $\begingroup$ Oh, you mean tree as in loop-free graph, and center as in the node(s) that are closest to the furthest away node. Now it makes sense. $\endgroup$ – aaaaaaaaaaaa Dec 1 '13 at 19:48
  • $\begingroup$ @eBusiness yes..the center of the tree is the node c that minimizes the maximum distance to all the other nodes..Any idea?? $\endgroup$ – bece Dec 1 '13 at 20:24
0
$\begingroup$

For a non-weighted tree imagine the longest path stretched to as straight line, with two ends $A$ and $B$, everything else is appendages to that. The line has length $l$, and $A$ and $B$ are $l-1$ jumps from one another. With eccentricity defined for each node as the distance to the furthest away node $A$ and $B$ has eccentricity $l-1$, their immediate neighbours eccentricity $l-2$ (unless the line consist of only two nodes) etc. Until you reach the middle nodes that has the lowest eccentricity on this line.

$A$ and $B$ obviously only have the one neighbour on the line, if they had another neighbour that neighbour could be used to extend the line, and it would not be the furthest line in the first place. $A$ and $B$'s neighbours could have more neighbours, but if they themselves were to have more neighbours, it would in total constitute a longer line. We can expand this to the rule that any node on the line can only have a tree of neighbors, beyond those through the line, that is as deep as the distance to the closest of $A$ and $B$. This in turn can be used to show that there can be no nodes that are further from any node on the line than the furthest of $A$ and $B$. Thus the nodes on the line cannot have a greater eccentricity than the one granted through the distance to $A$ and $B$.

Also, any neighbour to the line must be $1$ further from $A$ and $B$ than its neighbour on the line, thus it has eccentricity $1$ greater than the neighbour on the line, and its own neighbours eccentricity $2$ greater etc. Thus the middle of the line must have the lowest eccentricity of the whole graph, and therefore be the centre node(s).

For a weighted graph make all the nodes blue, multiply the weights of the connections by the lowest common denominator, and replace every connection with a series of length $1$ connections separated by red nodes, of total length equal to the original connection. Now you have a non-weighted tree to work with. If the centre happens to be one of the red nodes then the centre of the original graph must be the closest blue nodes(s). As the longest line cannot run through this red node without also running through the blue nodes that it lies between, the longest line must run through the centre node(s) in the original graph.

Addendum

That was a mile of text, and it is not even a strictly formal proof as it skips some obvious but difficult to formulate parts. Still it should be useful, and someone more skilled in mathematical writing than me might even be able to make a nice text out of it.

$\endgroup$
  • $\begingroup$ thanks for the response.but i didn't got the last paragraph..how do you modify the weighted graph?which are the blue and the red nodes? $\endgroup$ – bece Dec 2 '13 at 21:03
  • $\begingroup$ @bece Just imagine your graph is a web of strings of various length, and the nodes are blue beads, then fill every string with as many red beads as there is room for, now it is approximately a non-weighted graph. $\endgroup$ – aaaaaaaaaaaa Dec 2 '13 at 21:26

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.