【文件属性】：
文件名称：基于图匹配思想的最大独立集算法-ansi-vita 62-2016 modular power supply standard
文件大小：2.84MB
文件格式：PDF
更新时间：2021-06-09 22:34:52
集训队论文集
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