我正在为面试而学习，遇到了这个我无法解决的问题。它是这样的：
创建一个高效的算法，对无向图 G 执行两项任务：（1）通过用单个边替换边来消除边的多个副本，（2）将边 (u, v) 和 (v,w) 替换为边 (u,w) 其中 v 是二阶边。请注意，删除一个度数为 2 的顶点可以创建多个边的副本，而删除多个边的副本可以创建一个度数为 2 的顶点。
我不太明白如何删除一个度数为二的顶点可以创建多个边的副本，以及删除多个边的副本如何创建一个度数为二的顶点。有人可以帮忙澄清一下吗？
问问题
140 次
2 回答
0
移除度数为 2 的顶点可以创建多个边的副本：
原边：(u,v), (v,w), (u,w) 去掉v后：(u, w), (u, w)
删除多个边的副本可以创建一个度数为 2 的顶点：
原始边缘：(u,v), (v,w), (v,w) 去除后 (v,w): (u, v), (v, w)
于 2013-11-13T07:45:13.303 回答
0
在四个顶点的图中，w, x, y, z
w *----- x -----* y ------- z
| |
*---------------*
如果您使用替换规则将 (w, x) 和 (x, y) 替换为 (w, y)，那么看起来，从 w 到 y 有两条平行边。如果您删除重复的边，则图表将如下所示：
w --------------- y ------- z
所以现在如果你用 (w, z) 替换 (w, y) 和 (y, z) 我们只需要 (w, z)
w ------------------------- z
不完全是预期的
于 2013-11-13T07:13:40.210 回答