为了找到树的直径,我可以从树中取任何节点,执行BFS以找到距离它最远的节点,然后执行BFS在该节点上。距第二个BFS最远的距离将产生直径。正确性证明:图论中树的直径算法
虽然我不确定如何证明这一点?我曾尝试在节点数量上使用归纳,但情况太多。
任何想法,将不胜感激......
为了找到树的直径,我可以从树中取任何节点,执行BFS以找到距离它最远的节点,然后执行BFS在该节点上。距第二个BFS最远的距离将产生直径。正确性证明:图论中树的直径算法
虽然我不确定如何证明这一点?我曾尝试在节点数量上使用归纳,但情况太多。
任何想法,将不胜感激......
我们称之为第一BFS X中发现的端点。关键的一步是证明在第一步中发现的x总是“有效” - 也就是说,它始终处于某条最长路径的一端。 (请注意,一般情况下,可能有多条同样最长的路径。)如果我们可以建立这个路径,可以很容易地看到以x为根的BFS将尽可能地从x找到一些节点,因此它必须是一个整体最长的路径。
提示:假设(相反)在两个顶点u和v之间存在较长的路径,它们都不是x。
注意到,在u和v之间的唯一路径上,必须有一些最高(最接近根)顶点h。有两种可能性:h从BFS的根到x的路径上,或者不是。通过显示在两种情况下,u-v路径至少可以通过用x的路径替换其中的某个路径段而形成矛盾。
[编辑]实际上,可能没有必要分别处理这两种情况。但是我经常发现把配置分解成几个(或者甚至很多)情况并且分别处理每个配置更容易。这里,h在从BFS根到x的路径上的情况更容易处理,并给出了另一种情况的线索。
[编辑2]说回这个以后,现在看来,我认为这两种情况需要考虑是:(i)紫外线路径贯穿从根x的路径(在一些顶点y,不一定在uv路径的最高点h);和(ii)它没有。我们仍然需要h来证明每个案例。
我要去努力j_random_hacker's hint。让s, t
成为最远的一对。令u
为任意顶点。我们有像
u
|
|
|
x
/\
/ \
/ \
s t ,
一个示意图,其中x
是s, t, u
交界处。
假设v
是与u
最大距离的顶点。如果原理图现在看起来像
u
|
|
|
x v
/\/
/ *
/ \
s t ,
然后
d(s, t) = d(s, x) + d(x, t) <= d(s, x) + d(x, v) = d(s, v),
在不等式成立,因为d(u, t) = d(u, x) + d(x, t)
和d(u, v) = d(u, x) + d(x, v)
。存在v
在s
和x
之间而不是在x
和t
之间的对称情况。
另一种情况看起来像
u
|
*---v
|
x
/\
/ \
/ \
s t .
现在,
d(u, s) <= d(u, v) <= d(u, x) + d(x, v)
d(u, t) <= d(u, v) <= d(u, x) + d(x, v)
d(s, t) = d(s, x) + d(x, t)
= d(u, s) + d(u, t) - 2 d(u, x)
<= 2 d(x, v)
2 d(s, t) <= d(s, t) + 2 d(x, v)
= d(s, x) + d(x, v) + d(v, x) + d(x, t)
= d(v, s) + d(v, t),
所以通过平均化参数max(d(v, s), d(v, t)) >= d(s, t)
,并v
属于最大限度遥远对。
下面看它的另一种方法:
假设ģ =(V,È)是一个非空,与顶点有限树设置V和边缘套E。
考虑下面的算法:
这基本上是从叶子向内着色的图形,用绿色标记与叶子最大距离的路径,并标记只有较短距离为红色的路径。同时,Ç,中心,具有较短的最大距离到叶节点被缩减距离,直到Ç仅包含与对叶的最大的最大距离的一个或两个节点。通过构造,从叶顶点到它们最近的仅穿过绿色边缘的中心顶点的所有简单路径长度相同(计数),以及从叶顶点到其最近中心顶点的所有其他简单路径(遍历在至少一个红色边缘)更短。此外可以证明,
现在考虑你的算法,这可能是更实用,在上面的光。从任何一个顶点v开始,恰好有一个简单的路径p从顶点,在中心顶点结束,并包含中心的所有顶点(因为摹是一棵树,如果有是两个顶点C然后它们共享边缘)。可以示出具有v作为一个端点都具有p的并集与从中心到叶片遍历仅绿色边缘的简单路径的形式中ģ最大简单路径。
我们的目的的关键点是另一端点的输入边缘必然是绿色的。因此,当我们搜索从那里开始的最长路径时,我们可以访问那些仅遍历从叶中心(所有顶点)到另一叶的绿色边的人。这些正是G中的最大长度简单路径,所以我们可以确信第二次搜索确实会揭示图形直径。
你能告诉我你的意思是太多的情况吗?理论上所有的子案例都应该通过归纳证明。 –
关键的一步是证明从第一个BFS发现的端点,我们称之为x,必须是最长路径的端点之一。提示:假设(相反)在两个顶点u和v之间有一条较长的路径,它们都不是x。在u和v之间的唯一路径上,必须有一些最高(最接近根)顶点h。有两种可能性:h在从根到x的路径上,或者不在。通过显示两种情况下的矛盾,通过用x的路径替换某个路径段,可以使u-v路径变得更长。 –
勘误表:在上面将“可以变得更长”改为“可以变得至少一样长”。这处理u或v(或两者)与x相同*深度的情况。 –