图论（暂停更新）

最大团

问题描述：团就是最大完全子图。

给定无向图G=(V,E)。如果UV，且对任意u，vU 有(u，v)E，则称U 是G 的完全子图。

G 的完全子图U是G的团当且仅当U不包含在G 的更大的完全子图中，即U就是最大完全子图。

G 的最大团是指G中所含顶点数最多的团。

例如：

(a) (b) (c) (d)

图a是一个无向图，图b、c、d都是图a的团，且都是最大团。

求最大团的思路：

首先设最大团为一个空团，往其中加入一个顶点，然后依次考虑每个顶点，查看该顶点加入团之后仍然构成一个团，如果可以，考虑将该顶点加入团或者舍弃两种情况，如果不行，直接舍弃，然后递归判断下一顶点。对于无连接或者直接舍弃两种情况，在递归前，可采用剪枝策略来避免无效搜索。

为了判断当前顶点加入团之后是否仍是一个团，只需要考虑该顶点和团中顶点是否都有连接。

程序中采用了一个比较简单的剪枝策略，即如果剩余未考虑的顶点数加上团中顶点数不大于当前解的顶点数，可停止继续深度搜索，否则继续深度递归

当搜索到一个叶结点时，即可停止搜索，此时更新最优解和最优值。

/***************************************************************************************************************************************/

最小割

割：设Ci为网络N中一些弧的集合，若从N中删去Ci中的所有弧，即：使得从顶点Vs到顶点Vt的路集为空集时，称Ci为Vs和Vt间的一个割。

最小割：若从Ci中任意删去一条弧，Ci便不再成为Vs和Vt间的割时，称该割满足割的最小性或为最小割。

（ http://baike.baidu.com/view/10778678.htm ）

割就是流网络G=(V,E)的割(S,T)将划分成S和T=V-S两部分，使得s∈S，t∈T
也就是原点和汇点在两个不同的子集中
最小割是指流网络中容量最小的割

最小割=最大流！！！

/********************************************************************************************************************************************/

最小顶点覆盖Or最小点集覆盖

在一个二分图中，找出最少的点，使得这些点能覆盖所有的边。

最小顶点覆盖=最大匹配！！！

最小点权覆盖

在一个二分图中（分为x部，y部），选出一些点，使得这些点覆盖所有的边，并且选出来的点权值最小（这里点是带有权值的！！！）

建立模型：

建立源点s，汇点t，在原二分图中，若存在边 u--v 则建边 s--u 权值为u的点权值，u--v 权值为INF，v--t 权值为v的点权值

最小点权覆盖 = 最小割 = 最大流！！！

最大点权覆盖

最大点权覆盖 = Sum-最小点权覆盖！！！

/************************************************************************************************************************************************/