文档介绍：维普资讯
最位独栗, 耸幺同缝筠莒聋
第卷第期运筹学杂志. .
年月人.,
求最佳独立集算法
一
朱年朱嫱』,
【西南交通大学】埘伦比大学,美周
在网络【,,,.卜求最佳独立问题, 』描述为:
川: : ∑,
∈、
..—,【,∈,
。, .
,
本文提的综合算法, 含个了算法, 分别寻求最佳独立集. 必要寸, 综合
应用, 效果更佳. ·
§.网络分解及收缩算法
,蒋二者必有一个且仅有一个属
于最佳独立集【,‘时, 称此点具有留舍逆性,简称百逆.
定理在任一边,歹的端点中, 如乓中三少有一点, 不妨设为点,满足
式的条件,
\/∑.
,‘
式中:—点的权; :。一点所有邻点【
‘
容的点对时, 中权仇小者不计人.
则点与必具有留舍百逆性.
证明不失一般性, 【,的一个端点已满足式. 如∈’,
必有,‘,因共边的蛳点:、不牛¨弈. 特, 』‘,因已设点满足【式, 为保证最
优性, 故必有∈』‘.

图
本文月收到
维普资讯
一期求』他拙集算法
』点, 若存在关系:
】; ,;篆: 】.耋;≯
则称点与一点具有留舍同~性, 简称同一性. 易见, .而三个关系足等价的,
定义寸称点集一一女¨、和共它的点要
么都桐邻, 要么不牛邻,.
例如, 图中的“及点, 图中:
中与,,均不牛『邻的』它点竹
一
, ●●●●●●

一一
图一图∑∑
⋯
弱埘称点集特在有寸称性的点人,将典电某些点、多少不限分别和
共它不同的点连边图中的“点及点与其下方的点连边,如满足
式中:‘一和“点牛邻的乓它点; 『厂和点辑邻的它点.
则称图中“点及点组成的集合为对称点柴. ~
其实,射豫点也满足式限不过在:式右边的点·权和恒为而已.
, ’
、定理在埘称点或崩对称点中,所有点翻具有留舍同一性.
如侧个或个以卜的点,都确另外一个点具有留舍瓦逆性,则这两个或两个
以上的点问必具有留舍同一性. . ’
· 证明’不失一殷性,:取为例说驯之. 图中,两点然届于同一对称点
集. 如果∈,则必有』‘及’』‘,因共边的邻点不、相容.
则, 就将丢失最优性. 同,。当∈』‘,必有“∈,。. 一
的证刿与卜述类以. ,
维普资讯
一一运筹学杂忐卷
, 网络卜的点或点桀『, 存在大撼的瓦逆性、同一性或对称性关系, 这
不难通过边的检查,, 将网络化简.
变换几具有留舍同一。的点,都’合并成一个点, 合并后的点权为被合并各
点的权和,『的关系, 为合并前各点外部关系的综合.
变换几分别具有留舍同一讹的个点集『口, 如存在互逆,且一者被另一者
完全包络寸,则』将两个点集收缩为一点,其点权按下式计算: :
: 一
. , ∑
。
式中: , 一分