我想在Mathexchange中问这个问题,但它不是关于计算和是/否,而是更多关于计算机科学相关算法,所以我在这里问它。
在bfs算法中,可以将每个遍历级别标记为层。例如,如果s是起始垂直,则任何单层中的顶点都应该与s具有相同的距离。这是BFS搜索算法最基本的特点之一。
假设有i层,BFS算法生成的树称为T,图称为G这意味着T中2个节点之间的最大距离将是i。(可能一个来自起始层,一个来自底层)
使用该属性,我如何证明在a中存在一个顶点G,使得它的程度最多是6*|V|/i
我认为,由于层中的任何一个顶点uL_j都有边连接到层L_j-1L_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

10-05 22:58
查看更多