algorithm - 两个连通图的并集的属性，如果它们的交集不连通

让G1=(V, E1)and G2=(V, E2)在同一个顶点集 V 上有两个以上顶点的连通图。如果G1∩G2=(V, E1∩E2)不是连通图，则该图G1∪G2=(V, E1∪E2)

a) 不能有切割顶点。

b) 必须有一个循环

c) 必须有尖端（桥）

d) 具有严格大于 G1 和 G2 的色数

==================================================== ========================

正确答案是选项（b）

==================================================== ========================

我的方法是：

问题是我得到了选项 a) 也纠正了我选择图表的方式。所以，我如何确定在考试中要采用什么图表，以便我得到正确的答案，正如您在此处看到的正确答案是选项 b)，但我也得到了 a) 正确的答案。

标签： algorithmgraph

如果您的目标是通过反例来反驳，那么您从一个具有 3 个顶点的简单图形开始了一个良好的开端。

这样的图满足G1和G2连通，交点不连通的要求。然而，工会只反驳了答案 c)。具体来说，工会

下一步是认识到 d) 几乎肯定是错误的。原因：在不改变其色数的情况下向图中添加节点很容易。也就是说应该很容易找到G1和G2是三色的例子，而并集也是三色的。

所以这给你留下了a）或b）。
如果你猜 a) 是错误的，那么你需要找到一个图，它有一个割顶点，并且有一个环。
如果你猜 b) 是错误的，那么你需要找到一个没有割点的图，也没有环。

猜测 b) 是错误的有点问题，因为没有环的图是树或路径，而树和路径充满了切割顶点。

所以下一步是想象一个有切割顶点的图。我想到的第一个这样的图表是沙漏：

再一次，G1 和 G2 是连通的，交叉口是不连通的。这一次，工会反驳了三个答案。具体来说，工会

请注意，我们还没有证明 b) 是正确的，只有 a) c) 和 d) 肯定是不正确的，所以 b) 是消除的答案。