算法分析
基于最大团问题的两种解法
李源
(中铁成阳管理干部学院陕西咸阳712000)
数事执术费用
摘要：最大围问题(maximum cliqueproblem，MCP)是图论中的一个经典组合优化间题，电是一类NP(NondeteministicPolyniomial)完全问题，也被称为最大独立集树间题。给出了最大困同题的基本定义和其数学描述；分新求解该问题的典型启发式算法，即四溯算法和优先队列分支限界算法，本文主要阐述算法的介绍、算法求解最大困问题的基本思露、特点及性能；最后介绍了测试这费启发式算法性能的测试基准图。
关键词：最大团问题回溯算法优先队列分支限界算法图
中图分类号：TP312 1、基本概念
文献标识码：A
文章编号：1007-9416(2011)09-0132-02
(MaxClique abc=new MaxClique(),
最大团的定义：给定无向图G=(V,E)。如巢USV,且对任意u， VEU有(u，V)EE，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含项点数最多的团，
如果UV且对任意u,vEU有(u,v)EE，则称U是G的空子图。G 的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。 G的最大独立集是G中所含顶点数最多的独立集。对于任一无向图 G=(V.E)其补图G=(V1.EI)定义为：VI=V,且(u,v)EI当且仅当(u v)E
2、最大团问题算法设计思想
2.1最大团问题的国溯算法 2.1.1因隔算法该计思想
设当前扩展结点Z位于解空间树的第偿。在进人左子树前，必须确认从顶点到已选人的顾点集中每一个顶点都有边相连。在进人右子树前，必须确认还有足够多的可选顶点使得算法有可能在右子树中找到更大的团。在具体实现时，用邻接矩阵表示图G，。整型树组V返回所找到的最大团。V二1，当且仅当项点属于找到最大团。无向图G用邻接矩阵存储如图1。
行
????
列
2.1.2由南算法程序设计
? 0-0
图1
② 1 0
0-
? 0-0 0
最大团间题的回溯解法，部分代码如下。
class MaxClique(static int)X; static int n: static int cn : static int bestn; static int bestx;
static boolean (] a;.省略
public class Fac5_7
public static void main(String args(l)
32
万方数据
? 1 0 0 0-
? 1 1 0
int nl=5
int ak]=new int[n1+1];
boolean [] aw=new boolean[n1+1J[n1+1];
aw[1[1]=false;aw[1][2]=true: aw[13]=false: aw[1]
[4]true; aw[1][5]=true;
aw[21]true, aw[2]2]-false,aw[23]true,aw[2]
[4]=false; aw[25]true;
aw[3][1]false;aw[3][2]=true; aw[3][3]=false, aw[3]
[4]=false;aw[3]5]=true,
aw[4][1]-true; aw[4][2]=false;aw[4][3]=false; aw[4]
[4]=faise;aw[4][5]=true;
aw[5][1]=true; aw[52]true;, aw[5][3]=true,
aw
[5][4]=true; aw[5][5]=fa]se;
abc.aaw, abc.nnl,
System.out.printin("最大团顶点数为"+abc.
maxClique(ak));
for(int i=1,i<=nl,i++) System.out.print("
"+abc. bestx[i],
System.out.printlnO),
2.1.3送行结累，如图2 CC:INDONSsst Hicrosoft
windou xp (
LN.
图2
2.2最大团的问题的优先队列分支限界算法 2.2.1优先分支限界筹法思想
在扩展内部结点时，首先考察左子树结点，在左子树结点；加人到当前团中，并检查该顶点与当前团中其他顶点之间是否有边相连。当项点与当前团中的所有顶点之闻都有边相连，则相应的左子树结点是可行结点，否则就不是可行结点。为了检测左子树结点的