java - 匹配和完美数学

Question

摘自 Skiena 的书，这不是 HW，只是我为面试做的准备。

鉴于这个问题，

无向图 G = (V, E) 的匹配是一组边，其中没有两条有共同的顶点。完美匹配是所有顶点都匹配的匹配。

(a) 构造具有 2n 个顶点和 n^2 条边的图 G，使得 G 具有指数级的完美匹配。

(b) 构造一个有 2n 个顶点和 n^2 条边的图 G，使得 G 恰好有一个唯一的完美匹配。

我只是不知道如何开始。对于 a，我选择了 n = 3，所以我现在知道我有 6 个顶点和 9 个边，并尝试将它们连接起来，但我不知道这是否是完美匹配。

Answer 1

1. 对于 a):取一个包含 2n 个顶点的完整二部图，两个分区各有 n 个顶点。这些图有 n!完美匹配，当 n > 2 时超过 2^n。

2. 对于 b):我们在 (n,n) 个顶点上构建类似于完整二分图的东西。调用分区 A=(1,2,3,...,n) 和 B=(n+1,n+2,n+3,...2n)。

   让 A 成为一个小集团。

   对于 B 中的每个顶点 n+i，为 A 中的每个顶点 j 添加一条边 (n+i,j)，且 j<=i。例如，只有顶点 n+1 入射到边 (n+1,1)；顶点 n+2 入射到 (n+2, 1) 和 (n+2,2)；顶点 n+3 入射到 (n+3,1) (n+3,2) (n+3,3)。

   这迫使独特的完美匹配成为{e in E | e = (n+i,i) for some i in [1;n]}(尝试证明这一点以练习归纳法)。

   因为 A 是 n 个顶点的团，所以它有 n^2/2 - n/2 条边。 A 和 B 之间的边是从 1 到 n 的总和，即 n^2/2 + n/2，所以我们一起得到
   n^2/2 - n/2 + n^2/2 + n/2 = n^2 条边。