[科普中国]-点覆盖

点覆盖，在图论中点覆盖的概念定义如下：对于图G=(V,E)中的一个点覆盖是一个集合S⊆V使得每一条边至少有一个端点在S中。

定义 在图论中点覆盖的概念定义如下：对于图G=(V,E)中的一个点覆盖是一个集合S⊆V使得每一条边至少有一个端点在S中。图G的顶点覆盖是一个顶点集合V，使得G中的每一条边都接触V中的至少一个顶点。我们称集合V覆盖了G的边。最小顶点覆盖是用最少的顶点来覆盖所有的边。顶点覆盖数是最小顶点覆盖的大小。相应地，图G的边覆盖是一个边集合E，使得G中的每一个顶点都接触E中的至少一条边。如果只说覆盖，则通常是指顶点覆盖，而不是边覆盖。1

相关定义最小点覆盖最小点覆盖：就是中点的个数最少的S集合。普通图的最小点覆盖数只能用搜索解。
结论：二分图的最小点覆盖数=该二分图的最大匹配数。

最小边覆盖边覆盖的概念定义：边覆盖是图的一个边子集，使该图上每一节点都与这个边子集中的一条边关联，只有含孤立点的图没有边覆盖，边覆盖也称为边覆盖集，图G的最小边覆盖就是指边数最少的覆盖，图G的最小边覆盖的边数称为G的边覆盖数。
结论：二分图的最小边覆盖数=图中的顶点数-（最小点覆盖数）该二分图的最大匹配数。

最大匹配匹配：在图论中，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
算法：匈牙利算法求二分图的最大匹配。

最小路径覆盖DAG图的最小路径覆盖可以转化为二分图后求解。

最大独立集最大独立集：在N个点的图G中选出m个点，使这m个点两两之间没有边的点中，m的最大值。
结论：二分图的最大点独立数=点的个数-最小点覆盖数（最大匹配） 。
证明：除过最小点覆盖集，剩下的点全部都是互相独立的，因为它们任意两个点之间都没有直接的连边。
我们用反证法来证明一下，设最小点覆盖集为V，假如有两个没在V中的点之间有一条边，那么这条边就不会被V中的点所覆盖，那么V就不是最小点覆盖集，又因为V是最小点覆盖集，所以刚才假设的两个点时不存在的，除过V之外的点都是两两相互独立的。

例子任何一个图的顶点集合都覆盖了它的边集合。如果图中不含有零度顶点，则反过来也成立。2

完全二部图Km,n的顶点覆盖数为min(m,n)，边覆盖数为max(m,n)。

性质图的顶点数目等于顶点覆盖数与最大独立集合的大小之和（Gallai 1959）。

本词条内容贡献者为:

王伟 - 副教授 - 上海交通大学