文件名称：基于图匹配思想的最大独立集算法-ansi-vita 62-2016 modular power supply standard
文件大小：2.84MB
文件格式：PDF
更新时间：2024-06-29 16:21:32
集训队论文集
4.1 基于图匹配思想的最大独立集算法 4.1.1 二分图的最大独立集 二分图的最大独立集是一个经典问题。我们有以下定理： 定理 4.1. 对于 n阶二分图 G，α(G) = n − ν(G)，其中 α(G), ν(G)分别为图 G 的独立数和匹 配数。 该定理的证明可以在很多材料中找到，故证明略。 用匈牙利算法或网络流求出二分图 G = (X,Y, E)的一个匹配数 ν(G)，即可得到 G的独 立数 α(G)。另外，用网络流建图后求最小割可以得到一个最大独立集 I。 这个算法只能解决最优化类的独立集问题，不能解决更加复杂的问题（如计数或带有 其它限制等）。 4.1.2 无爪图的最大独立集 二分图的最大独立集给了我们一个思路——求图的最大匹配时，可以通过找增广路不 断增加匹配大小，那么求其它图的最大独立集能否也采用增广的方式？遗憾的是，在任意 图上，两个独立集的对称差16的导出子图不一定是若干条路径或环，所以并不能用找增广 路的方法求最大独立集。 不过，在一种特殊的图上，这种算法是可行的。 定义 4.1. 无无无爪爪爪图图图（claw-free graph）定义为所有导出子图都不是 K1,3的无向图。其中 K1,3称 为爪爪爪（claw），即两部分别含有 1个点和 3个点的完全二分图。 无爪图的最大独立集可以用类似一般图匹配的算法来求解。该算法依赖于以下定理： 定理 4.2. 设 I1, I2 为无爪图 G 的两个独立集，则 G[I1∆I2]的每一个连通块都是一条简单路 径或简单环。 证明. 设 v ∈ I1，则 N(v) ∩ I1 = ∅，在 G[I1∆I2]中，v的度数为 |N(v) ∩ I2|。 假设存在三个不同的点 v1, v2, v3 ∈ N(v) ∩ I2，因为 I2 是独立集，所以 v1, v2, v3 两两不相 邻，因此 G[{v, v1, v2, v3}]是一个爪，矛盾。 因此 |N(v) ∩ I2| ≤ 2，即 G[I1∆I2]的所有点度数均不超过 2，定理得证。 注意到如果 |I1| < |I2|，那么 G[I1∆I2]必然存在一个连通块 C，满足连通块中属于 I2 的 结点比属于 I1 的结点多。由于 C 中属于 I1, I2 的结点交替出现，当 C 为简单环时，C 中属 于 I1, I2的结点一样多，而当 C为简单路径时，C中属于 I1, I2的结点个数相差 1，故必然存 16集合 A, B的对称差 A∆B = {x|[x ∈ A] , [x ∈ B]} 43