问题描述:团就是最大完全子图。
给定无向图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-最小点权覆盖!!!
/************************************************************************************************************************************************/
分享到:
相关推荐
图论 图论 图论 图论 图论 图论 图论 图论
代数图论代数图论
是一款图论算法软件,用于帮助理解学习图论算法细节及其本质。
代数图论代数图论代数图论代数图论代数图论
图论导引教程图论导引教程图论导引教程图论导引教程
图论
图论课件 图论课件 有用可放心下载 图论课件
并行图论算法并行图论算法并行图论算法并行图论算法
图论及其应用习题解答 图论及其应用习题解答 图论及其应用习题解答 图论及其应用习题解答 图论及其应用习题解答 图论及其应用习题解答 图论及其应用习题解答
ACM算法模板的PDF版本,方便大家打印与使用,所有模板均经过测试。 最短路: SPFA模板 ...图论--最短路--第K短路(IDA*)(IDA Star)模板 ...图论--欧拉回路--弗罗莱算法模板 ...图论--LCA--Tarjan(离线)...图论--强连通
图论算法理论实现及其应用(PDF文字版)
《图论(第2版)》系统阐述图论与算法图论的基本概念、理论、算法及其应用,建立图的重要矩阵与线性空间,论述计算复杂度理论中的NP完全性理论和著名的一些NPC问题等。《图论(第2版)》概念明确,立论严谨,语言...
1. 桥的定义在图论中,一条边被称为“桥”代表这条边一旦被删除,这张图的连通块数量会增加。等价地说,一条边是一座桥当且仅当这条边不在任何环上。一张图可以有零或多座桥。
matlab、图论
图论 (113页).pdf
代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码...
基于图论的图像处理,一些论文跟文档的合集
图论方法及应用图论方法及应用图论方法及应用图论方法及应用图论方法及应用图论方法及应用图论方法及应用图论方法及应用图论方法及应用图论方法及应用图论方法及应用图论方法及应用图论方法及应用图论方法及应用图论...
图论算法及其算法编程,有助于图论初学者对图论的了解以及应用