algorithm - BFS生成的一棵树分析

Question

我想在 Mathexchange 上问这个问题，但它不是关于计算和是/否，而是更多关于计算机科学相关算法，所以我在这里问。

在BFS算法中，可以将遍历的每一层标记为层。例如，如果 s 是起始顶点，则任何单层中的顶点都应与 s 具有相同的距离。这是BFS搜索算法最基本的特点之一。

假设有i层，用BFS算法生成的树叫做T，图叫做G。这意味着 T 中任意 2 个节点之间的最大距离将为 i。 (大概是起始层一个，底层一个)

使用该属性，我如何证明 G 中存在一个顶点 a 且其度数最多为 6*| V|/i ?

我想因为层 L_j 中的任何顶点 u 都有边连接到层 L_j-1 和 L_j+ 中的顶点1，显示 3 个后续层的存在，总共有最多 6|V|/i 个顶点。有助于。

但问题是我知道目标，但我不知道如何实现它。

Answer 1

方法可能应该是:采用三元组层(例如 [1,2,3]、[4,5,6]...)。有i/3他们和他们是脱节的。他们一起有V顶点，这意味着必须有一个三元组 <= V/(i/3)其中(否则......算一下)。但是，这种方法最多导致 3V/i学位。

也许是 i应该是直径(我将其称为 m 作为两个顶点之间的最大距离。我对你的陈述感到困惑

the maximum distance between any 2 nodes in T would be i.

这是不正确的 - 对于某些顶点，您必须向上然后向下)。然后，m将是 <= 2*i这导致度数最多为 6V/m 的顶点.