本来字符串处理相关快写完了。。结果手抖给弄没了。。于是打算填上图论的坑。那么先把今天讲的二分图相关写了吧。

个人认为写的很烂。。。

 

1 二分图的定义与判定

【二分图一般指无向图】对于无向图G，如果可以将图分成两部分S,T，S,T之间有边相连，而S,T自己内部没有边，则称该无向图为二分图。

当然，也有有向图称作无向图的时候。

区别二分图，关键是看点集是否能分成两个独立的点集。对于某图G。我们可以利用交叉染色法判定其是否为二分图。。就是DFS一遍，给他按照黑，白，黑，白的顺序染色，如果发现出现矛盾，则不是二分图，图中有可能有奇环存在。

【补充 重要定理：】

【图中的一个连通块中有奇环，则该连通块中全是奇环。】

 

2 二分图最大匹配

【任意两条边都没有公共端点】的边的集合称为图的匹配。二分图的最大匹配即为找到最多的这样的边

一般我们在数据范围小时采取匈牙利算法，范围大时采取网络流。

算法的具体实现我就不说了。。大家都会。。。

还是说一些经典的问题吧。。比较经典的就是棋盘上面的问题了。

给定一个N行M列的棋盘，已知某些位置禁止放置，求能够放到棋盘上的1*2多米诺骨牌的最大个数？

给定一个N*M的棋盘，有一些格子不能放置棋子，问棋盘上最多能放多少个马，使它们不能相互攻击。

给定一个N*M的棋盘，有一些格子不能放置棋子，问棋盘上最多能放多少个車，使它们不能相互攻击。

有一个N*M(N,M<=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。

 

前两个题显然先对棋盘进行黑白染色，然后把白点和黑点看成两部分，暴力连边做匹配即可。第二个是最大独立集

后两个题都是把行和列看成两部分。显然放车的直接按行列为点，交叉位置为边连接就行。而最后一个需要先横着扫一遍，竖着扫一遍。把横向出来的和竖向出来的交叉部分看成边，连起来跑二分图匹配即可。

 

3一些奇怪的定理

我先都列出来吧。。

 

二分图最小点覆盖=二分图最大匹配

最小路径覆盖=点数－最大匹配。

二分图最大独立集=点数－最大匹配

二分图最大团=补图的最大独立集

【有没有感觉到世界的恶意】

感性感知如下：

 

二分图最小点覆盖=二分图最大匹配：

如果有一条边的两个顶点全不在最大匹配的点上，那么又会多出一条匹配边，所以二分图最小点覆盖<=二分图最大匹配。

如果最小点覆盖比最大匹配小，那么最小点覆盖肯定缺少了一些边。所以二分图最小点覆盖>=二分图最大匹配。

所以二分图最小点覆盖=二分图最大匹配

 

最小路径覆盖=点数－最大匹配&&二分图最大独立集

原谅我，我不会

 

二分图最大团=补图的最大独立集

这是显然的。。。。。

 

 

【关于最小路径覆盖】

DAG上最小路径覆盖-》直接跑

无向图最小路径覆盖-》除以2

不要求每个点只走一次的最小路径覆盖-》floyd

 

4 二分图最大匹配可行边和必须边

 

可行边：

包含在某一个最大匹配方案中的边

对应网络流残量网络tarjan缩点后边的端点在同一个联通分量上或本身是匹配边

必须边：

包含在任意一个最大匹配方案中的边。

对应网络流残量网络tarjan缩点后边的端点在不在同一个联通分量上且本身是匹配边

 

 

感觉自己写了一些很没用的东西。。就是这样。。

算是总结一下吧。。