（运筹学与控制论专业论文）一些4正则图最优扩张的演化.pdf

韭夏窑逼太堂亟堂焦途塞 生塞撞垩 中文摘要 摘要：针对4 一正则图的平面嵌入的纵横扩张的特殊性，某些4 一正则图类的最小折 数纵横扩张已经有了线性算法。本文通过基纵横扩张，提供了从一个4 一正则图扩 充为另一个4 一正则图的方式，使得从原图的最小折数基纵横扩张自然导出扩充图 的最小折数基纵横扩张。全文共分六章： 第一章介绍了一些基本概念及相关的定理。 第二章在刘彦佩教授对图的可嵌入性研究的基础上建立了广平衡图的运输问 题模型。 第三章在广平衡图模型的基础上，得到了最小折数纵横扩张的判别准则。 第四章讨论了4 一正则平面图的特殊性质，并得到了它的最优纵横扩张的判别 准则。 第五章给出了求一类4 一正则平面图最优纵横扩张的算法，并利用第四章得到 的判别准则从理论上进行了论证。 第六章总结了全文的结论。 关键词：4 一正则图；纵横扩张；广平衡图；基纵横扩张；规范圈 分类号：0 1 5 7 5 韭毫窑煎太堂亟堂毽淦塞曼至叁! a b s t r a c t a b s t r a c t ：a c c o r d i n gt ot h ep r o p e n i e so f r e c t i l i n e a re x t e n s i o n so f 4 - r e g u l a rg r a p h s ， al i n e a rt i m ea l g o r i t h mh a sb e e nd e s i g n e dt o g e tr e c t i l i n e a re x t e n s i o n s o fs o m e p a r t i c u l a rk i n d so f4 - r e g u l a rg r a p h sw i t ht h em i n i m u mt o t a ln u m b e ro fb e n d s i nt h i s p a p e r ，ag e n e r a l i z e da l g o r i t h mi sp r o v i d e dt oe x t e n da4 - r e g u l a rg r a p ht oa n o t h e r 4 - r e g u l a rg r a p ht h r o u g hb a s er e c t i l i n e a re x t e n s i o n , f r o mw h i c ht h eb a s er e c t i l i n e a r e x t e n s i o nw i t ht h em i n i m u mt o t a ln u m b e ro f b e n d so ft h eg r a p hi sn a t u r a l l yo b t a i n e do n t h eb a s i so f t h e 耐g i n a lo n e t h e r ea r es i xc h a p t e r si nt h i sa r t i c l e ： t h ef i r s tc h a p t e ri n t r o d u c e ss o m eb a s i cc o n c e p t sa n dr e l a t e dt h e o r i e s i nt h es e c o n dc h a p t e rt h et r a n s p o r t a t i o nm o d e lo fg e n e r a l i z e de q u i l i b r i u mg r a p hi s c o n s t r u c t e dv i at h ey el i u sr e s e a r c hf o re m b e d d a b i l i t yt h e o r yi ng r a p h s i nt h et h i r dc h a p t e rt h ec r i t e r i ao f t h em i n i m u mb e n dr e c t i l i n e a re x t e n s i o ni sd e r i v e d f r o mt h et r a n s p o r t a t i o nm o d e lo f g e n e r a l i z e de q u i l i b r i u mg r a p h t h ef o u r t hc h a p t e re x a m i n e st h es p e c i a lp r o p e r t i e so fr e c t i l i n e a re x t e n s i o n so f 4 - r e g u l a rg r a p h s a n dt h ec r i t e r i ao f o p t i m a lr e c t i l i n e a re x t e n s i o n so f 4 - r e g u l a rg r a p h si s o b t a i n e d i nt h ef i f t hc h a p t e raa l g o r i t h mf o ro p t i m a lr e c t i l i n e a re x t e n s i o n so fak i n do f 4 - r e g u l a rg r a p hi sg i v e n a n dw ea l s og i v et h ep r o o fb a s e do i lt h ec r i t e r i af r o mt h e f o u r t hc h a p t e r t h es i x t hc h a p t e rg i v e sac o n c l u s i o no f t h ew h o l ea r t i c l e k e y w o r d s ：4 - r e g u l a rg r a p h s ；r e c t i l i n e a re x t e n s i o n ；g e n e r a l i z e de q u i l i b r i u mg r a p h ； b a s er e c t i l i n e a re x t e n s i o n ：n o r m a lc y c l e c i a s s n o ：0 1 5 7 5 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：考语壶l 签字日期：2 “年i f 月叫日 导师签名： 荔多产一 签字日期：么坶：存f 1 月叫日 致谢 本论文的工作是在我的导师刘彦佩教授的悉心指导下完成的，刘彦佩教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来 刘彦佩老师对我的关心和指导。 刘彦佩教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，在此向刘彦佩老师表示衷心的谢意。 刘彦佩教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷 心的感谢。 在实验室工作及撰写论文期间，万良霞、俞勤等对我论文中的算法研究工作 给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。 韭 塞銮盈太 堂亟堂焦淦塞度 序 在超大规模集成电路( v l s i ) 的布局设计中出现了种种模型。在这些模型中， 通常将元件设想为平面上的点，而元件之间连接的导线设想为平面上的线。这样， 将一个电路变成了一个图。因为元件总是放在一块绝缘的平板( 即这个平面上) ， 导线为印制在其上的金属( 导体) 曲线。为避免短路，这些代表导线的曲线之间 不允许交叉。这种要求就是数学上所说的求相应图的平面表示。然而，实际的情 形并非任何一个图都有平面表示。反映到电路上就是，并非任何一个电路均可安 置在一块板面上，使得印制导线之间不会出现交叉。随着社会需求之扩大，成批 生产带来了设计与制造的规范化、自动化之要求。近十年来，人们愈来愈趋于利 用单层双面的模型，即将元件配置在一个板面上后，将它们之间的连线限制沿水 平和竖直二个方向走以便将水平走向的线段划在同一面上和将竖直走向的全划在 另一面上。这样的模型有利于规范化。当然，不能保证总可以使得每条连二元件 的线均为水平或竖直线段，这就不能不把一些连线表示成由水平或竖直线段组成 的折线。本文所说的最优即指使所有连线的总折数达到最小。 丝塞窑理态堂亟堂篷淦塞i l矗 l 引言 在超大规模集成电路( v l s i ) 的布局的研究中引出了纵横嵌入这个问题。在实际 生活中往往有这样的需求，即是要找出电路图在平面上的最小折数纵横嵌入，这 是很困难的，而其中最基本也是最重要的一步就是研究一个嵌入的最小折数纵横 扩张。在【2 】中，提供了纵横嵌入的基本理论。继之，在【l 】，【3 】中进一步讨论算法 的理论与实现。并且，将它们纳入了更具普遍性的运输网络术。在此基础上，文 献【7 和【9 】中都给出了一类4 正则图的最小折数扩张的线性算法。在上述基本理论 的基础上，本文通过基纵横扩张，提供了从4 正则图扩充为另一个4 - 正则图的方 式，使得从原图的最小折数基纵横扩张自然地导出扩充图的最小折数基纵横扩张。 1 1已有结果 在3 0 年代，k u r a t o w s k i ，w h i t n e y 和m a c l a n e 分别解决了图的平面性问题。 8 0 年代，学者们开始研究图的纵横嵌入。l v a l i a n t 证明了一个图有纵横嵌入的 充要条件是它是4 一平面的。随后，r t a m a s s i a 设计了一个算法，在o ( n 2 l o g 打) 时 间内构造一个平面嵌入的最小折数纵横扩张。r t a m a s s i a 和i t o l l i s 提供了一个 线性算法，构造平面嵌入的纵横扩张。9 0 年代初，对于图的纵横嵌入的研究更趋 深入。刘彦佩教授建立了有关的基本理论。此后，y p l i u ，m o r g a n a 和s i m e o n e ： k a n t ：r t a m a s s i a 。i g t o l l i s 和j s v i t t e r ：以及h ex i n 都给出了有关纵横 扩张的线性算法。但这些算法都不能得到最小折数。1 9 9 4 年，a g a r g 和r t a m a s s i a 证明了若平面嵌入没给定，4 一平面图的最小折数纵横嵌入问题是n 卜困难的，3 一 平面图的最小折数纵横嵌入问题可在多项式时间内解决。1 9 9 8 年，g i u s e p p ed i b a t t i s t a ，g i u s e p p el i o t t a 和f r a n c e s c ov a r g i u 设计了一个多项式时间算法， 在平面嵌入没有给定的情况下，求两类图( s e r i e s p a r a l l e lg r a p h 和3 一平面图) 的最小折数纵横扩张。在【8 】和【9 】中，万良霞和傅超等通过不同途径分别给出了一 类4 正则图类的最小折数纵横扩张的线性算法。 1 2图论的基本概念 一个图g 就是指一个集合v 及其上的一个二元关系r 。y 是顶点集，其中的 元被称为顶点。任意的u , v v ，若“，v 震，则甜与v 有一边相连。顶点u 和v 称为 是这条边的端点。这条边称为端点和v 的关联边。所有边的集合记为e ，记 g = ( 矿，e ) 。在一个图中，与顶点“关联的边的个数，称为顶点雄的度，记为d ( “) 。 若对任意的“v ，有d ( u ) = k ，则称此图是k 一正则的。用f 表示图中边的数目， 显然有 d ( u ) = 2 e o e r 若一条边的两个端点重合，则称之为环。若两个端点之间的边多于一条，则 称有重边。既无重边也无环的图称为简单的。 在g 中，若w = u o e l l l l e 2 略吼是个顶点和边的交替序列，使 p ，= ( 砧h ，“，) ，v i = i ，2 ，k 称矽为从到的途径。和分别称为形的起点和终点。矿的长度为k ，在一 个途径中，若任意两条边皆不相同，则称之为迹。若在迹中任意两个顶点皆不相 同，则称之为路。起点和终点相同的途径，迹和路分别称之为迂，回和圈。若一 个图中任意两个顶点之闻存在一条路，则称此图是连通的。图g 的每一个连通的 部分，称为它的个连通分支。若去掉一条边后使得连通分支增加，则称此边为g 的割边。若去掉某些边后使得连通分支增加，则称这些边为g 的一个边割。 对于两个图g l = ( k ，巨) 和g = ( v ，e ) ，若k v ，e 冬e ，则称g l 是g 的一个予 图。若巧= v ，则称g l 为g 的支撑子图。对任意的巨e ，称g t = ( 巧，互) 为g 的 边导出子图，其中k 是所有与臣中的边关联的顶点的集合。在一个图g 中，若去 掉一个顶点后的边导出之图仅有一个公共点，则称此顶点为g 的割点。连通无圈 图称为树。一个树又是一个支撑子图，称之为支撑树。对于图的每一个支撑树， 每一条不在支撑树上的边与此支撑树恰形成一个圈，称为这条边所在的基本圈。 一个有向图g = ( 矿，e ) 是指集合v 上的一个二元有序关系r ，若u r v ，则称有 一个从“到v 的弧，记为 。h 和v 分别称为这个弧的起点和终点。 e = f u r v ，v u ，v n 是弧集。 对于图g ，给它的所有点处的关联边规定一个循环序，若可以把它划在平面 上，使得代表边的曲线除端点外无其它公共点，则称为图g 的一个平面嵌入( 或 平面图) ，记为( g ) 。g 称为可平面图。所有顶点的度不大于k 的可平面图，称为 k 一平面图。一个平面图，把平面分成若干个连通的区域，这些区域称为面。其中， 唯一一个无界面称为无限面，记为五。在每一个面的闭包上的边集称为这个面的 边界。面厂的边界上边的数目称为厂的度，记为d ( n 。若在g 的一个平面嵌入中， 所有边都用由水平和竖直线段组成的折线来表示，则称此嵌入为纵横嵌入。无限 面确定的的纵横嵌入称为纵横扩张，记为y ( g ) 。在一条折线上，纵线段与横线段 的交汇处，称为个折。每条边上的折数都不超过f 的纵横嵌入，称为卜嵌入。所 有边都无折的纵横扩张和纵横嵌入分别称为网格扩张和网格嵌入。折数达到最少 2 j e基銮适 盔堂 亟 堂位 j 佥塞曼i直 的纵横扩张称为最小折数的。 1 3线性规划 线形规划的一般形式是： m i n c 7 x( 1 1 ) 嘉 其中，c 是厅维列向量，t 表示向量的转置，a = ( 4 4 4 ) 为一个秩为m 的 r l l x n 矩阵，b 和4 ，i = 1 ，2 ，n 是m 维列向量，它们都是常量。设君为4 的一个非 奇异子矩阵，则称b 是线性规划问题的一个基。不失一般性，令b = ( 4 ，4 ，a m ) ， 称爿，( _ ，= l ，2 ，m ) 为基向量，与基向量彳，相应的变量为基变量，否则为非基变量。 相应于基的一个解x = ( b b ，0 ) 称为线性规划的一个基解。同时满足两个约束条件 的解，称为线性规划问题的可行解。满足第二个约束条件的基解称为基可行解。 对应于基可行解的基称为可行基。基解中非零分量的个数小于m 时，这个基解是 退化的，否则，称为非退化的。类似地，基可行解中非零分量的个数小于m 时， 称为退化的基可行解，否则，称为非退化的基可行解。 1 4运输问题 给定图g = ( v ，e ) ，在它的顶点集矿中，有s 个发点( 或源) ，构成源集s 。t 个收 点( 或汇) 。构成汇集r 。其余的点称为中转站。对于每一个源v ，有一个给定的正 数烈v ) ，称为发量。对于每一个汇v ，有一个给定的正数6 ( v ) ，称为收量。且 口( v ) = 6 ( v ) 。 y e sv e t 对每一条边e e ，有一个权c ( 力。设通过边e 的流量为x ( e ) ，则运输问题的模型 为： r a i n c ( 咖( 口) t e e x ( e ) - x ( e ) = 0 ，v 矿、( s u r ) ； i 口( v ) ，v s ； 畦口盹巧 i 一6 ( v ) ，v r ； 3 韭夏銮照太堂 亟圭堂焦论塞j i畜 其中，e 和e 分别表示从v 发出的边和进入v 的边的集合。 模型( 1 ) 的一个可行解对应的图，称为流向图，其中有流向的边称为弧。基可 行解对应的图称为基流向图。若在两个顶点“，v 间，既存在从到v 的非零流又 存在从v 到“的非零流，则称”，v 问存在对流。显然，在基流向图中没有对流， 且有流向的边不能构成圈。 令 f 见( c ) = ( c ) + 盹( c ) 一m + ( c ) ； 【p a c ) = m o ( c ) + m + ( c ) 一耽够) 其中，致( c ) ，髓( c ) 和t o o ( c ) 分别表示圈c 中与顺时针方向一致的弧上的总 权，与逆时针方向一致的弧上的总权和边上的总权。若在圈c 中，n ( c ) o ， n ( c ) o ，则称c 为正规圈。对于运输问题已知下列结果： 定理1 1 1 6 j 运输问题的一个可行解是非退化的基可行解的充分必要条件是在 其流向图中，有流向的边构成一个支撑树。 定理1 2 陋l 运输问题的一个可行解是最优解的充分必要条件是在其流向图中 无对流且每一个圈都是正规圈。 定理1 。3 嘲运输问题的一个基可行解是最优解的充分必要条件是在其基流向 图中每一个基本圈都是正规圈。 4 韭壅銮遭太堂亟堂熊i 金塞亡垩煎圈搓型【3 】 2 广平衡图模型【3 】 设g = ( v ，e ) 是一个平面图，a ( g ) 是它的一个平面嵌入，f 是它的面集，f o 为 无限面。对任意的v v ，令d e f ( v ) = 4 - d ( v ) ，称d e f ( v ) 为顶点v 的亏数。对任意的 f f 。令 r e s ( 力= 【彻d ( f ) + - 4 4 ，, f ，：石f o ，； 称r e s ( f ) 为面厂的赢数。其中，d ( f ) 表示，的边界上边的个数。 令 一= v i v 矿，d e f ( v ) o ； e ( 专力= 化) i v vk ( ) ，v f e ， ； e + = ( z ，f , ) l v f , ，乃e f ，z a 蜕 其中，表示k 中在f 的边界上的点的集合。z 砸圻表示z 与z 的边界有 公共边。 称h ( t g ) = ( 矿( 日) ，e ( ) ) 为j a ( g ) 的广平衡图，其中矿( 日) = 以u f ， e ( 日) = e ( - - h f ) u f 。 令 f c = 厂lr e s ( f ) o , f e f ； e = f ir e s ( f ) o ， 那么在( g ) 的纵横扩张，( g ) 中，：和正边界的公共边上有乃。个折的方向是从z 内的石2 角到，内的3 芹2 角。由于v v l ，d c f ( v , ) = l 或2 ，且毛o ，0 ， 因此嘞= o ，1 或2 。若用 圻稀- r c g ) 中面乃在v f 处的角，那么定义 氐j 、f i = ，r 2 ，= o ； 石，毛= l ； 3 万2 ，= 2 6 韭塞窑道友堂亟堂僮迨塞量尘煎熬熟毯芷韭判宝宝堡 3 最小折数纵横扩张判定定理 定义3 1 令 允( c ) = ( c ) + 吃( c ) 一心( c ) ，五( c ) = ( c ) + n ( c ) 一堤( c ) ， 其中一( c ) ，毽( c ) 和( c ) 分别表示圈c 中与顺时针方向一致的弧数，逆时针 方向一致的弧数和空自边数。若在圈c 中，无( c ) 0 ，丑( c ) 0 ，则称c 为规范 圈。否则，是非规范圈。不满足规范圈的方向称为可调方向。在非规范圈上，若 含有圯中的点，则在可调方向上必含以此点为起点的流量不为零的弧，称这样的 非规范圈为可规范圈。那些不含圪中的点的非规范圈属于可规范圈。 在日( ，g ) 中，如果某个圈c 是可规范的，不妨设，顺时针方向的弧数大于其 它弧与边的数目和。令仃是顺时针方向弧中流量的最小值，令顺时针方向弧的流 量都减去盯，逆时针方向的弧和边的对应流量都加上盯，那么，c 可调整为规范 圈。 定理3 1 i s l 一个平面嵌入的纵横扩张是最小折数的当且仅当在其广平衡图模 型的流向图中，无对流且无可规范圈。 证对于任意给定的平面嵌4 g ) ，设日( ，昭) 是它的广平衡图。令c 表示g 边 上的费用。由于对任意( v ，f ) e ( - - ) f ) ，c ( ( v ，) ) = 0 。对任意( g ，d e ， c ( ( g ，厂) ) = l 。在h ( i a g ) 的每一个圈中都含有偶数条e ( 一。f ) 中的边且不影响规 范性。因此，每一个规范圈都是正规圈。可规范圈保证了调整后解的可行性。再 由定理1 2 即得此结论。 定理3 2 1 8 1 ( g ) 的h ( i z g ) 模型的一个基可行解所对应的纵横扩张是最小折 数的当且仅当在其广平衡图模型的基流向图中，所有基本圈都不是可规范圈。 证由定理1 3 及3 1 可得。 7 韭鏖窑道盘芏亟堂僮淦塞4 ：垂则国曲挂珏筐 44 正则图的特殊性 对于4 一正则图，有v v v ，d e f ( v ) = 4 - 以v ) = 0 ，k = v i v v ，d e f ( v ) o 为空 集，4 正则图的广平衡图的运输问题模型可简化如下： 6 ( y ( g ) ) = n f i n ( y o + 乃，) “) e f ( 珂) f 嘶- - y j , ) = r e s ( f _ ，) ，乃e f ； ( 石) e 6 ( h ) 【均，只，z + ，v ( z ，乃) e ( 抒) 并且，4 正则图g 的广平衡图h ( a g ) 恰好是它的对偶图。r ( g ) 中的有折 边和h ( i a g ) 中的有流向的边一一对应。 定义4 i4 正则图g 的广平衡图模型日 g ) 的基可行解对应的纵横扩张 ，( g ) 称为图g 的基纵横扩张。相应地，非退化的基可行解对应的纵横扩张 “g ) 称为图g 的非退化的基纵横扩张。 定理4 i4 正则图g 的纵横扩张y ( g ) 是图g 的非退化的基纵横扩张的充 分必要条件是在广平衡图h ( i a g ) 中，有流向的边构成一个支撑树。 证由定义4 ，i 及定理1 1 可得。 3 韭塞銮遵太堂亟堂僮论塞4 ：正国毂量尘蕴煎塑毯毖值化 54 正则图的最小折数纵横扩张优化 定义5 1 g = ( 矿，f ) 是一个4 正则平面图，若在g 上存在一个圈c ，使得在c 上的每一个节点v 处，在c 的内部和外部区域均恰有一条边与v 关联，把这样的圈 c 的集合记为n 。 对4 正则平面图g = ( y ，e ) ，设y ( g ) 是g 的纵横扩张，将，( g ) 中的一块区域 用一个矩形圈住，假设该区域共有疗条边( 地，v 1 ) ，( u 2 ，叱) ，( ，) 连到外部区域， 则该矩形恰交这疗条边于疗个点珥，甜：，玩，该矩形连同这聆个点构成一个圈 c o ( u , 一u 2 蠢) ，显然，c oe n 。这样，便由图g 出发，增 j 1 n 个结点，u 2 ，峨和 n 条边产生一个新图g ，以及它的纵横扩张r ( g ) ，如图5 1 所示。并且，由此产 生的新图g 的纵横扩张r ( g 。) 比图g 的纵横扩张r ( g ) 增 j h 4 个折。相应于图g 的广 平衡图h ( i a g ) ，新图g 的广平衡图h ( a g ) 增加2 玎条边( 弧) ( z ，爿) ，( 矗，爿) ，( z ，石。) ，石) ，( z ，五) ，( ，五) ，其中， ( 石，z ) ，( z ，左) ，( z ，五) 中有4 个流量为l 的弧，如图5 2 所示。并且也有圈 c ( z a 彳z ) 兀。 越1 rh “。工 一 0 图5 1 图5 2 9 韭瘟窑堡太堂亟主堂焦盈塞：正则国鳆量尘蕴筮塑趱芷韭馋丝 定理5 1 假设，( g ) 是g 的最小折数基纵横扩张，并且在由上述方法构造的 r ( g ) 中，v v c o ，与v 关联的c o 内部的边“，讧) ，( u 2 ，也) ，( ，越) 均为无折边， 则r ( g ) 是新图g 的最小折数纵横扩张。 证在g 的广平衡图h ( 1 a g ) 中，令t = r + 芝：( z ，力，其中r 是g 的广平衡 图h ( u g ) 的支撑树，则r 是h ( 1 a g ) 的一棵支撑橱：若不然。假设c 是r 中的一 个圈。若圈c 不包含点_ ，：，i = i ，2 ，挥，则c 中的边全部在z 中。这与r 是树矛盾。 若存在z 。c ， = t , 2 ，胡，此时必有h ( 1 z g ) 中圈z 爿。z 石。内的一个点石在h ( 1 z g ) 中与z 关联，否则点在丁中是1 度点，不可能在圈c 上。将c 上的边( 或弧) ( z ，z ) 用边( 或弧) ( ，f ) 代替，所得到的c 仍然是一个圈，且c 。t ，这与r 是树矛 盾。下证h ( a g ) 中的所有基本圈都是规范圈。 假设e 是h ( 1 a g ) 中的一个基本圈，其中口是h ( g g ) 的一条非树边。首先 证明当口t 即口是h ( g ) 中的非树边时，e 是规范圈。此时，只要考察可能出 现的如图5 3 所示情况。即在日( g ) 中的包含非树边口的基本圈乞中的一条有流量 的弧，不妨设为( 磊，彳) ，在c ：中剖分为2 条与( 五，石) 同流向的弧 磊，彳) 和饼，彳) 。 这样，在c ：中与( 石，石) 同向的弧的数目就比c ：多l 。但由于圈c ( 1 爿z 石) l - i ， t 中必有另一条弧( 或边) 也被剖分，使得在q 中与瓴，石) 反向的弧的数目也比 a 多1 。这样，由于奠是规范圈，故q 也是规范圈。其次，证明当 口e ( z ，爿) ，( ，爿) ， ，( z ，工) ，即口是h ( 1 a g ) 中比h o a 6 ) 增加的非树边时，c o 是 基本圈。不失一般性，考虑非树边 彳，z ) 。如果( 磊，磊) 是弧，那么圈g ( 彳五石z ) 是基本圈e f 、。显然，它是基本圈。如果( z ，五) 是边，令h ( 1 z g ) 中包含( 石，z ) 的 基本圈是c 2 。那么，c 3 = c 1 + c 2 是( ，z ) 在h ( a g ) 中所在的基本圈。c 3 的弧数恰 好在顺时针和逆时针方向比c 都多l ，由于c 是规范圈，因此，g 是规范圈。 综上，日( 施) 中的所有基本圈都是规范圈。根据定理3 2 ，r ( g ) 是新图g 的 最小折数纵横扩张。证毕。 图5 3 a e 鏖銮堙太堂亟堂焦迨塞：正删国鳆量尘垣熬熟毯芷毯值丝 定理5 2 按上述算法产生的新4 正则图g 的最小折数纵横扩张y ( g ) 比4 正 则图g 的最小折数纵横扩张y ( g ) 增加4 个折。 对一个4 正则平面嵌入图g n ，假设已经求得它的最小折数基纵横扩张。在 a ( g ) 中任选一个定点，在这个定点的每一个关联边上都增加一个顶点，再按顺时 针方向依次连接它们，即可得到一个4 正则平面嵌入g l ，它有矿( ，酊) + 4 个顶点。 推论5 14 正则图g l 的最小折数纵横扩张r ( g ) 比4 正则图g 0 的最小折数纵 横扩张r ( g ) 增加4 个折。 证 在定理5 2 中，当矩形圈住的区域中只有一个顶点耐，即得此推论。 在【8 】和【9 】中，通过不同途径分别给出了和推论5 1 类似的4 正则图类的最小 折数纵横扩张的线性算法。因此可以说，通过基纵横扩张，定理5 1 和定理5 2 取 得了4 正则图最小折数纵横扩张的一个更广泛的结果。 i e塞銮煎盔堂亟堂僮 纶 塞结j 金 6 结论 章： 本文在【l 】的基础上，主要研究了4 一正则图的纵横扩张优化问题。全文共分六 第一章介绍了有关的基本知识。 第二章建立了广平衡图的运输问题模型如下： 6 ( y ( g ) ) = 衄n ( 托+ ) ， ( z ， ) e ， = d e f ( h ) ，t e ； ( 圻k e 一 即，j 列 f r c s ( l ) ，乃e p ； 勃+ ( y 口一 ，) = o ，矗； n 西k 叫4 砷肛 “西扣矿 lr c s ( z ) ，只； 而，肋，乩z + ，v ( q ，乃) ，( z ，乃) e ( 日) ， 其中z + = o ，i ，2 ，l 第三章进而得到了最小折数纵横扩张的判定定理： 定理3 i t 川一个平面嵌入的纵横扩张是最小折数的当且仅当在其广平衡图模 型的流向图中，无对流且无可规范圈。 定理3 2 1 川 ( g ) 的日( ，f g ) 模型的一个基可行解所对应的纵横扩张是最小折 数的当且仅当在其广平衡图模型的基流向图中，所有基本圈都不是可规范圈。 第四章讨论了4 正则图的特殊性，进而得到4 正则图的相对简便的最优扩张 判定定理： 定理4 14 正则图g 的纵横扩张r ( o ) 是图g 的非退化的基纵横扩张的充分 必要条件是在广平衡图( ，昭) 中，有流向的边构成一个支撑树。 第五章给出了一类4 正则图的最小折数纵横扩张的线性算法。 定理5 1 假设y ( g ) 是g 的最小折数基纵横扩张，并且在由上述方法构造的 r ( o ) 中，v v c 0 ，与v 关联的c 0 内部的边( u l ，“) ，( “：，如) ， ，瓦) 均为无折边， 则r ( g ) 是新图g 的最小折数纵横扩张。 定理5 。2 按上述算法产生的新4 正则图g 的最小折数纵横扩张r ( g ) 比4 正 则图g 的最小折数纵横扩张y ( g ) 增加4 个折。 推论5 14 - 正则图g l 的最小折数纵横扩张r ( g 。) 比4 一正则图g 0 的最小折数纵 横扩张y ( g ) 增加4 个折。 第六章是全文的总结。 1 2 韭复变通盔 堂 亟 堂焦趁塞绪监 除非特别声明，本文考虑的是无环，无1 度点的连通平面图。 对于一个可平面图，当它的平面嵌入不确定时，求它的所有最小折数纵横嵌 入中折数最少的问题，g a r g 和t a m a s s i a 证明了对4 平面图，此问题是n p 一困难问 题。对3 - 平面图，此闯题是多项式的。b a t t i s t a , l i o t t a 和v a r g i u 研究了两类图 ( s e r i e s - p a r a l l e lg r a p h 和3 ，平面图) ，给出了多项式时间算法。对于其它图类还有 待于进一步研究。本文给出了一类4 正则平面图的最小折数纵横扩张。这类图的 阶数覆盖了所有大于6 的整数。但这仍然只是所有4 正则平面图的一部分。要找 出一个线性时间算法以给出所有4 正则平面图的最小折数纵横扩张仍然是不容易 的。较好的思路是不断给出一些4 正则图类的最小折数纵横扩张。 韭塞窑壅盘堂亟堂焦监塞叁耋塞哒 参考文献 f 1 】刘彦佩，图的可嵌入性理论【m 1 ，科学出版社，北京1 9 9 4 【2 】刘彦佩，纵横布局论【m 】，中国铁道出版社，北京，1 9 9 6 【3 】刘彦佩，纵横嵌入术【m 】，科学出版社，北京，1 9 9 4 【4 】刘彦佩，运输网络术【m 】，上海交通大学出版社，上海，1 9 9 8 【5 】j a b o n d ya n du s r m a r r y ，图论及其应用【m 】，吴望名等译，科学出版社，北京，1 9 8 4 【6 】林诒勋，线性规划与网络流【m 】，河南大学出版社，开封，1 9 9 6 【7 】万良霞，刘彦佩。纵横扩张的优化【j 】，高校应用数学学报a 辑，2 0 0 3 ，1 8 ( 3 ) ：3 5 0 - 3 5 6 8 1 傅超，刘彦佩，一类4 一正则图的最小折数纵横扩张【j 】，曲阜师范大学学报( 自然科学 版) ，2 0 0 2 ，2 8 ( 2 ) ：1 6 2 0 【9 】9 兰培挺，刘彦佩，4 正则图的纵横扩张优化【j 1 ，周口师范学院学报，2 0 0 6 ，2 3 ( 5 ) ：5 - $ j o 】k u r a t o w s k iks u rl ep r o b l e md e sc o u b e sg a u c h e s 朗t n p o l o g i e ，f u n d m a t h ，1 5 ( 1 9 3 0 ) , 2 7 1 - 2 8 3 【1 1 w h i t n e y h ，n o n s e p a r a b l e a n dp l a n a r g r a p h s ，t r a n s a m s ，3 4 ( 1 9 3 2 ) ，3 3 9 1 6 2 【1 2 】w h i t n e yh ，p l a n a rg r a p h s ，f u n d m a t h ，( 2 1 ) 1 9 3 3 ，7 3 - 8 4 【1 3 w h i t n e yh ，o nr e g u l a rc l o s e dc u l n e si nt h ep l a n e ，c o m p o s i t i o nm a t h ，4 ( 1 9 3 7 ) ，2 7 6 2 8 4 【1 4 m a e l a n e s ，a c o m b i n a t o r i a lc o n d i t i o n f o r p l a n a r g r a p h s ，f u n d m a t h ，2 8 ( 1 9 3 7 ) ，2 2 3 2 1 1 5 y p l i u ，e m b e d d a b i l i t yi ng r a p h s , k l u w e r , d o r d r e h t b o s t o n ，l o n d o n ；s c i p r e s s ， b e i j i n g n e w y o r k , 1 9 9 5 1 6 】l v a l i a n tu n i v e r s i t yc o n s i d e r a t i o n si nv l s ic i r c u i t s ，i e e et r a n s c o m p u t e r s , c 一3 0 ( 1 9 8 1 ) , 1 3 5 - 1 4 0 【1 7 】r o b e r t o t a m a s s i a , o ne m b e d d i n g a g r a p h i n t h e 鲥d w i t h t h e m i n i m u mn u m b e r o f b e n d s , s i a mj c o m p u t ，1 6 ( 1 9 8 7 ) ，4 2 1 4 “ 1 8 】r t a m a s s i a ，i t o l l i s ，p l a n a r 鲥de m b e d d i n g si nl i n e a rt i m e 1 e e et r a m o l lc i r c u i t sa n d s y s t e m s ，c a s - 3 6 ( 1 9 8 9 ) ，1 2 3 0 1 2 3 4 【1 9 y pl i u ，a m o r g a n a , b s i m e o n e , al i n e a ra l g o r i t h mf o r2 - b e n de m b e d d i n g so fp l a n a r g r a p h s i n t h e t w o m i m e n t i o n a lg r i d ，d i s c r e t e a p p l m a t h ，8 1 ( 1 9 9 8 ) ，n o 1 - 3 ，6 9 - 9 1 2 0 】gk a n t , d r a w i n gp l a n a rg r a p h su s i n gt h ec a n o n i c a l - o r d e r i n gi np r o c i e e es y r u p o n f o u n d a t i o n so f c o m p u t e rs c i e n c e ，p i t t s b u r g h ，i e e e ，p i s c a t a w a y , n j 。1 9 9 2 ，1 0 1 - 11 0 【2 1 r t a m a s s i a , 1 gt o l l i sa n dj s v i t t e r , l o w e rb o u n d sf o rp l a n a ro r t h o g o n a l 鲥dd r a w i