lux*_*cem 0 algorithm tree graph
给内容没有循环的树(例如最小生成树:http://fr.wikipedia.org/wiki/Fichier : Minimum_spanning_tree.svg)如果将树用作root用户,如何计算哪个节点最小化？
Wor*_*red 12
所有树都没有循环.根据定义,树是一个无循环的连通图.如果有一个顶点,答案是微不足道的.所以假设至少有两个顶点.
设u和v为两个顶点,使得它们的距离d(u,v)最大.应该很容易看出,如果选择沿最短的uv路径的顶点作为根,则深度将至少为ceiling(d(u,v)/ 2).还应注意,如果选择一个顶点作为不在该路径上的根,则深度将大于ceiling(d(u,v)/ 2).
假设我们选择了根- [R为沿着最小中间顶点UV路径,使得d(Û,- [R)= 天花板(d(Û,v)/ 2)和d([R ,v)≤ 天花板(d(你,v)/ 2).如果有另一个顶点,w,使得d(r,w)> ceiling(d(u,v)/ 2),我们将得到d(u,r)< d(w,r)然后,因为那里只是树中任意两个不同顶点之间的一条路径,我们有d(u,v)= d(u,r)+ d(r,v)< d(u,r)+ d(r,w)= d(u,w),与你和v的距离最大相矛盾.所以现在深度,以r为根,是天花板(d(u,v)/ 2).
所以我们需要找到距离最大的两个顶点.一旦我们这样做,我们可以使用最短路径寻找算法的uv,注意长度,并沿着所述路径中途遍历并使用该中间顶点作为根.
我们如何找到这些顶点？选择一个顶点w并将其放入队列中.当队列非空时,将队列中下一个顶点的邻居添加到队列的末尾.当队列为空时,请记下最近删除的顶点.这将是你.再次执行该程序,您将获得v.
为什么这样做？上述算法从w找到距离最远的顶点.如果w碰巧是u或v,则算法分别清楚地找到v或u.所以假设w既不是你也不是v.如果算法在第一遍中找到了u或v,那么它将起作用(因为它会在第二遍中找到另一个),所以通过矛盾的方式假设在第一遍之后它发现x使得它不是树的最大路径的结束.从我们的三角不等式ð(ü,v)≤ d(ü,w ^)+ d(w ^,v)和d(v,X)≤ d(v,w ^)+ d(w ^,X).从我们第一次减去第二ð(ü,v) - d(v,X)≤ d(ü,w ^) - d(w ^,X).然后,我们可以重新安排到d(ü,v)+ d(w ^,X)≤ d(ü,w ^)+ d(v,X).由于d(瓦特,Û)≤ d(瓦特,X)(X是从最大路径的端部瓦特 ; 吴不能超过WX)和d(v,X)< d(Û,v)(X是不我们可以将不等式加强到d(u,v)+ d(w,x)< d(u,v)+ d(w,x).但是,这是不可能的,因此x必须位于最大路径的末尾.
