无向图算法
无向图算法
提问于 2013-10-04 05:14:58
假设我们有一个n节点，m个无向图G= (V；E)，我们有两个不同的节点叫做s和t，假设s和t之间的距离严格大于n/2。证明了存在一个与s和t不同的节点v，使得从s到t的每条路径都经过，给出了运行时间为O(n + m)到这样一个顶点的算法。你不需要证明你的算法是正确的，但是你必须证明像v这样的顶点是存在的。
我想不出这个过去的论文问题的确切答案，帮帮我！
回答 1
Stack Overflow用户
发布于 2013-10-04 16:08:52
假设s和t之间有两条不共享节点的路径。由于s和t之间的距离> n/2，所以每条路径在s和t之间都有>= n/2节点，这意味着图有>= n+2节点，这是一个矛盾。
对于算法来说，只要找到任何一条路径，而不需要使用路径节点就能看到连接到一侧的子图的位置，就足够了。详情如下：
- 如果s只连接到一个节点，而不是我们正在寻找的那个节点。
- 如果没有，则从
- 寻找路径s-t
- 查找连接到s的节点，而不使用路径s-t中节点的边。
- 路径s-t上的最后一个节点，即连接部分中的节点，是我们正在寻找的节点。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/19173736
复制相关文章
相似问题
腾讯云开发者
