BFS 生成的树的分析
我想过在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 个顶点。会有帮助的。
但问题是我知道目标，但不知道如何实现。
I thought about asking this question in the Mathexchange, but it is less about calculation and yes/no, but more about computer science related algorithm, so I am asking it here.
In BFS algorithm, it is possible to mark each level of traversal as layers. For example, if s is the starting vertice, vertices in any single layer should all have same distance to s. This is the one of the most basic characteristic of BFS search algorithm.
Assume that there are i layers, and a tree generated by BFS algorithm to be called T, and the graph to be called G. This means that the maximum distance between any 2 nodes in T would be i. (probably one from the starting layer, and one from the bottom layer)
Using that property, how can I prove that there exists a vertex a in G such that its degree would be at most 6*|V|/i ?
I thought since any vertex u in Layer L_j have edges connected to the vertices in layer L_j-1 and L_j+1, showing the existence of 3 consequent layers with total of at most 6|V|/i vertices. would help.
But the thing is that I know the goal, but I do not know how to approach it.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
该方法可能应该是：采用三层层（例如[1,2,3]，[4,5,6]...）。它们有
i/3个，并且它们是不相交的。它们一起具有V顶点，这意味着必须存在一个包含<= V/(i/3)的三元组（否则……算一下）。然而，这种方法最多导致3V/i程度。也许
i应该是直径（我将其称为m作为两个顶点之间的最大距离。我对你的陈述感到困惑这是不正确的 - 对于某些顶点，您必须先向上然后向下）。那么，
m将是<= 2*i，这会导致度数最多为6V/m的顶点。The approach should probably be: Take triplets of layers (eg. [1,2,3], [4,5,6]...). There are
i/3of them and they are disjoint. Together, they haveVvertices, which means there must be a triplet with<= V/(i/3)of them (otherwise ... count it). However, this approach leads to at most3V/idegree.Maybe the
ishould be the diameter (I'll call itmas Maximum distance between two vertices. I'm confused by your statementwhich is not true - for some vertices you must go up then down). Then,
mwould be<= 2*iwhich leads to vertices with degree at most6V/m.