二分图

把无向图$G$划分为两个不相交顶点集$U$和$V$,使得每一条边都分别连接$U$、$V$ 中的顶点,即不含有奇环的图

概念

二分图判定

非联通图是二分图当且仅当其每个联通分量都是二分图

匹配

边集$E$满足其中任意两条边没有公共顶点

最大匹配

所有匹配中所含匹配边数最多的匹配

完备匹配

某个匹配中所有的顶点都是匹配点

最大权匹配

带权二分图所有匹配中权值最大的匹配

扩展

最小点覆盖

选出一个点集,使每条边都有顶点在其中,且点数最少
最小点覆盖=最大匹配

最小边覆盖

选出一个边集,使每个顶点都有边在其中,且边数最少
最小边覆盖=二分图点数-最大匹配

最大点独立集

选出一个点集,使所有点之间两两无边,且点数最多
最大点独立集=二分图点数-最大匹配

最小路径覆盖

在有向图$G$中用最少的不相交路径把图中所有点覆盖
拆点建二分图:对于$(x,y)$,连边$(x_1,y_2)$
最小路径覆盖=二分图点数-最大匹配

最小链覆盖

在有向图$G$中用最少的路径把图中所有点覆盖
对$DAG$求出传递闭包后,问题转化为最小路径覆盖
最小链覆盖=二分图点数-最大匹配

最长反链

反链:点集$V$,对于$\forall (u,v)\in V$,满足$u$不能到达$v$且$v$不能到达$u$

$Dilworth$定理:最长反链=最小链覆盖

最大团

选出一个点集,使所有点之间两两有边,且点数最多
最大团=补图的最大点独立集

以上推广到带权形式也是类似的

分享到: