0

从 Skiena 的书中，这不是硬件，只是我为面试做的准备。

鉴于这个问题，

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

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

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

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

4

2 回答 2

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 之间的边的总和sum from 1 to n是 n^2/2 + n/2，所以我们一起得到
    n^2/2 - n/2 + n^2/2 + n/2 = n^2边缘。

于 2013-04-20T20:14:52.360 回答
0

这张图可能会帮助你（a）：

V={1,2,a,b}

E={(1,a),(1,b),(2,a),(2,b)}

2*2 个顶点

2^2 边

于 2013-04-20T18:02:53.487 回答