最大团问题研究报告
最大团问题研究报告
2009
摘要：
本文首先对最大团问题从一般性描述和数学描述两个方面进行了概述，其次对其研究发展进行了概括，之后对解决最大团问题的相关算法进行了逐一介绍，并对部分算法进行了比较分析，并对回溯法和分支限界法详细介绍，最后给出了最大团问题的应用领域。 关键字：最大团、蚁群、启发式、智能搜索
1 最大团问题概述
1.1 最大团问题一般描述
给定无向图G=(V，E)。如果U V，且对任意u，v U有(u，v) E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。
如果U V且对任意u，v U有(u，v) E，则称U是G的空子图。G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。G的最大独立集是G中所含顶点数最多的独立集。
对于任一无向图G=(V，E)其补图G=(V1，E1)定义为：V1=V，且(u，v) E1当且仅当(u，v) E。
U是G的最大团当且仅当U是G的最大独立集。
图1 无向图G 1.2 最大团问题数学描述
MCP作为一个整数规划问题有许多等价的描述。整数规划问题的描述(二次0-1问题)： 设：
则： t：(0,1)n 2v x {0,1}n, S 2v,x t 1(S) {xi:i 1,2,...,n}
xi 0,i S
nS其中, 1 , i ， n为图的顶点数。
min f(x) - xi
i 1
s.t.xi xj 1, (i,j) E,x {0,1}n
你可能喜欢
- 最小费用最大流问题
- 最大团
- 最大利润问题
- 网络最大流问题
- 请示报告最大区别
- 运筹学第六章6.5最小费用最大流问题17页
- 6.-5最小费用最大流问题34页
- 第5-6 最小费用最大流问题与中国邮递员问题31页
- 用最小费用最大流理论确定铁路货物运价问题的研究4页
- 最小费用最大流问题3页
- 最小费用最大流问题23页
- 最大利润问题3页
- 二次函数中最大利润问题18页
- 二次函数最大利润问题12页
- 最大利润问题复习课 215页
- 二次函数最大利润问题12页
- 最大利润问题4页
- 网络流与匹配问题最大流,最》43页
- 网络最大流问题24页
- 10-4 网络最大流问题-xfj27页
- 6.4网络最大流问题10页
- 蚁群算法在网络最大流问题中的应用3页
- 网络最大流问题43页
