我想在Mathexchange中问这个问题,但它不是关于计算和是/否,而是更多关于计算机科学相关算法,所以我在这里问它。
在bfs算法中,可以将每个遍历级别标记为层。例如,如果s
是起始垂直,则任何单层中的顶点都应该与s
具有相同的距离。这是BFS搜索算法最基本的特点之一。
假设有i层,BFS算法生成的树称为T
,图称为G
这意味着T
中2个节点之间的最大距离将是i
。(可能一个来自起始层,一个来自底层)
使用该属性,我如何证明在a
中存在一个顶点G
,使得它的程度最多是6*|V|/i
?
我认为,由于层中的任何一个顶点u
层L_j
都有边连接到层L_j-1
和L_j+1
中的顶点,显示了3个结果层的存在,最多有顶点。会有帮助的。
但问题是我知道目标,但我不知道如何实现它。
最佳答案
方法可能是:取三层(如[1,2,3],[4,5,6]…)它们中有i/3
且不相交。它们一起有V
顶点,这意味着必须有一个包含<= V/(i/3)
顶点的三元组(否则…数一数)。然而,这种方法最多导致3V/i
度。
也许i
应该是直径(我称之为cc>)作为两个顶点之间的最大距离。你的陈述把我搞糊涂了
T中任意2个节点之间的最大距离为I。
这不是真的-对于某些顶点,必须先向上然后向下)。然后,m
将是m
这将导致顶点的阶数最多<= 2*i
。