![](https://csdnimg.cn/release/download_crawler_static/19223326/bg1.jpg)
第
39
卷第
6
期
2008
年
11
月
太原理工大学学报
Vo
l.
39
No.6
Nov. 2008
JOURNAL
OF
TAIYUAN
UNIVERSITY
OF
TECHNOLOGY
文章编号
:1007-9432(2008)06-0636-04
基于
QO-l
规划模型用分枝
走界法求解最大团问题
续晓欣贾晓峰
2
(1.中北大学应用数学系,山西太原
030051;
2.
太原理工大学理学院,山西太原
030024)
摘
要
z
搜索图的最大团是经典的
NP
难题。通过运用二次
0-1
规划模型(简称
QO-1
规划
l
模
型〉寻得最大团问题的解法,所用的分枝定界法建立在此模型之上。通过一个命题推导出图的最大
团求解问题与一类特殊
QO-1
规划的等价性,借助于求解一般
QO-1
规划的分枝定界法推演出求最
大团问题的分枝定界规则,从而将图论中的经典问题转化成代数问题加以解决,并给出实例说明该
算法的有效性。
关键词
2
最大团
;QO-1
规划
J;
分枝定界法;梯度
中圄分类号
:0157
文献标识码
:A
通常所说的最大团问题是寻找有限阶简单元向
图基数最大的完全子图的问题。在理论上,最大团
问题是经典的
NP-
难题,因此寻找该问题一般多项
式时间复杂度的算法是十分困难的,但一直以来人
们从未停止过对其有效可行算法的探索和追求。精
确算法中最常用的是枚举法;近似算法和启发式算
法常以贪婪算法为基础,以模拟退火算法、禁忌搜索
算法、遗传算法最为经典;除此之外近年来还发展了
→些并行算法,如:人工神经网络方法,
"DNA"
仿生
算法等等。本文给出一种在
QO-1
规划模型基础上
由求模型整数解而寻找图的最大团的方法。
整数规划的一种特殊情形是
0-1
规划,它的变
量取值仅限于
O
或1,
QO-1
是一种特殊的二次
0-1
规划,所求目标函数是二次函数。
文献
[lJ
中所给的
QO-1
规划的一般形式如下:
m
时
X)
=
CTX
十
÷XTQX
,
xε{0
,
1}".
(1)
式中
:Q=(q;j)
川是一个
nX
η
阶的有理矩阵
;C
是
一个
η
维有理向量。(1)式没有线性项时为:
minf(X)
=
XTAX
,X E
{0
,
1γ(2)
式中
,
A=(
句
)nXn
是一个
nX
η
阶有理矩阵,满足
a;;
= C; +
qü
/2
,
且
i
=l=-
j
时
,
a;j
=qü
/2.
命题
1
对于具有顶点集
V={
叫,吨
,
V3
,
…,
叫)的图
G(V
,
E)
,
其最大团问题可等价于以下的线
收稿日期:
2007-06-30
性整数规划问题:
minf(X)
=-
~衍,
i=l
S.
t.
X;
十
Xj
~
1,
(V;
,
v)
巨
~E
且
X
E
{0
,1}". (3)
式中,
(3)
的最优解
X
妈
=
Cxt
,
xz*
,X3* , … ,X
n
*
)
可以
定义图
G
的一个最大团
C:
若
X;*
=
1
,则
V;
εC;
若
xt
==0
,
则
V;
唔
C
,且
C
的基数
ICI
=-
f(X
骨)
[2J
1
主要结果
利用已知条件,命题
1
有下面的二次规划形式。
命题
2
对于具有顶点集
V=
{Vj'
吨
,
V3
,
…,
V"}
的图
G(V
,
E)
的最大团问题可表示成以下的二
次规划形式:
minf(X)
=
XTA'X
,
s.
t.
X;
十
Xj
ζ
1,
(V;
,
Vj)
巳
E
,且
Xξ{0
,1}".
(4)
式中
,
A'
是一个与
Ac
同阶的有理矩阵,
α
吨
u
一
1
,且
i
手
J
,向=吨
证明对于马
,
Xj
ε{0
,1}
,由于
x;+Xj~l
仲
X;.
Xj=O
,
因此
(3)
可以写成以下形式:
minf(X)
=-
~x;
十
2
~
X;.
句,
i=1
i>i
(v"v
,
)EE
s.
t.
X;
+
Xj
~
1,
作者简介
z
续晓欣(1
980-)
,女,山西吕梁人,助教,硕士,主要从事图论及其应用的研究,
CTeD
13835101850