nig

整理一下一些有关图论的结论。 以下一般图 $G=(V,E)$，二分图左部点集为 $L$，右部点集为 $R$。 ### 一般图中，最小点覆盖+最大独立集=$|V|$ 考虑到最小点覆盖，最大独立集都可以写成整数规划的形式。 最大独立集：$|V|$ 个 $01$ 变量 $x_i$，$\forall_{(u ......