顶点Biconnected和边双连通误解

-1

如果没有顶点的移除断开图连接，则连通图是顶点双连通的。如果没有移除切断图的边，则连通图是边双连通的。为以下语句给出每个证明或反例：顶点Biconnected和边双连通误解

（a）顶点双连通图是边双连通的。（b）边双连通图是顶点双连通的。

对于A）我的尝试是应该是这样，因为我没有看到去除顶点如何影响边的双连接。对于B）我的尝试是NO，因为如果我们有一个桥，连接两个图，删除该边将不再具有图顶点双连通。

也许我完全错了，任何援助将不胜感激。

来源

2013-04-20 user2302617

简单[反例]（https://www.math.umass.edu/~tevelev/zuz.png）（b） – 2013-04-20 17:18:30

@EgorSkriptunoff是我的（a）对不对？ – user2302617 2013-04-20 17:23:23

@ user2302617您没有提供（a）的证据。你提供了直觉，这是教育的一个重要组成部分，但在正式的背景下无关紧要。 – 2013-04-20 17:33:21

a）证明：通过相互矛盾。令G =（V，E）为顶点双连通。假设它不是边缘双连通的。那么存在一个边e = {v，w}，我们可以去除，使得G'=（V，E \ {e}）被断开。但是，我们也可以从G中移除v或w，并断开图形（因为移除边的任一端点也会移除该边），这与G是顶点双连通相矛盾;因此G也必须是边连通的。

来源

2013-04-20 20:25:02

我从视觉图中学得更好，我很难跟随你。 – user2302617 2013-04-20 20:28:53

不幸的是，可视化并不能帮助你学会如何证明一些东西。它只能帮助你理解证据背后的直觉。这个背后的想法是：如果我可以通过删除一条边来断开图，我也可以通过删除其中一条边所在的顶点来断开图。所以这证明'不是顶点双连通=>顶点双连通'，这是你想要证明的东西的对立面。 – 2013-04-20 20:35:50

你真的不应该接受你不明白的答案;如果事情不清楚，最好在评论中要求澄清。 – 2013-04-20 20:42:06

顶点Biconnected和边双连通误解

回答

相关问题