（应用数学专业论文）2划分问题的算法改进和相关性质.pdf

摘要 摘要 电路划分问题( c i r c u i tp a r t i t i o n i n g ) 是超大规模集成电路( v e r yl a r g es c a l ei n t e g r a t i o n ，以下简称v l s i ) 布线中的一个重要过程，它是降低集成电路布线复杂 性、提高电路性能的一种有效方法，因此设计相应的电路划分算法就显得十分必 要。 针对该问题，在过去的几十年中不断有人提出各种算法来优化和解决它，其 中最为著名的就是k e r n i g h a n 和l i n 在1 9 7 0 年提出的2 一划分算法。但是这个算法 存在一个缺陷，即算法结果对于初始划分状态的选择具有很强的依赖性，而这可 能会导致不同的初始状态会产生截然不同的结果。因此对初始状态选择的改进就 成为一个十分重要的问题。在本篇文章的开始，我们首先提出一种基于k e m i g h a n l i n 算法的2 一划分贪婪算法。这一算法通过依据一定的标准来选取初始划分状态， 减少其选择的随意性，从而消减初始状态对于算法最终结果的影响。随后我们又 介绍了2 一划分图的连通性，正则性和h a m i l t o n 性等性质，为进一步研究2 一划分 问题提供了相关的理论依据。 关键词：2 一划分，k e m i g h a n - l i n 算法，初始划分状态，2 一划分图 1 1 1 a b s t r a c t a b s t r a c t p a r t i t i o n i n gp r o b l e mi sav e r yi n d i s p e n s a b l ep r o c e s si nv e 巧l a r g es c a l ei n t e g r a t i o n ( v l s i ) d e s i g na n di sa ne f f e c t i v em e t h o dt or e d u c et h ec o m p l e x i t yo fv l s i a n di m p r o v et h ep e r f o r m a n c eo ft h ec i r c u i t t h e r e f o r eu n d o u b t e d l yh o wt od e s i g nt h e a l g o r i t h mo ft h ec i r c u i tp a r t i t i o n i n gb e c o m e sv e r yi m p o r t a n t i nt h ep a s ty e a r s ，t h i sp r o b l e mh a sa t t r a c t e dac o n s i d e r a b l ea m o u n to fr e s e a r c h i n t e r e s ta n dt h e r ea r ev a r i o u sh e u r i s t i ca p p r o a c h e s t h em o s tf a m o u so n eo fw h i c hi s t h ec l a s s i c a lt w o - w a yp a r t i t i o n i n gt e c h n i q u e ，p r o p o s e db yk e r n i g h a na n dl i ni n 19 7 0 h o w e v e r ，t h i sa l g o r i t h mh a sa no b v i o u sd r a w b a c k ，w h i c hi st h ea l g o r i t h mi sh i g h l y s e n s i t i v et ot h ec h o i c e so fi n i t i a lp a r t i t i o na n dt h ef i n a lr e s u l t sv a r ys i g n i f i c a n t l ya sa c o n s e q u e n c eo fd i f f e r e n ts t a r t i n gp o i n t s t h u st h a ti sv e r yn e c e s s a r yt om a k ea ni m - p r o v e m e n to nt h ec h o i c eo ft h ei n i t i a lc o n d i t i o n i nt h ef i r s tp a r to ft h i sp a p e r , w e p r o p o s ean e wg r e e d ya l g o r i t h mw h i c hi sb a s e do dt h ek e m i g h a n - l i na l g o r i t h m ，t o c h o o s et h ei n i t i a lc o n d i t i o na c c o r d i n gt os o m ec r i t e r i o n a n do u ra l g o r i t h mc a no v e r c o m et h ei n f l u e n c eo ft h ei n i t i a lc o n d i t i o no nt h ef i n a lr e s u l t s t h e nw es h o ws o m e p r o p e r t i e so ft h et w o w a yp a r t i t i o n i n g ，s u c ha sc o n n e c t i v i t y , h a m i l t o n ，e t c k e yw o r d s ：t w o - w a yp a r t i t i o n i n g ，k e r n i g h a n - l i na l g o r i t h m ，t h ei n i t i a lc o n d i t i o n ， t w o - w a yp a r t i t i o n i n gg r a p h i v 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：起晶 。叩年莎月t 日 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：起晶 。口d 7 年莎月f j 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 第一章引言 第一章引言弟一早，ii 1 1v l s i 问题的发展和介绍 随着计算机技术的迅速发展，集成电路越来越为人们所广泛熟知。它是采用 专门的设计技术和特殊的集成工艺，把一个电路中所需的晶体管、二极管、电阻、 电容和电感等元件及布线互相连接在一起，放置在一小块或几小块半导体晶片或 介质基片上，然后封装在一个管壳内，成为具有所需电路功能的微型结构，其中 所有元件在结构上已组成一个整体。这样，整个电路所占体积将大大缩小，且引 出线和焊接点的数目也大为减少，从而使电子元件向着微小型化、低功耗和高可 靠性方面迈进了一大步。与晶体管相比，它具有体积小，重量轻，引出线和焊接 点少，寿命长，可靠性高，性能好等优点，同时成本低廉，便于大规模生产。此 外，用集成电路来装配电子设备，其装配密度可提高几十倍甚至几千倍，设备的 稳定工作时间也可大大增加。这使得它不仅在工、民用电子设备如收录机、电视 机、计算机【1 】等方面得到广泛的应用，同时在军事【2 】 3 】、通讯 4 】、遥控等领 域也发挥着重要的作用。 半个世纪以来，集成电路主要经历了中小规模( m s i ) 、大规模( l s i ) 和超大规 模( v l s i ) 这几个发展阶段，其中超大规模集成电路是指在一块芯片上集成的元 件数超过1 0 万个，或门电路数超过万门的集成电路。利用超大规模集成电路技术 可以将一个电子分系统乃至整个电子系统“集成”在一块芯片上，完成信息采集、 处理、存储等多种功能。目前超大规模集成电路的集成度已达至1 6 0 0 个晶体管，线 宽达n o 3 微米，主要用于制造存储器和微处理机。 随着集成度的日益提高、特征工艺尺寸的不断缩小、性能与功耗的同步增长， 给人们进行v l s i 设计提出了越来越大的挑战。其中v l s i 布线问题作为v l s i 设计 中的一个重要环节，对电路性能的可靠性也起着十分重要的作用。这一问题简单 的说，就是通过设计相应的优化算法，将数以千计的元件通过电路连线布局在独 立的芯片之上，以使得算法的目标函数，即线网总长，路径时延，可布性等达到 优化 5 】。 第一章引言 这个过程主要包括两个步骤， 第一，依据一定的标准确定元件在芯片上的位置； 第二，通过线路将这些元器件连接起来。 一般来说，v l s i 问题所涉及的元件的数目是十分巨大的，过程也是很复杂 的 6 】。因此我们解决这类问题常用的方法是将一个较大的电路划分成几个较小 的电路，再通过对这几个较小的电路分别布局的方式达到优化。如下图所示，图l 一 1 给出的是一个电路模型图，而图1 2 和图1 3 是将这个电路分割成几个小电路的 两种不同的方法：g 和q 。 珥 丑 珂 珂 图1 1 电路模型图 图1 - 2 表示分割方法c l 那么我们自然会问如何对电路进行划分，或者说电路划分的主要依据是什 么? 接下来将详细说明这一问题。 2 第一章引言 卜 】j僻 博 畦 勺厂 1 虹 卜 r 1 e 肚一臣轨 r 1 j i l i 图1 - 3 表示分割方法c 2 1 2 划分问题的数学模型 在现实生活中，人们总是希望能够花费最少的费用来实现效益的最大化，当 然v l s i 问题也不例外。在超大规模集成电路中，如果元件之间的连线过长，就 会导致电子信号传输的速度减慢【7 【8 ，布线所需的区域和花费相应增加【9 ，这 会对电路性能的提高，成本的降低产生不利影响。因此，一种理想的划分方式应 该是在不影响电路性能的前提下，尽可能缩短元件之间连线的长度，即给定一 个电路c ( c 由不同的元器件和元器之间的连线组成) ，我们的目标就是将g 划分 成k 个子电路，以使得连接这几个子电路之间的元器件的连线最短【1 0 11 1 1 2 。 事实上，如果我们把电路c 用图g ( ve ) 来表示，电路中的所有元件用顶点 集y 代表，元件之间的连线用边集e 代表，那么电路划分问题就转化成一个图的 划分问题 1 3 ，即将一个图分成几个子集，并使得这些子集之间的割边集的权重 和最小( 如图2 ) 。但是即便做了这样一个转化，这类问题仍然并不容易解决，甚 至这类问题的最简单的形式，即2 一划分问题，因其是一个n p - 完备问题【1 4 】，也 没有最优算法。 下面我们来看2 一划分问题的一个简单例子， 假设一个电路有2 n 个元件，我们把它分割成两个“平衡 1 5 】的子电路，即 每一个子电路元件的个数为佗，使得两个子电路之间的连线和最小。 3 第一章引言 电路c 图g 2 图2 6 如果我们不考虑电路的“平衡性 ，那么可以应用最大流最小割算法很容易 得到最优解 1 6 】。但是，电路的“平衡性”往往在实际应用中有着极其重要的作 用，因而是不能够被忽略的。 由于2 一划分问题没有有效算法，因此一直以来不断有人尝试提出一些近似 算法来解决这一问题 1 7 】 1 8 】，这其中就包括k e m i g h a n 和l i n 在1 9 7 0 年提出的一个 经典的2 一划分算法 1 9 】( 简称k - l 算法) 。随后又有许多人对这一算法做出了相 应的改进【2 0 【2 1 】。例如，s c h w e i k e r t 和k e r n i g h a l l 提出的一种用以解决多指针问题 的网络割模型算法 2 2 】，f i d u c c i a 和m a t t h e y s e s 提出的用以大幅度改进k e m i g h a n l i n 算法复杂度的f _ m 算法 2 3 ，而后为了解决局部最优问题，模拟退火算法也被 引入到图的划分问题中来 2 4 】 2 5 2 6 】。 4 第二章基于k e m i g h a n - l i n 算法的近似算法 第二章基于k e r n i g h a n - l i n 算法的近似算法 2 1 k e r n i g h a n - l i n 算法 k e m i g h a n - l i n 算法是k e r n i g h a n 矛t l l i n 在1 9 7 0 年提出的用以解决“平衡”的2 一划 分问题的一个近似贪婪算法 1 9 ，它的基本思想是首先将图g 任意分成两个顶点 个数相等的子图g 1 ，g 2 ( 即初始划分状态) ，再通过计算这两个子集各个顶点的内 外部连边的权重之差，分别从g 1 ，g 2 中选取两个顶点互相交换，使得交换后割边 集的权重和减少的最多。这其中要求之前被交换过的顶点交换后被“锁定”，即 以后的交换过程不再参加交换。这个过程会一直进行下去，直到所有的顶点都被 交换过一次后停止。然后回溯整个交换过程，寻找割边集权重和最小时的划分状 态，即为算法得到的最终划分。 实验结果表明，这个算法对于顶点的平均度数大于3 的图，有着比较令人满 意的运行结果和运行时间 2 7 ，但是，对于稀疏图来说，它所得到的运算结果往 往是局部最优值，和实际的最优结果相差较大。除此之外，它的最终结果的好 坏在一定程度上也会取决于初始划分状态的选择，即初始划分状态选取的随意 性会使得运算时间增力 1 1 2 8 ，运算结果也会因初始值的不同相差较大 2 9 。因此， 对k e r n i g h a n - l i n 算法进行一定程度的改进，消减初始值对运算结果的影响是十 分必要的。 2 2 2 一划分问题的相关概念和定义 首先来回顾几个常用的概念。 一般几何上将图定义为空间一些点( 顶点) 和连接这些点的线( 边) 的集合。 而在图论中将图定义为一个对偶g = ( ke ) ，其中y 表示顶点的集合，e 表示边 的集合，并且顶点集y 和边集e 之间存在这样一种对应关系，即如果边e e 的两 个端点分别为u 和u ，那么e 可写成e = ( 乱，秒) 。 5 第二章基于k e m i g h a n - l i n 算法的近似算法 一般图g 的顶点个数用i yj 表示，边的个数用i ej 表示。 如果顶点v 是边e 的一个端点，则称边e 与顶点v 相关联( i n c i d e n t ) ；如果顶 点u ，v v ，且( u ，u ) e ，则称钆和v 是邻接的( a d j a c e n t ) 。 在图g 中，与顶点v 相关联的边的个数被称为点v 的度数，记为d g ( u ) 。若顶 点v 的度数为1 ，则点v 被称为叶子点。 如果一个图g 中每个顶点的v 的度数都是常数k ，则称图g 为七一正则图。 对于图g = ( ve ) 和图g 7 = ( v 7 ，e 7 ) 来说，若有y 7 y 和e 7 e ，则称 图g 7 = ( v 7 ，e 7 ) 是g = ( ve ) 的一个子图。进一步，若y 7cy 和e 7ce ，则称 图g = ( v ，e 7 ) 是g = ( ve ) 的一个真子图。 定义2 1p = v o e l v l v k - - 1 e 惫v 惫为图g 的一个顶点和边的交替序列，且边e t 的端 点为v i - - 1 和仇，其e e i = 1 ，2 ，k 。若序列中的每条边和顶点各不相同，则称“为 图g 的一条路( p a t h ) ，v o 和v k 分别称为p 的起点和终点。 定义2 2 对于图g 来说，若g 的两顶点钆和口之间存在一条路，则称u 和v 是连通的； 若g 的任意两个顶点连通，则称图g 是连通的，否则是非连通的。而非连通图可 分解为若干连通分支。 定义2 3 设图g 是连通图，若从图g 中去掉边e 后，g 不再连通，则称边e 为图g 的 割边；若s e ，从图g 中去掉属于s 的所有边之后，图g 不再连通，但去掉s 的 任何真子集的边，图g 仍然保持连通，则称s 为图g 的一个割边集，也就是说割边 集。s 是使连通图g 失去连通性的最小的边集合。 定义2 4 如果图g 存在这样一条路厶即路f 遍历图g 的每个顶点恰好一次，则称 路f 为图g 的h a m i l t o n 路。 下面给出2 一划分问题的精确定义： 定义给定一个图g = ( ve ) ，ke 分别为它的顶点集和边集，且i y i = 2 n 。任取 点u v ，边e e ，e 的权重记为u ( e ) ，将顶点集y 划分成为两个顶点个数相等的 子集，k ，使得k 与k 之间割边集的权重和最小，其中n = 仍，uk = v 。 6 第二章基t - k e m i g h a n - l i n 算法的近似算法 如果令p ( 乱) 代表点u 所属的子集，则与之间割边集权重和可表示为 c o s t = u ( e ) 一 v e = ( u ，口) p ( 1 正) p ( ) 在详细说明如何解决这个问题之前，仍然先来看两个概念： ( 2 1 ) 外部连线：任意点z ，若有e = ( z ，秒) ，y k ，则边e 叫做点z 的外部连 线， u ( e ) 为点z 的外部连线的权重和，记为邑。 v e = ( ，掣) y e 屹 内部连线：任意点。，若有e = ( z ，) ，y v 1 ，则边e 叫做点z 的内部连 线， ( e ) 为点z 的内部连线的权重和，记为l 。 v e = ( ，) y , q 均 我们把历和厶的差称为d ( z ) ，即d ( z ) = 厶一b ，同时定义函数q = 翌伽 d ( z ) ) 。 图3 例如，在图3 中点a 的外部连线为e ，e 2 ，e 3 ，内部连线为e 4 ，e 5 。若设图中每条边的 权重均为1 ，则玩= 3 ，厶= 2 ，d ( x ) = l b = 一1 。 2 3 算法的详细步骤 正如前面所提到的一样，k e m i g h a n - l i n 算法的缺陷主要在于，初始划分状态 选取的任意性会对最终结果的好坏产生较大的影响，因此我们所要做的就是使初 始划分状态的选取不是随意的，而是依据一定的标准来确定的。下面给出算法的 基本思想。 整个算法主要包括两个阶段： 7 第二章基于k e r n i g h a n - l i n 算法的近似算法 图4 第一阶段通过贪婪算法逐步去掉权重较小的边，直至图g 不再连通为止。这 时y 被划分成两个子集，k ，这两个子集之间的连边即为割边集，这 时的状态就是初始划分状态。 这里需要说明的几点是： ( 1 ) 在去边的过程中，叶子点不在考虑范围之内，这主要是因为如果边e 的其中一 个顶点为叶子点，则去掉边，v 被划分成两个子集k ，其中i l = 1 ，i i = l y l 一1 。这会导致当l y | 彳艮大时，两个子集的顶点个数相差太多，影响图形的 平衡性( 如图4 ) 。 ( 2 ) 在上述过程中，如果有多条边符合选取条件，即这几条边的权重相等，并且 去掉它们当中任何一条边图g 都会不连通，则依据以下优先性去边。 ( a ) 去掉某条边后，y 恰好被划分成两个顶点个数相等的子集，k ； ( b ) 如果没有边满足( a ) 条件，则在这些权重相等的边中，选取满足这样条件 的边，即去掉这条边后所形成的割边集权重和最小。 下面我们来看一个例子： 例2 1 在图5 j 中，边( d ，e ) ，( e ，) 的权重最小且相等，其中去掉边( d ，e ) ，y 被划分 成两个顶点个数相等的子集，k f 如图5 2 ，j ，去掉边( e ，) ，y 被划分成两个顶点 个数不等的子集w ，似口图5 3 ) 。依据上述原则似) 应该去掉边( d ，e ) 。 8 第二章基- - - k e m i g h a n - l i n 算法的近似算法 b a l到u 7 d ef 1 0 夕2 2 鼍 c 图5 1 e f 1 0 y - j ! 2 2 f ， 。 图5 2 、 d夏名 -： 一 2 ，72 图5 - 3 9 g h 去掉边( d , e ) 后，图g 被 分割成v 1 和v 2 两个子集 去掉边( e ，f ) 后，图g 被分割成v i 和啦两个 子集 第二章基于k e r n i g h a n - l i n 算法的近似算法 第二阶段经过第一阶段后，y 被划分成和两个子集，其中 n = d ，uk = v 不妨令l i = n l ，i k l = n 2 ， ( 1 ) 如果 z 1 = 几2 ，即图g 已经被划分成两个顶点个数相等的子集，则不需 要再移动任何点： ( 2 ) 如果n 1 = d ( z 1 ) ，并将它从子集k 移到子集中去，这时变 为一 z ，) ，变为+ z 1 ) ，即时和订。然后更新曙中所有点的d ( 。) 值，重新 计算这一取值，仍然选取d ( z ) 值最小的点x 2 ，这时q = r a i n z d ) ) = d ( x z ) ， 将它从子集w 移到子集k 1 中去。反复执行这个过程，直到将z ，z 2 ，z 3 ，x n 2 - , 1 这旦铲个点从k 移动到中，形成一个新的分割“，( 1 叫i = i 巧i ) 为止。 下面给出整个算法的详细过程： 算法实现 s t a g e1 令g = ( ve ) ，s = d ，e 7 是由图g 中两个端点均非叶子点的边组成的集 合： s t e p1 当e 7 d 时，从e 7 中挑选权重u ( e ) 最小的边e 。 情况1 存在多条边权重相等且最小，并且去掉它们当中任何一条边图g 都 会不连通，则若存在边e ，使得去掉它之后，图g 分割成两个顶点个 数相等的子图g 1 和g 2 ，则结束算法。否则，在这些权重相等的边中， 选取满足这样条件的边，即去掉这条边后所形成的割边集的权重和 最小。 情况2 存在多条边权重相等且最小，但是去掉它们当中任何条边图g 仍 然连通，则任取一条边从图g 中去掉，进行s t e p2 ； 情况3 只有一条边权重最小，将这条边从图g 中去掉并检查g 的连通分支 的个数： 1 0 第二章基于k e r n i g h a n - l i n 算法的近似算法 ( 1 ) 如果图g 的连通分支个数为1 ，则进行s t e p2 ： ( 2 ) 如果图g 的连通分支个数为2 ，即g 分割成两个子图g 1 和g 2 ，则结 束s t a g e1 ，进行s t a g e2 s t e p2 令s = s + e ) ，g = g 一 e ) ，并更新e 7 ，令其为图g 中端点均非叶子 点的边组成的集合，进行s t e p1 ； s t a g e2m ，k 为s t a g e1 确定的初始划分，且uk = y ，nk = 仍。令i i = n 1 ，i l = n 2 ，q u e u e 卜d ，i 卜1 ，= ，= k ； s t e p1 计算所有f l 勺d ( x ) 值( 其中x ) ； s t e p2 选取使得d ( z ) 值最小的点x i k ( q i = d ( x t ) = 厶一易) ，并 令q u e u e 卜q u e u e + _ 既) ，“= 吖+ x t ) ，= 鹾一 兢) ； s t 印3 如果= ，则算法停止；否则更新中所有点的d ( 。) 值，i i + 1 ， 回到s t e p2 。 下面我们来看一个例子： 例2 2 把图6 中的图g 划分成两个顶点个数相等的子集，并使得划分之后，两个子 集之间的割边集的权重和最小。 b h 6c 图6 g 5 f 第二章基z j - - k e m i g h a n - l i n 算法的近似算法 h b 6 c 图7 1 g 5 f 根据上述算法过程可知，首先应该在图g 中选取权重最小的边，那么由观察 不难得到，应选择边( o ，c ) 。去掉边( n ，c ) 后，得到图7 - 1 。 由图7 1 可知，图g 仍然连通，所以应该继续去边。图中边的最小权重为4 ， h b 6 c 图7 - 2 g 5 f 共有3 条边的权重等于4 ，即边( n ，6 ) ，( d ，e ) ，( d ，允) ，且去掉他们之中的任何一条， 图g 仍然连通，所以可从中任选一条，不妨去掉边( n ，b ) ，得到图7 2 。 1 2 第二章基于k e r n i g h a n - l i n 算法的近似算法 b h 6 c 图7 - 3 由图7 2 可知，图g 仍然连通，所以应该继续去边。图中边的最小权重仍然 为4 ，共有2 条边的权重等于4 ，即边( d ，e ) ，( d ，尼) ，所以可从中任选一条，不妨去掉 边( d ，e ) ，得到图7 3 。 b h 6c 1 3 图7 4 g 5 f 第二章基- j = k e m i g h a n - l i n 算法的近似算法 由图7 3 可知，图g 仍然连通，所以应该继续去边。图中边的最小权重还是 为4 ，且只有边( d ，九) 的权重等于4 ，所以去掉边( d ，h ) ，得到图7 - 4 。 去掉边( d ，允) 后，图g 分成两个连通分支和，其中的顶点个数为2 ，k 的 顶点个数为8 ，至此算法的第一阶段结束，接下来进行算法的第二阶段，即从较 大的连通分支k 的顶点个数中移动3 个顶点到较小的连通分支。 在算法第二阶段，首先应计算较大连通分支中各个顶点的d ( z ) 值，从而选 取d ( z ) 值最小的顶点，将它从较大分支中移动到较小分支中去。由图7 5 可知， ；h 图7 5 g 5 f 点b 和点h 的d ( z ) 值最小，不妨移动点h ，得到两个新的连通分支k 7 和，其中“= a ，d ，九) ，吃= p ，c ，e ，f ，夕) ( 如图7 6 所示) 。 经过移动后，产生了两个新的连通分支，所以要重新计算较大的分支，即以中 各点的d ( z ) 值。由图7 6 可知，点夕的d ) 值最小，所以将点夕从中移到“中去， 再得到两个新的连通分支巧和嘭，其中k = a ，d ，h ，9 ) ，= 6 ，c ，e ，厂) ( 如 图7 7 所示) 。此时，整个图g 划分成两个顶点个数相等的连通分支，即得到我们 想要的划分，至此算法完全结束。 1 4 第二章基于k e m i g h a n - l i n 算法的近似算法 b 图7 - 6 h 6c 图7 7 1 5 g ， 5 f g 5 f 第二章基于k e m i g h a n - l i n 算法的近似算法 在上述例子当中，我们通过本篇文章中所论述的这个算法，将图g 划分成了 两个顶点个数相等的子集嵋和嘭，其中w = 乜，d ，h ，9 ) ，嘭= 6 ，c ，e ，) ，割边 集s = ( n ，6 ) ，( a ，c ) ，( d ，e ) ，( g ，) ) ，其权重和为1 6 。而通过实验验证，我们可以知 道上述例子中，图g 的最优划分即为w = o ，d ，h ，夕) ，嘭= p ，c ，e ，) ，与这个 算法得到的结果一致。因此这一算法对改进初始状态的选取是有着比较好的结果 的。 以上主要讨论的是“平衡”的2 一划分，并没有涉及子集顶点个数不相等的2 划分和七一划分等更为一般的情况。事实上，只要对上述算法的第二阶段稍作修 改，它同样适用于子集顶点个数不相等的2 一划分和尼一划分，这里不再一一讨论。 1 6 第三章2 一划分问题的一些相关性质 第三章2 一划分问题的一些相关性质 前一章我们讨论了2 一划分算法的改进，在这一章中我们将继续探讨2 一划分 问题的一些性质。在讨论之前，有必要先定义几个概念。 定义3 1 任给图g = ( ve ) ，对于它的任意2 一划分 = x l ，x 2 ，z 礼) ，= z 竹+ 1 ，x n q - 2 ，x 2 n ) ， 我们用6 ( ，k ) 来表示它。 定义3 2 若有图g 的两个2 一划分6 ( ，k ) 和6 ( “，) ，其中 = x l ，x 2 ，x i ，z 几) ，k = z 竹+ 1 ，x n + 2 ，茁j ，x 2 n ， “= z 1 ，z 2 ，巧，z n ) ，= z n + 1 ，x 竹+ 2 ，x i ，x 2 扎) ， 即可以通过交换和k 中的一对顶点( 戤，巧) 得到巧和e ，那么就称6 ( ，k ) 和 6 ( 巧，) 是可交换的。 利用上述定义，我们可以构造一个新图g 7 = ( y 7 ，e ，) ，其中顶点集y 是由这 样的点组成的集合，即图g 7 中的任意一个顶点u 代表原图g 中一个2 - ：皂l j 分。且若 任意两个2 一划分状态6 ( ，k ) 和6 ( k 7 ，“) 是可交换的，那么这两个划分所对应 的顶点u 1 和铭2 之间就有一条边相连，则边集e 7 即为这些边组成的集合。通过这个 过程构造的这个新图g 被称为2 一划分图。 那么所构造的这个新图g 具有那些性质昵? 下面我们将一一讨论。 3 12 一划分图的正则性 在这节当中，我们所要研究的是2 - 戈l j 分图作为一类比较特殊的图，它的顶 点度数是否具有比较特殊的性质呢? 1 7 第三章2 一划分问题的一些相关性质 事实上，根据前面2 一划分图的构造原理，求图g 7 中一点u 的顶点度数，即是 求它所对应的2 一划分6 ( ，k ) 与多少个其他的2 一划分存在可交换关系。接下来 我们详细论述这一问题。 对于任意的2 一划分6 ( m ，k ) 来说，若 = x l ，x 2 ，z n ) ，k = x n + 1 ，x n + 2 ，x 2 n ) ， 则如图8 1 所示，点z l 可与中点。n + l 交换形成一个新的划分6 ( ，吃) ，同 样也可与点z 礼+ 2 x 2 n 交换( 图8 2 ，图8 - 3 ，图8 4 ) ，形成另外礼一1 个不同 的划分。那么按照上述定义，6 ( ，k ) 与右边的n 个2 一划分都是可交换的。 x lx n + lx n + lx l x 2 x n + 2 x 2x n + 2 i ： ：e 鲁- ： i x n 1 x 2 n 1 x n 1x 2 n 1 x nx 2 n】【nx 2 n 图8 1x 1 与x n + l 交换 x 1x n + 1x 2 n 1x n + 1 x 2x n + 2 x 2 x n + 2 i i i ：鼍-： i i x n 1x 2 n 1x n 1x l x n x 2 n x nx 2 n 图8 3x l 与x 2 n 1 交换 x 1 x n + l x 2x n + 2 ： ：嵋 i ) 【n 1x 2 n 1 x n x 2 n x n + 2x n + 1 x 2x 1 i i m i i i x n 1x 2 n 1 x nx 2 n 图8 2x l 与) 【n + 2 交换 x 1 ) 【n + 1x 2 nx 叶1 x 2 x n + 2 x 2x n + 2 i i ：e 卜： ： i x n 1 x 2 n 1x n 1 x 2 n 1 x nx 2 nx nx i 1 鍪t 8 - 4x 1 与x 2 n 交换 同理，x 2 也可与z 计1 ，z 他+ 2 ，x 2 n 交换，交换之后产生礼个新的2 一划分，这 些2 一划分与6 ( ，k ) 也是可交换的。中一共有n 个点，所以6 ( ，) 可与n 2 个点 可交换，即点u 的度数为n 2 。又由点钆的任意性可知，图g 7 中所有点的度数均为n 2 ， 所以图g 为n 2 一正则图。 1 8 第三章2 一划分问题的一些相关性质 3 22 一划分图的连通性 由图的连通性定义可知，若要证明一个图连通，则必须证明图中任意两点之 间存在一条路把它们连接起来。那么对于2 - ：恁l j 分图g 7 来说，根据2 一划分图的构造 原理，要证明任意顶点u 1 和u 2 之间存在一条从点u 1 到点u 2 的路，就是要证明u 1 所 对应的2 一划分6 ( k ，k ) 可以通过一系列变换转化成u 2 所对应的6 ( 巧，) 。 下面我们通过以下几步来实现这一变换。 不妨令图g 的顶点集v = 1 ，2 ，3 ，佗一1 ，n ，佗- i - 1 ，2 n ，任取2 一划 分6 ( ，) ，且= x l ，x 2 ，z n ) ，k = x 卅1 ，x n + 2 ，x 2 n ) 。 第一步，分别对和k 中的点按标号顺序从小到大排序。 例如，v = 1 ，2 ，3 ，4 ，5 ，6 ) ，= 6 ，1 ，3 ) ，= 5 ，4 ，2 ) ，则排序之后= 【1 ，3 ，6 ) ，k = 2 ，4 ，5 ) ； 第二步，在和中选取包含标号为1 ，2 ，3 ，n 的顶点个数最多的子集。 例如，在第一步中的例子中，包含两个1 ，2 ，3 中的点，只包含一个，所以 应选择。 ( 1 ) 若所包含的这样的顶点个数较多，则不妨令中共有k 个这样的顶点，因 而可知中，标号在t , d - 1 ，凡- - i - 2 ，n - t - 3 ，2 n 之中的顶点个数共有t , 一七个， 同样中标号在1 ，2 ，3 ，n 之中的顶点个数也为n k ，则k 中这n 一后个点 和k 中这几一后个点可一一对应，随机组合成n 一忌对，从而将中的这佗一尼个 顶点与k 中的这7 , 一晃个顶点互换； ( 2 ) 若k 所包含的这样的顶点个数较多，则同样重复上述过程，将中的竹一七个 顶点通过纯一忌次交换，换到k 中； 第三步，通过上述过程，2 一划分6 ( ，k ) 变换2 一划分6 ( w ，w ) ，其中叩= 1 ，2 ，3 ，礼) ，v = n - t - 1 ，+ 2 ，n - - t - 3 ，2 n 。 仍以y = 1 ，2 ，3 ，4 ，5 ，6 ) ，= 1 ，3 ，6 ) ，k = 2 ，4 ，5 ) 为例，按照上述过程 将中的点6 与k 中的点2 交换。 1 9 第三章2 一划分问题的一些相关性质 同样点乱2 所对应的2 一划分巧( 巧，巧) 也能通过上述过程变换到j ( 叩，叼) ，则2 一划 分6 ( k ，k ) 可以先转化成6 ( 叩，曙) ，然后再由6 ( w ，嵋) 转化成2 一划分6 ( ，巧) ， 即顶点u 1 和u 2 之间存在一条从点u 1 到点u 2 的路，因而图g 7 是连通的。 3 32 一划分图f l , 勺h a m i l t o n 性 对于任意一个图来说，判断其是否包含h a m i l t o n 路是一个n p h a r d 问题，是没 有多项式算法的。但是对于一些特殊的图来说，是可以通过特定的方法找到一 个h a m i l t o n 路，而2 - 戈l j 分图正是这样一种图。在给出构造方法之前，先作如下说 明，即事实上，无论如何进行划分，每一个2 - 戈1 分的两个子集中必有一个包含 数字1 ，则只需用包含数字1 的那个子集来代表这个2 一划分，就可以穷举图g 的所 有2 - 戈l j 分，进而表示2 一划分图g 中的所有点。 例如划分6 ( ，k ) ，其e e y l = 1 ，2 ，3 ，扎) ，= n + 1 ，n + 2 ，n + 3 ，2 n ， 则6 ( ，k ) 表示为 1 ，2 ，3 ，礼) ；同样若划分6 ( “，) ，其中 “= 1 ，3 ，5 ，2 n 一1 ) ，“= 2 ，4 ，6 ，2 n ， 则6 ( “，) 表示为 1 ，3 ，5 ，2 n 一1 ) 。 有了如上定义，下面我们以2 n 个点的2 一划分图为例，给出h a m i l t o n 路的一般 构造方法。 任取数字l ，2 ，3 ，2 礼一1 ，2 佗，并给出这2 佗个数所对应的所有2 - ：蛇u 分及由 它们构成的2 一划分图g 7 ，按照下列顺序排列这些2 一划分。 首先，对于划分 1 ，2 ，3 ，佗) 来说，固定前佗一1 个数不变，将最后一个数n 逐 步增2 1 ：l 至l j 2 n ，即 ( 1 ，2 ，3 ，n 一1 ，佗) 一( 1 ，2 ，3 ，佗一1 ，亿+ 1 ) _ _ ( 1 ，2 ，3 ，n 一1 ，2 n 一1 ) _ ( 1 ，2 ，3 ，n 一1 ，2 n ) 于是就产生了这样一条路：以划分( 1 ，2 ，3 ，佗一1 ，n ) 代表的点为起点，划 分( 1 ，2 ，3 ，礼一1 ，2 n ) 代表的点为终点，并且在这条路上共有n + l q - 点。而后 对于划分( 1 ，2 ，3 ，几一1 ，2 n ) 来说，固定其它的数不变，将n 一1 变为n 。 ( 1 ，2 ，3 ，佗一1 ，2 n ) _ ( 1 ，2 ，3 ，n ，2 n ) 接下来再按照上面类似的过程，保持划分( 1 ，2 ，3 ，7 , ，2 n ) 前佗一1 个数不变， 2 n 第三章2 一划分问题的一些相关性质 最后一个数2 凡逐步减+ n n + 1 ，则上面产生的那条路又延长到( 1 ，2 ，3 ，礼，n + 1 ) 代表的点，这时在这条路上共有2 扎个点。 ( 1 ，2 ，3 ，礼，2 n ) 一( 1 ，2 ，3 ，佗，2 n 一1 ) _ _ ( 1 ，2 ，3 ，礼，n + 2 ) 一( 1 ，2 ，3 ，礼，佗+ 1 ) 此时与上面的过程不同，要再将划分( 1 ，2 ，3 ，礼，n + 1 ) 变换为( 1 ，2 ，3 ，n + 1 ，n + 2 ) 。 ( 1 ，2 ，3 ，n ，n + 1 ) 一( 1 ，2 ，3 ，n + 1 ，n + 2 ) 不断重复上述整个过程，在走遍所有2 一划分点的同时，延伸这条路。 ( 1 ，2 ，3 ，扎+ 1 ，n + 2 ) 一( 1 ，2 ，3 ，n + 1 ，n + 3 ) 一 _ ( 1 ，2 ，3 。，死+ l ，2 死) _ ( 1 ，2 ，3 。，n + 2 ，2 n ) 不难看出这是一个将划分 1 ，2 ，3 ，礼 中的数，由大到小一层层逐步变化的 过程。这个过程一直进行下去，将穷举所有的2 一划分，直到最后一个划分 l ，n + 2 ，佗+ 3 ，2 礼一1 ，2 n 为止。而这个过程保证了产生的路遍历2 一划分图g 7 的每 个顶点恰好一次，因而这条路是一条h a m i l t o n 路。 下面的例子进一步阐述了2 一划分图的h a m i l t o n 路的构造过程。 例3 1 任取数字1 ，2 ，3 ，4 ，5 ，6 ，用这6 个数产生的所有2 一划分构造2 一划分图，并 找出这个2 一划分图的一条砌m f z 幻，2 路。 按照上述方法，构造如下， ( 1 ，2 ，3 ) 一( 1 ，2 ，4 ) _ ( 1 ，2 ，5 ) _ ( 1 ，2 ，6 ) _ ( 1 ，3 ，6 ) 一( 1 ，3 ，5 ) 一( 1 ，3 ，4 ) _ ( 1 ，4 ，5 ) _ ( 1 ，4 ，6 ) _ ( 1 ，5 ，6 ) 2 1 第四章结论 第四章结论 在本文第一部分中，我们首先介绍了电路划分问题的相关背景和它所适用 的数学模型。紧接着在文章的第二部分，又介绍 k e r n i g h a n - l i n 算法的核心思 想，并在k e r n i g h a n - l i n 算法的基础上提出了一种2 一划分近似算法。这一算法对 k e m i g h a n - l i n 算法初始划分状态的选取做出了改进，通过得到割边集的权重和尽 可能小的初始划分状态，减少了初始划分状态选取的随意性，降 氐t k e r n i g h a n - l i n 算法中运算结果对初始值的敏感性和得到局部最优值的可能性。 在文章的第三部分，我们讨论了2 一划分图的一些基本性