0

假设我们有一个无向图 G = (V,E)，并且我们构造一个新的图 G'，如果两个节点在 G 中有一个共同的邻居节点，则它们是相邻的。如果我们有这样的一个，有人可以解释为什么以下陈述是正确的建筑 G'?

如果 G 有一个大小为 n 的独立集合，则 G' 有一个大小为 n 的匹配。如果 G' 有一个大小为 n 的匹配，则 G 有一个大小为 n 的独立集合。

不幸的是，我不知道这个问题

4

0 回答 0