（运筹学与控制论专业论文）两类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 ：t h i sp a p e rm a i n l ys t u d i e st 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 n s o f4 一r e g u l a rg r a p h s ，i ts h o w st w ok i n d so f4 - r e g u l a rg r a p h s ，a n df o ra n yo r d e ro ft h e s e g r a p h st h e i rm 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 n si s 百v e n t h e r ea r ef i v ec h a p t e r si nt h i st h e s i s ： 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 t h es e c o n dc h a p t e ri n t r o d u c e st h et h e o r yo fe m b e da b i l i t yi ng r a p h s t h et h i r dc h a p t e rg i v e sa na l g o r i t h mf o rg e t t i n gt h em i n i m u mb e n dr e c t i l i n e a r e x t e n s i o n so fak i n do f4 一r e g u l a rg r a p h s ，m a i n l yd i s c u s s e sf o u rt y p e so f4 一r e g u l a rg r a p h s ， g i v e sam i n i m u mb e n dn u m b e rr e c t i l i n e a re x t e n s i o nf o rs u c hag r a p hw i t ha n yo r d e r , a n dp r o v i d e st h er e l a t i o nb e t w e e ni t so r d e ra n dt h em i n i m u mb e n dn u m b e r t h ef o u r t hc h a p t e rg i v e sam 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 no fa n o t h e rk i n do f 4 - r e g u l a rg r a p h s t h ef i f t hc h a p t e rg i v e sac o n c l u s i o no ft 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 ；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 ；m i n i m u mb e n d n u m b e r ；r e c t i l i n e a re x t e n s i o n ： c l a s s n o ：0 1 5 7 5 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意 学位论文作者签名：签字日期：厂年f 月即日 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅同意学校向国 家有关部门或机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 浓f 速 铆签咧房讯 签字日期：铆硝犀t 瑚卅日签字日期：碲1 瑚矽1 7 t 致谢 本论文的工作是在我的导师刘彦佩教授的悉心指导下完成的，刘彦佩教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响在此衷心感谢几年来 刘彦佩老师对我的关心和指导 刘彦佩教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，在此向刘彦佩老师表示衷心的谢意 俞勤学长对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷心 的感谢 在实验室工作及撰写论文期间，郝荣霞、姜伟、王立东、杨艳等对我的论文 的研究工作给予了热情帮助，在此向她们表达我的感激之情 另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业 序 随着计算机的发展，超大规模集成电路( v l s i ) 的集成度越来越高，v l s i 布 局优化也越来越重要国内外将这一问题视为未来计算机设计成败的关键 上世纪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 2l o g n ) 时间内构造一个平面嵌入的最小折数纵横扩张 9 0 年代初，对于图的纵横嵌入的研究更趋深入刘彦佩在文献 2 】中建立了有 关基本理论此后，y p “u ，m o r g a n a 和r t a m a s s i a 等数学家都给出了有关纵横扩 张的线性算法1 9 9 4 年，a g a r g 和r t a m a s s i a 证明了4 平面图的最小折数纵横嵌 入问题是n p 困难的，3 平面图的最小折数纵横嵌入问题可以在多项式时间内解 决 19 9 8 年，b a t t i s t a ，l i o r 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 正则图的最小折数纵横扩张问题， 分别给出了简便算法 1 引言 在超大规模集成电路( v l s i ) 的布局设计中出现了种种模型在这些模型中， 通常将元件设想为平面上的点，而元件之间连接的导线设想为平面上的线这样， 将一个电路变成了一个图因为元件总是放在一块绝缘的平板( 即这个平面上) ， 导线为印制在其上的金属( 导体) 曲线，为避免短路，这些代表导线的曲线之间 不允许交叉这种要求就是数学上所说的求相应图的平面表示然而，实际的情 形并非任何一个图都有平面表示反映到电路上就是，并非任何一个电路均可安 置在一块板面上，使得印制导线之间不会出现交叉随着社会需求之扩大，成批 生产带来了设计与制造的规范化、自动化之要求近十年来，人们愈来愈趋于利 用单层双面的模型，即将元件配置在一个板面上后，将它们之间的连线限制沿水 平和竖直二个方向走以便将水平走向的线段划在同一面上和将竖直走向的全划在 另一面上，这样的模型有利于规范化当然，不能保证总可以使得每条连二元件 的线均为水平或竖直线段，这就不能不把一些连线表示成由水平或竖直线段组成 的折线本文所要研究的就是使所有连线的总折数达到最小 在 1 、 2 和 3 中给出了构造一个平面嵌入的最小折数纵横扩张的基本理 论 4 中给出了运输问题的模型及其利用该模型求最小折数扩张的理论； 8 中 利用运输问题求解最小折数扩张，但是只是给出了一般结果 9 给出了确定一类 4 一正则图的最小折数扩张的线性算法但是此类图只是给出了这类图的阶为所有 不小于6 ( 不包含7 ) 的正整数的情形本文是在 8 给出结果的基础上，把 9 中的 图进行了扩充，讨论了这类图中阶为所有正整数的情况 本文所指平面图皆连通且无l 度节点 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 2l o g n ) 时问内 构造一个平面嵌入的最小折数纵横扩张r t a m a s s i a 和i t o l1 i s 提供了一个线性 ：i 基塞銮逗太堂亟堂位i 金塞 互i 吉 算法，构造平面嵌入的纵横扩张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 都给出了有关纵横扩张的线性算法但这 些算法都不能得到最小折数1 9 9 4 年，a g a r g 和r t a m a s s i a 证明了若平面嵌入 没给定，4 一平面图的最小折数纵横嵌入问题是n p 一困难的，3 一平面图的最小折数纵 横嵌入问题可在多项式时间内解决1 9 9 8 年，g i u s e p p ed ib a t t i s t a ，g i u s e p p e l 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图的一些基本概念和定理 在数学上，一个图，常记为，是由二集合y 和e 所组成的使得其中e 是由所 有y 中元素对形成的集合的一个子集矿和e 分别称为g 的顶点集和边集，它们 的元素分别称为g 的顶点和边 如果允许矿中的一个元素与它本身组成一对，且e 中有这样的元素，称这种 边为环边，称这样的图为带环图 若e 中之元素允许重复出现，则这种重复出现的边称为重边具有重边的图 称为带重图既无重边又无环的图，称为简单图 设矿= h ，屹，屹) ，则v 的基数吲= n 称为g 的阶这里，我们只研究，l 为有 限的自然数，或者说是有限图的情况因此，l e l = m 也是有限的，称m 为g 的度 用( v f ，v j ) e 表示顶点h 与 ，之间有一条边，这时，称它们是相邻的而称， k 或_ 与这条边( k ，_ ) 是关联的有时，为方便，常想象每条边( 咋，) e 是由两 条半边( v ，_ ) 和( h ，_ ) 组成这时，称k 与半边( m ，_ ) 而不与半边( v ，_ ) 关联 与一个节点关联的边的数目称为这个顶点的次，记为d ( v ) 如果一个图的所 有顶点的次都相同( 设为d ( 1 ，) = k ) ，则称它为正则的( k 一正则的) 2 i 匕瘟銮垣太堂蚣堂焦监变量i 直 用s 表示图的边的数目，显然有d ( d = 2 占在图g 中的一个顶点和边的序 p e r 列v o e o v , e l 一v ，一l e t 1 1 , 1 使得k y ，i = o ，l ，乞e ，j = o ，1 ，l - 1 ，并且满足 勺= ( _ ，_ 一) ，j = o ，1 ，i - 1 ，i 1 ，则称它为和m 的一个途径 如果在一个途径中没有重复出现的边，则称为路如这个序列中v o = m ，则称 为闭的称闭径为环游，闭路称为圈 若一个图g = ( y ，e ) 的任何两个顶点都有g 中的一条路连接，则称g 是连通 的 因为“两个顶点间有一条路连接”，或“两顶点是连通的 确定顶点集上的一 个等价关系则在此等价关系下被分划为矿= k + + k ，并且遂产生e 的一个划 分e = 巨+ + e ，使得q = ( 形，互) ，l f s ，为g 的子图这时，q ，1 f - l v u ，v y ) ，称为 弧集 一个连通且无圈的图，称为树，记为t 如果图g = ( 矿，e ) 的一个子图t 是树 而且它的节点集矿( 丁) = v ，则称丁为g 的一个支撑树同时，t = ( 矿，e e ( 丁) ) 称为 g 的一个上树 因为e = ( 甜，y ) e e ( 丁) = e ( 于) 在r 上有且仅有一条连“和v 的路，从而p 与 r 形成恰好一个圈这个圈被称为g 对于r 的一个基本圈 一个边的子集s e ，如果从g 中将s 中的边去掉即得g s = ( y ，e s ) 的连 通片数比g 的多并且s 的任何子集均不再有此性质，则称s 是g 的一个上圈 i 匕塞交通太堂亟堂僮i 金室曼l 畜 因为一个图g 有一个支撑树丁当且仅当g 是连通的，和从中去掉任意一条边 均使丁剩下的部分由两个连通片组成，则丁的任一边p 与r 中的边形成恰好一个上 圈，称这个上圈为g 对于r 的基本上圈 图g 的基本圈和基本上圈的数目与丁的选择无关 若一个图是具有这样的一个图形，它的边仅在顶点处相交，则该图称为平面 图如果一个图能画在平面上使得它的代表边的曲线仅在端点相交，则称这个图 为可嵌入平面的，或称平面图平面图g 的这样一种画法称为g 的一个平面嵌入【5 】 记为( g ) 所有顶点度不大于七的可平面图，称为尼平面图 一个平面图，把平面分成若干个连通的区域，这些区域的闭包称为g 的面， 记为厂其中，唯一一个无界面称为无限面，记为石 用b ( f ) 表示平面图g 中面厂的周界若g 是连通的，则可以认为是一条闭途 径，g 在6 ( 厂) 中的每条割边都被这条途径经过两次；当b ( f ) 不包含割边时，这条 途径是g 的一个圈 称面厂与它的周界上的顶点和边是关联的称一条边分隔和它关联的面面厂 的度d ( f ) 是指和它关联的边的条数( 即d ( 门中边的条数) ，其中割边被计算两次 假如图g 的一个嵌入( g ) 中所有的边均用由水平或竖直线段组成的折线段表 示，则称它为g 的纵横嵌入每条边无折的嵌入称为网格嵌入【5 】 如果g 本身就是一个平面嵌入，则当它的一个与g 拓扑等价的纵横嵌入满足 条件：纵横嵌入的无限面与g 的无限面相对应，则称此纵横嵌入为g 的一个纵横 扩张，记为r ( g ) 在一条折线上，纵线段与横线段的交汇处，称为一个折；总折数达到最小的 纵横扩张称为最小折数纵横扩张每条边上均无折的纵横扩张称为网格扩张 称节点次不大于4 的图为常规的 上世纪9 0 年代，对于图的纵横嵌入的研究更趋深入刘彦佩教授在文献 2 】 中给出了这方面的奠基性的结果，建立了一种较系统的理论，己得到下列重要结 果： 定理1 1 连通4 平面图皆是3 可嵌入的 4 j e 塞交通厶堂亟堂僮i 金塞互l 言 定理1 2 一个3 连通4 一平面图g = ( v ，e ) 是2 一可嵌入的，当且仅当g 与兀。不 同构 在实际应用中，往往有这样的需求，即要找出电路图在平面上的最小折数嵌 入，这是很困难的而其中最基本也是最重要的一步就是研究一个嵌入的最小折 数扩张仅就最小折数扩张而言，要进一步得出一些简便的算法，尤其是线性算 法，还是不容易的 1 9 9 4 年，a g a r g 和r t a m a s s i a 证明了若平面嵌入没有给定，4 - 平面图的最小 折数纵横嵌入问题是n p 困难的，3 平面图的最小折数纵横嵌入问题可在多项式时 间内解决要彻底解决v l s i 布局优化问题，还有很多工作要做 本文在已有结论的基础上，给出了两类4 正则图的最小折数扩张的简便算法 5 2 对网格嵌入的判定 关于平面嵌入，在实际的线路设计中，不仅要考虑线路图是否能无交叉地画 在平面上，即电路板上，而且出于整齐，方便，高效的要求，我们还希望连接电 器元件的导线能保持水平或是竖直方向，且没有折网格嵌入就是所有边均用水 平或竖直线段表示且无折的平面嵌入本章从三个方面给出了网格嵌入的判定定 理及相应实例 2 i网格嵌入 对于任何一个图g = ( v ，e ) ，将每个节点 ，v 所关联的半边规定一个循环次序 并称之为节点1 ，处的旋，记为盯( 1 ，) 所有节点处旋的集合被称为图g 的旋，记为 o r ( g ) = 仃( v ) i v l ，乃 对一个给定的图g = ( v ，e ) 的任一个给定的旋o - ( a ) ，我们总能将g 画在平面 上使节点为点，两点之间的连续曲线为边，使得每一条代表边的曲线均除端点外 不通过任何代表节点的点，并且在每个节点附近的充分小的邻域中沿顺时针方向 绕此节点所确定的与它关联的半边循环序，就是给定的旋我们称这种图的表示 为它的一个浸入 假若图g 在一个平面嵌入( g ) 中所有的边均用水平和竖直线段组成的折线 段表示，则称它为g 的纵横嵌入一个平面嵌入( g ) 的纵横扩张，是指这样一个 平面嵌入7 ( g ) ，它与( g ) 的旋一样，且无限面相应 若g 的一个浸入( g ) 中所有的边均用水平和竖直线段组成的折线段表示，则 称它为g 的纵横浸入 在一个纵横嵌入中，可以在一条边上有几个内点，它们每个都与此边上的水 平和竖直线段相遇这些点称为所在边上的折每一条边上均无折的纵横嵌入称 为网格嵌入若嵌入p ( g ) 有一个纵横扩张，使得其中每一条边均无折，则称为网 6 格扩张 2 2 利用平衡图判定网格扩张的存在性 对一个常规图g = ( v ，目的平面嵌入( g ) ，f 为面的集合，记 厂一= 1 ，iv v v ，d e f ( v ) o ： 弋 l 只= ( 厂f 夥f ，r e s ( f ) o ) 下面引入二部图q u i = ( x o ，& ) 其中， f 如= u v ( i ) l l f 彤( 1 ，) ) ； i 饥 = u 厂( 川l _ ， - r e s ( f ) ； = uu 1 ，( 现f ( j ) ll d e f ( v ) ( 2 2 ) 。，怃y ( m l n j 且不存在c ，玩( g ；c ) c ( 或者玩( g ；c - ) c 觞) 使得也满足( 2 2 ) ，则称c 为面一非平衡的并且，用q 向。表示 定理2 3 一个常规图g 的无三角形面的平面嵌入( g ) 有一个网格扩张，当 且仅当在( g ) 中没有构形q 。( 或q 佑。) 构形q ，。和q 佑。也称为( g ) 的网格障碍 例如，图2 - 1 中给出的( g ) 中，取回路v 也k b u 为上圈c 4 这时，有 a e f ( v ) 1 ，v = 蟛( ) + 蟛( v ) + 珂( 屹) + 珂( k ) + 珂( 鸭) + 埘( k ) = 8 和 从而，有 r e s ( f ) = r e s ( f ) + r e s ( f 2 ) = o f ( 矿) d e f ( v ) r e s ( f ) j - j ，一 v e v 厂f ( 矿) 即( 2 1 ) 成立所以c 搴为q 。 易验证，这个( g ) 是没有网格扩张的 图2 - 1 在一个纵横嵌入中，可以在一条边上有几个内点，它们每个都与此边上的水 平和竖直线段相遇这些点称为所在边上的折 定理2 4 一个外可平面常规图g 有一个网格扩张，当且仅当 p ( 1 ，) 3 p 一4 ( 2 3 ) 惺y 其中p 是g 的节点数，p ( v ) 是节点v 的次 i a t _ 明： 设外可平面图g 的节点都在无限面f o 上，取c 为f o 的边界若c 为 q 伽，即满足( 2 - 3 ) ，也就是说 其中， r e s ( f o ) d e f ( v ) 讵y r e s ( f o ) = p + ( d + 4 = p + 4 9 ( 2 4 ) ( 2 5 ) j 匕塞銮迪太堂亟堂位监塞砬幽搔隧殴判定 d e f ( v ) = ( 4 一p ( v ) ) = 4 p 一p ( y ) ( 2 - 6 ) vv三y1 ，y 将( 2 5 ) ，( 2 6 ) 代入( 2 4 ) ，有 p + 4 4 p 一p ( y ) v v 整理上式，得 p ( ，) 3 p - 4 1 r 此时，由定理2 4 ，( g ) 有一个网格障碍，从而没有网格扩张 因此，当满足( 2 - 1 ) 式时，平面嵌入没有构形q 庙。，故( g ) 存在网格扩张 反之亦然 1 0 3 第一类4 正则图的纵横扩张 3 1广义平衡图的运输模型 设g = 缈，e ) 是一个4 平面图，自然是常规的，( g ) 是它的一个平面嵌入，f 是它的面集，f o 为无限面 对任意的y 矿，d e f ( v ) = 4 - a ( v ) ；d e f ( v ) 为顶点v 的亏数 对任意的f ，令【r e r e s s ( ( 厂f ) ) ：d d ( ( 厂s ) ) - + 4 4 , ，f 厂：厶f o ；称r e s ( 厂) 为面的赢数其 中，d ( s ) 表示f 的边界上边的个数 对于嵌入( g ) ，引进一个新图n ( , u g ) = ( 矿( ) ，e ( ) ) ，假若记 k = 矿l v y y ，d e f ( v ) o ， e ( k 一，) = ( v ，s l v v 一( 厂) ，v f ， ， e = ( z ，乃) j ，彳f , f a d j f ： ， 其中，( 1 ，f ) 表示从v 到f 的方向( 厂) 为f 面边界上属于一的节点的集 合z a d 蟛表示z 与乃相邻，称( g ) 为( g ) 的广义平衡图其中v ( n ) = 一u ，； e ( ) = e ( - - - h f ) u e 由性质：d e f ( f ) 一r e s ( f ) = r e s ( 厂) 可建立广义平衡图的运输问 v 矿， f 5 f ( f j d e f ( v ) om ( ) om ( ，) o 题模型如：6 ( g ) ) = m i n ，如，使得 = d e f ( k ) ，哆圪； ( v io ) e ( _ _ ，) ，j - i 吻+ 均= ( u 。o ) e ( _ + ，) ，l( z ，乃) e x q z ，x 42 一x i i r e s ( f ：) ，乃； o ，乃r o ； ( 3 - 1 ) r e s ( f j ) ，乃只； j 匕塞变亟太堂亟堂位i 金塞 一 筮= 娄垒：正则图的纵横芷送 其中，z + = o ，1 ，2 ，) 呀是相应于边( v ，乃) 的变量，是相应于边( z ，乃) 的 变量 若趵 o ，则在( g ) 的纵横扩张7 ( g ) 中，z 和乃边界的公共边上有均个折的 方向是从z 内的角到乃内的3 角 勃= x ( ，乃) = o ， ，乃= k 氐j 。f j = 兀 2 ， ，乃= 3 3 2一类4 正则图的广义平衡图模型 在4 一正则图的平面嵌入【g ) 中，d e f ( v ) = 4 一d ( 1 ，) = 0 ，且对v ，v ( u g ) ，在 它的纵横嵌入7 ( g ) 中有4 ，= 必其中，v 在面厂的边界上故吻= x ( ，乃) = o ， k = y l v l ，v , d e f ( ，) o = a 从而，4 一正则图( g ) 的广义平衡图( g ) 的模型 如下： 6 ( y ( g ) ) = m i n 虼 惦z p y g = r e s ( 乃) 加， ( 3 2 ) l 均z + ，v ( z ，) e ( ) 并且，4 一正则图g 的广义平衡图n ( t g ) 恰好是它的对偶图y ( g ) 中的有折边 和n ( , u g ) 中的有流向的边一一对应 3 34 一正则平面图的1 个初始图 阶为4 的4 一j 下则平面图，如鲰，。中( g ，。) 所示，h ，屹，屹是它的节点， f ( i = o ，1 ，2 ，3 ，4 ，5 ) 是它的面，其中f o 为无限面 1 2 仇 ( g ，。) 吼。 7 + ( , u g l y ，) 结论3 1 在鲰，。中所示的纵横扩张7 + ( g ，。) 是阶数为4 的4 一正则平面图 ( g ，。) 的最小折数纵横扩张，最小折数是8 证明：在图鲡 l 中的( g ，。) 给出了广义平衡图n ( z g ，。) 的一个可行解，且 厂( g 。) 即为其对应的一个解下证其最优性 在+ ( g ，。) 中，令六五为零向弧( 六一) ，则在。( g ，) 只需要验证三个基 本圈q ( 五彳工六五) ( f = 1 ，2 ，3 ) ；其中，( q ) = 2 ，允( q ) = o ( f = 1 ，2 ，3 ) ，故它们均为 规范圈可知7 。( g ，。) 为最优解，即7 ( g 。) 是最小折数纵横扩张，且其折数 县8 3 4构造方法及应用 3 4 i 构造方法 f 面我们研冗如伺由已知的1 个初始图得到阶为4 的4 - 正则图，得到一个图 类 构造方法如下：在已知的4 - 正则平面嵌入( g ，。) 中，任取一个节点_ ，按j 顿 时针方向记与巧关联的4 个面分别为厶，厶，f j 2 ，厶；在与相连的四条边上各增 加一个节点，按顺时针方向记为屹，屹。，屹m ，+ 。；连接( 心k - i ) ，( v 4 。，u 川) ， ( 屹v 4 聊) ，( v 4 k + 2 屹) ，则可得到新的平面嵌入( g ；h 。) ，如g “。中所示 显然可见在( g f m 。) 中会比原平面嵌入( g ，。) 增加4 个面，这四个面与_ 相 关联，按顺时针方向记为工t ，m ，五m 同时，( g ；一。) 的阶数比( q ，。) 增 加了4 g “l ，屹j - o i l i j y l i ， 7 4 k + l l 、 j 4 k + 3 六 ， 7 4 2 。，2 7 z ( g i n 。) ) 引理3 1 若y 。( g ，。) 是平面图( q ，。) 的最小折数纵横扩张，则由构造方法 得到的7 。( g ：卅。) 是( q 肼。) 的最小折数纵横扩张，折数增加4 证明：由( q ，。) 得到的4 一正则图的平面嵌入( q 船。) 所对应的广义平衡图 n + ( g ；斛) 模型中的一组可行解可以由n + ( q ，。) 的一组可行解得到 事实上，在( g ：小) 中新增加的四个面工。和六m ，工m ，工m 分别与面 厶，厶，厶，厶各有一条公共边( - p ) ，( 心。，屹) ，( u ，m ) 和( 屹，v 4 ) 在 ( g ，。) 中相应地增加四条流量为1 的弧( 。“，厶) ，= ( o ，1 ，2 ，3 ) ，和四条空白 边以。，五榭) ，川，厶m ) 舢，厶) ，朋，六。) 即得+ ( q 舢。) 的一组可行解， 如g 舢。中矿( ( g ：f n 。) ) 所示相应地，在7 ( g ，。) 中增加四条一折边n ，屹。) ， n 。，k 川) ，化m ，。m ) 和n m ，屹) ，则对应解的纵横扩张7 。( q n 。) 即得，如 鳞n 。中7 + ( ( q 一。) ) 所示 下证厂+ ( g ：n 。) 的最优性只需验证由空白边的所确定的四个基本圈 q ( 丘川丘川+ 。厶+ 。厶六川) ( ，= o ，1 ，2 ，3 ) ，( i = l ，2 ，3 ，4 ) 若厶厶是一条空白边，则有丑( q ) = 2 ，允( q ) = 2 ，( i = 1 ，2 ，3 ，4 ) ，q 为 规范圈，由定理3 1 可知，此解为最优解若厶厶是一条j 顿时针方向的弧，则有 以( c f ) = 2 ，无( q ) = o ；否则，有4 ( q ) = o ，允( q ) = 2 ，( i = 1 ，2 ，3 ，4 ) ；不论哪种 1 4 j 匕塞交通太堂亟堂位i 金塞筮二娄垒= 正则图的纵横芷张 情况，c ：f 都为规范圈由引理1 3 1 可知，此解为最优解 综上，7 ( q 船。) 的最优性得证，且折数比厂( q ，。) 增加了4 ，在，( g ：f 鼾。) 中新增加的4 个1 折边分别为( v 4 ，v 4 。) ，( v 4 。，v 4 州) ，“川，k 聊) ，n m ，h h ) 3 4 2 构造方法的应用 在矿如g i 。，) 中在与唯一的一个节点相连的每一条边上均增加一个节点，按顺 时针方向记为v 2 ，屹，心，屹；连接( 屹，v 3 ) ，( b ，k ) ，( 心，屹) ，( 屹，屹) ；与m 关联的三个面 顺时针记为石，z ，石，正( 为了描述的方便厶记了两次) ；新产生的四个面按顺时针 方向记为六，正，六，五；则此时( g l ，：) 产生，如鲂，：中的( g l ，：) 所示，它的阶为5 在( g i ，：) 中的7 个面中，新增加的四个面按顺时针方向记为z ，工，六，五，它 们的在边界上分别包含新节点和节点v l 的4 个面；在面的边界上包含新节点但不包 含节点m 的面仍记为五，z ，五 ，：“ 1 正j zk 1z以1 、 人广( g l ：) 广( q 。：) 鳞： 结论3 2 在岛，：中所示的纵横扩张7 ( g i ，：) 是阶数为5 的4 - 正则平面图 ( g i ，：) 的最小折数纵横扩，最小折数为1 0 证明：绣，：中的n + ( g i ，：) 给出了( g i ，：) 的广义平衡图n ( , u g x ，：) 的一组可行 解， o ( g l ，：) 即为一解，它为( g l ，：) 的一个纵横扩张 下证其最优性在( g i ，：) 中有四个基本圈c i ( 石五丘六石) ，乞( 丘石以六厶) ， 巳( 石石以彳五) ，c 4 ( 以六一六五) 其中，当i = l ，3 时，丑( q ) = 0 ，允( q ) = 2 ；而 当扣2 ，4 时，丑( q ) = 2 ，允( q ) = o ；故q ( f = 1 ，2 ，3 ，4 ) 均为规范圈由引理3 1 可 1 5 知，7 ( g i ，：) 为最优解 至此，得到了( g l ，：) 的最小折数纵横扩张，最小折数为1 0 在y ( g ，。) 中任取一个节点，不失一般性地取b ，与u 关联的四个面按顺时针 方向记为五，彳，正，六；在与m 相连的每一条边上均增加一个节点，按顺时 针方向记为屹，屹，鸭，v 6 依次连接( 屹，) 和( 屹，屹) ，( 屹，屹) ，( 吃，屹) 则4 - 正则平面 图( g ，：) 就构造出来了，它的阶为6 ，如吼，：中( g ，：) 所示 在( g ，：) 中的8 个面中，新增加的四个面按顺时针方向。记为六，六，无，石，它 们的在边界上分别包含新节点和节点m 的4 个面；在面的边界上包含新节点但不包 含节点m 的面仍记为厶，石，正，正 结论3 3 在编。：中所示的纵横扩张7 ( g ，：) 是阶数为6 的4 - 正则平面图 ( g ，：) 的最小折数纵横扩，最小折数为1 2 证明：岛，：中的( g ，：) 给出了( g 豇，：) 的广义平衡图( g ：) 的一组可行 解，+ ( g ，：) 即为其对应的一解 下证y ( , u g h ，：) 的最优性在n + ( , u g h ，：) 中只需要验证四个基本圈 q ( 彳五六五z ) ，q ( 六六五六五) ，c 3 ( f ，：o a a a ) ，c 4 ( f o r , ，a a f o ) 即可易得这四 个基本圈满足4 ( q ) = 0 ，允( q ) = 2 ，( i = 1 ，4 ) ；五( q ) = 2 ，丸( c f ) = 0 ，( i = 2 ，3 ) ， 它们都是规范圈；故y ( g 。：) 是最优解 至此，得到了( g ，：) 的最小折数纵横扩张，最小折数为1 2 1 6 在矿( g ，。) 中任取一个节点，不失一般性地取m ，与m 关联的四个面按顺时 针方向记为五，彳，五，石；在与v l 相连的每一条边上均增加一个节点，按顺 时针方向记为匕，屹，吩依次连接( 心，屹) 和( 屹，屹) ，( ，吻) ，( 屿，心) 则4 一正则平 面图( g ：) 就构造出来了，它的阶为7 ，如，。中( g ：) 所示 在( g ，：) 中的9 个面中，新增加的四个面按顺时针方向记为工，以，石，石，它 们的在边界上分别包含新节点和节点u 的4 个面；在面的边界上包含新节点但不包 含节点v l 的面仍记为石，石，五，石 结论3 4 在，：中所示的纵横扩张7 ( g ，：) 是阶数为7 的4 一正则平面图 ( g 。：) 的最小折数纵横扩张，最小折数是1 2 证明： ，：中的矿( g ，：) m i nt ( g ，：) 的广义平衡图( g ，：) 的一组可 行解，7 ( g ，：) 即为其对应的一解下证7 ( g ，：) 的最优性在( g ，：) 中， 令六五为零向弧( 石以) ，石五为零向弧( 石五) ；只需要验证四个基本圈 q ( 六六彳六) ，c 2 ( z 石石石石) ，c 3 ( 五石石五厶) ，c 4 ( 六五五石五) 易得这四个基本 圈满足以( c f ) = 0 ，丑( q ) = 2 ，( i = 1 ，2 ) ；以( q ) = 2 ，丑( q ) = o ，( i = 3 ，4 ) 它 们都是规范圈，故y ( g ，：) 是最优解 至此，得到了( g 。：) 的最小折数纵横扩张，最小折数是1 2 在矿( g ，。) 中任取一个节点，不失一般性地取m ，与h 关联的四个面按顺时 针方向记为f o ，z ，六，六；在与h 相连的每一条边上均增加一个节点，按顺时 针方向记为坞，1 c 6 ，b ，依次连接( 屹，屹) 和( ，吩) ，( 码，) ，( ，) 则4 - 正则平面 1 7 图( g ，：) 就构造出来了，它的阶为8 ，如鲸，。中( g ，：) 所示 在( g ，：) 中的1 0 个面中，新增加的四个面按顺时针方向记为以，石，石，石， 它们的在边界上分别包含新节点和节点m 的4 个面；在面的边界上包含新节点但不 包含节点m 的面仍记为厶，彳，五，石 ， p 【g ，z ) 屹 石 以 恢匠勿六硪 一磁翻7 i 7 ( p g ：) 结论3 5 在鲰，：中所示的纵横扩张厂( g 。：) 是阶数为8 的4 正则平面图 ( g ，：) 的最小折数纵横扩张，最小折数是1 2 证明：鲰，。中的( g ，：) 给出了( g ，：) 的广义平衡图( g e ，：) 的一组可行 解，y ( g ，：) 即为其对应的一解下证y 。( g ，：) 的最优性在( 川，：) 中， 令石彳为零向弧( 石石) ，石五为零向弧( z 六) ；只需要验证四个基本圈 c i ( z 石石五z ) ，c 2 ( l f , x l f o ) ，岛( l a f 。f o a ) ，q ( z 石以五z ) 易得这四个基本 圈满足五( c f ) = 0 ，丸( q ) = 2 ，( i = 1 ，2 ) ；4 ( q ) = 2 ，五( q ) = o ，( i = 3 ，4 ) 它 们都是规范圈，故7 ( g ，：) 是最优解 至此，得到了( g ，：) 的最小折数纵横扩张，最小折数是1 2 3 5本类4 一正则图的结果 定理3 1 按此构造方法得到的阶为4 ，z 的4 一正则平面图类鲰的纵横扩张 厂( g ，。) 的最小折数为4 ( 刀+ 1 ) ，( ，l = 1 ，2 ，3 ) 证明：咒= 1 时鲡，所示知定理显然成立假设定理对刀= k 时成立，下证定理 对以= 尼+ 1 也成立 j 京交通厶堂亟堂位论玄 箍= 差垒：匹则幽的纵撼芷丞 由归纳假设知，( g ，。) 具有最小折数纵横扩张7 ( g ，。) ，且其折数为 4 ( 老+ 1 ) 由引理知y ( g n ) 为( g 打。) 的广义平衡图n ( g 川) 对应模型的 一个最优解，且其最小折数为4 ( k + 1 ) + 4 = 4 ( k + 2 ) ；由归纳法原理知定理成立 因此，我们介绍了4 正则图的一个图类，对任意阶的4 正则图给出了它的一 个最小折数纵横扩张 3 6小结 本章主要研究了一类4 正则平面图的最小折数纵横扩张问题，介绍了4 一正则 图的一个图类，对任意阶的这样的4 正则图给出了它的一个最小折数纵横扩张算 法 对于一个可平面图，当它的平面嵌入不确定时，求它的所有最小折数纵横嵌 入中折数最少的问题，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 一正则平面图的最小折数纵横扩张，这类图的阶数 覆盖了所有的整数但这仍然只是所有4 正则平面图的一部分要找出一个线性 时间算法以给出所有4 正则平面图的最小折数纵横扩张仍然是不容易的较好的 思路是不断给出一些4 正则图类的最小折数纵横扩张 1 9 4 第二类4 正则图的最小折数纵横扩张 4 1已有的结论 上世纪9 0 年代，对于图的纵横嵌入的研究更趋深入刘彦佩教授在文献 2 】 中给出了这方面的奠基性的结果，建立了一种较系统的理论，已得到下列重要结 果： 定理4 1连通4 平面图皆是3 可嵌入的 定理4 2 一个3 一连通4 - 平面图g = ( v ，e ) 是2 - 可嵌入的，当且仅当g 与n 。不 同构 在实际应用中，往往有这样的需求，即要找出电路图在平面上的最小折数嵌 入，这是很困难的而其中最基本也是最重要的一步就是研究一个嵌入的最小折 数扩张仅就最小折数扩张而言，要进一步得出一些简便的算法，尤其是线性算 法，还是不容易的 1 9 9 4 年，a g a