二分图最大(基数)匹配及若干等价问题

设G(V,E)是一个无向图，则V的一个子集A被称为独立集当且仅当不存在两个顶点i和j属于A并且边(i,j)存在于E中. 独立集中元素个数最大的称为最大的顶点独立集.

二. 最小顶点覆盖集的定义
对于任意一个无向图G=(V,E)，一个顶点覆盖集合C（其中C为V的一个子集）满足：对于G中的每一条边(x,y)，至少有一个端点属于C.
求顶点集C（其中C为V的子集），使其大小|C|达到最小。

三. 完全子图的最大顶点集
考虑无向图G(V,E)，设V'为V的一个非空子集。若V'中的任意两顶点i,j都满足边(i,j)存在于E中，则称V'构成一个完全子图（clique）。
目标在于寻找这样的V'集合，并使其阶数（大小）达到最大值。

四.三者的等价性
(1)最大独立点集与最小顶点覆盖集的等价性
假设A为G(V,E)的一个独立点集，令B=V-A，则B为V的子集.
那么很容易就可以得出这样的结论：对于任意一条边(i,j)∈E，有i∈B或j∈B
所以B是图G(V,E)的顶点覆盖集
于是|A|=|V|-|B|，也就是说最大独立点集与最小顶点覆盖集是等价的两个问题.
在这个转化过程中就用到了点的“补集转化”——用点集V减去求解目标集合A，以得到新的目标集合B
(2)最大独立点集与最大完全子图的等价性
假设C为G(V,E)的一个完全子图
令全集U={(