一些定理

一、最小点覆盖=最大匹配

即，选一些点染色，要求图中所有边至少有一端被染色。

证明：

涂色方案：设匹配点为红点，未匹配点为蓝点。易知，一对匹配的红点，最多只有一个点会连接蓝点。将这个连接了蓝点的点染色。

合法性：所有匹配边显然已经合法了，考虑非匹配边。非匹配边有一个性质：它至少与一条匹配边有公共端点。所以那条与它有公共端点的边被合法化时，这条非匹配边也会合法。

最优性？

二、最小边覆盖=总点数-最大匹配

即，选一些边染色，要求对于图中任意点 \(u\)，至少有一条与 \(u\) 相连的边被染色。

证明：

考虑每个点怎么被染色。最暴力的就是随便找一条与它相连的边染色。考虑优化，一条匹配边可以使两个点合法，所以我们尽量选匹配边，最终答案就会减少匹配边的数量，最大化匹配边数量，最终答案就会减少最大匹配数。

三、最大独立集=总点数-最大匹配数

图的最大独立集是一个最大的点集，要求任意两点之间没有边相连。

证明：

问题等价于：去掉最少的点，同时删除与其相连的边，使得剩下点之间没有边。删除的那些点就是最小点覆盖问题，所以删除的最小的点的数量就是最大匹配数。

四、最小路径覆盖

这个问题是针对DAG的。给出一个有向图，请用最少的有向路径，覆盖所有的顶点。同一个顶点只能被一条路径覆盖。

根据DAG建出一个二分图 \(G\)：把每个点拆成两个点。分别表示这个点的入度和出度。再把DAG上的边连到 \(G\) 中

结论：最小路径覆盖= DAG点数 - \(G\) 的最大匹配

证明：

因为是求一条链，链上的点，除了起点和终点，其他点的出度入度都为 \(1\)。所以对应着二分图上一个点最多只有一个匹配。每一条链都可以在二分图上表示出来。让链的数量最少，等价于让入度为 \(0\) 的点变少，等价于让二分图第一部的非匹配点最少。也就是要找到最大匹配。