【离散数学 · 图论】支配集、独立集、覆盖集、匹配

（源文档高清截图位于最后）

回顾：
对两个顶点u和v，若有边(u, v)直连，则称u和v相邻。若两条边有公共顶点，称两条边相邻。边与相连的顶点关联。
自环：一条从一个顶点到它本身的边。
极大（小）值＝局部最大（小）值≠全局最大（小）值。

1、对无向图G(V, E)，若，且对任意的v∈(V \ V’)，总存在边(u, v)∈E且u∈V’，则称V’是G的一个点支配集。
换言之：点支配集以外的任意一个点总能与点支配集内的某一个点相邻。
求一个图的最小点支配集是NP困难的。

2、对无向图G(V, E)，若，且对任意的e∈(E \ E’)，存在E’中的边与其有公共点，则称E’是G的一个边支配集。
换言之：边支配集以外的任意一条边总能与边支配集内的某一条边相邻。
求一个图的最小边支配集是NP困难的。

3、对无向图G(V, E)，若，且V’中的任意两点都不相邻，则称V’是G的一个点独立集。
求一个图的最大点独立集是NP困难的。

4、对无向图G(V, E)，若，且E’中任意两条不同的边都没有公共的端点，且E’中任意一条边都不是自环，则称E’是G的一个边独立集，又称匹配。匹配中的边的端点称为饱和点（被匹配点）。
边数最多的匹配叫作最大匹配。如果图是带权图，那么权和最大的匹配称为最大权匹配。
如果一个匹配在加入任何一条边后都不再是一个匹配，那么这个匹配是一个极大匹配。最大的极大匹配就是最大匹配，任何最大匹配都是极大匹配。极大匹配一定是边支配集，但边支配集不一定是匹配。最小极大匹配和最小边支配集大小相等，但最小边支配集不一定是匹配。求最小极大匹配是NP困难的。
如果在G的一个匹配中，G的所有点都是被匹配的，那么这个匹配是一个完美匹配。如果只有一个点不被匹配，那么这个匹配是一个准完美匹配。

5、对无向图G(V, E)，若，且对任意的e∈E，总满足e的至少一个端点在V’中，则称V’是G的一个点覆盖集。
换言之：图的任意一条边总与点覆盖集内的某个点相关联。
点覆盖集一定是点支配集，但是极小点覆盖集不一定是极小点支配集。
一个点集是点覆盖集的充要条件是：其补集是点独立集。因此最小点覆盖的补集是最大独立集。
一个图的任何一个匹配的大小都不超过其任何一个点覆盖的大小。
求一个图的最小点覆盖集是NP困难的。但对二分图有König定理：
二分图的最小点覆盖集与最大匹配的大小相同。

6、对无向图G(V, E)，若，且对任意的v∈V，总满足v与E’的至少一条边相邻，则称E’是G的一个边覆盖集。
换言之：图的任意一个点总与边覆盖集内的某条边相关联。
最小边覆盖的大小可以由最大匹配贪心扩展求得：对于所有非匹配点，将其一条邻边加入最大匹配中，即得到了一个最小边覆盖。
最大匹配也可以由最小边覆盖求得：对于最小边覆盖中每对有公共点的边删去其中一条。
一张图的最小边覆盖的大小加上最大匹配的大小等于图的点数。
一张图的最大匹配的大小不超过最小边覆盖的大小。特别地，完美匹配一定是一个最小边覆盖。
一张图的任何一个独立集的大小都不超过其任何一个边覆盖的大小。