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

Question

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

a) 不能有切割顶点。

b)必须有一个循环

c)必须有一个尖端(桥)

d) 色数严格大于 G1 和 G2

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

Correct answer is the option (b)

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

我的方法是:

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

Answer 1

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

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

• 没有切割顶点，因此允许
• 确实有循环，因此 b) 允许
• 没有尖端，因此 c) 被消除
• 色数为 3，而 G1 和 G2 色数为 2，因此 d) 是允许

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

这样你就只剩下 a) 或 b)。
如果你猜a)是错误的，那么你需要找到一个有割点、有环的图。
如果您猜测 b) 是错误的，那么您需要找到一个没有有割点且没有有环的图。

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

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

再次，G1和G2连通，交点不连通。这一次，工会覆盖了其中的三个答案。具体来说，工会

• 确实有一个切割顶点，因此 a) 被消除
• 确实有循环，因此 b) 允许
• 没有尖端，因此 c) 被消除
• 色数为 3，G1 和 G2 的色数也为 3，因此 d) 被消除

注意，我们并没有证明b)是正确的，只是a)、c)和d)肯定是错误的，所以b)是排除法答案。