（基础数学专业论文）几类4正则平面图的最小折数纵横扩张.pdf

j b 塞銮垣盔堂亟堂焦逾塞生塞翅要 中文摘要 摘要：本论文在一类4 一正则平面图最小折数纵横扩张构造方法的基础上，给 出了4 类4 一正则图，建立了它们的最小折数级横扩张，并且得到它们的最小折数 取决于它们的阶数。 全文共给出了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 ：b a s e do nt h ea l g o r i t h mf o rt 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 f ak i n do f 4 一r e g u l a rg r a p h s ，t h i st h e s i ss h o w sf o u rt y p e so f4 - r e g u l a rg r a p h s ，f o rw h i c h t h em 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 n sa r ee s t a b l i s h e da n dt h e i rm i n i m u n l b e n dn u m b 郇a l ed e t e r m i n e do n l yd e p e n d a n to nt h e i ro r d e r s t h e r ea r ef o u rc h a p t e r si nt l l i st h e s i s ： n 峙f 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 r , t 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 p l 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 a n dt h e 4 - r e g u l a rg r a p h s m 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 hi s 季v 掘 t h et h i r dc h a p t e rg i v e sa l la l g o r i t h mf o rg e t t i n gt h en l i l l 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 f ak i n do f 4 一r e g u l a r 乒a p l l s ，m a i n l yd i s c u s s e sf o u rt y p e s o f 4 - r e g u l a rf 印1 1 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 l n l u n lb e n dn m b e r 1 1 1 ef o u r 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 yw 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 啪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 0 ：0 1 5 7 5 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 导师签名： 签字日期：年月e t签字1 3 期： 年 月 日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名： 签字e l 期：年月 日 9 致谢 本论文的工作是在我的导师刘彦佩教授的悉心指导下完成的，刘彦佩教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来 刘彦佩老师对我的关心和指导。 刘彦佩教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，在此向刘彦佩老师表示衷心的谢意。 刘彦佩教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷 心的感谢。 在实验室工作及撰写论文期间，杨艳、邵泽玲、潘立彦、林丽莉、霍磊磊等 对我的论文的研究工作给予了热情帮助，在此向她们表达我的感激之情。 另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。 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 2 l o g n ) 时 间内构造一个平面嵌入的最小折数纵横扩张。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 都给出了有关纵横扩张的线性算 法。但这些算法都不能得到最小折数。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 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 图的一些基本概念口1 在数学上，一个图，常记为，是由二集合矿和e 所组成的使得其中e 是由所 有y 中元素对形成的集合的一个子集。y 和e 分别称为g 的顶点集和边集，它们 的元素分别称为g 的顶点和边。 如果允许v 中的一个元素与它本身组成一对，且e 中有这样的元素，称这种 边为环边，称这样的图为带环图。 若e 中之元素允许重复出现，贝这种重复出现的边称为重边。具有重边的图 称为带重图。既无重边又无环的图，称为简单图。 设矿= v l ，屹，) ，则v 的基数m = n 称为g 的阶。这里，我们只研究n 为有 限的自然数，或者说是有限图的情况。因此，i e j - m 也是有限的，称m 为g 的度。 用( m ，v ，) e 表示顶点v 与v i 之间有一条边，这时，称它们是相邻的。而称， 一或v ，与这条边( v i ，y ，) 是关联的。有时，为方便，常想象每条边( m ，v ，) e e 是由两 条半边( v j ，_ ) 和( 叶，_ ) 组成。这时，称v f 与半边( h ，叶) 而不与半边( 叶，_ ) 关联。 与一个节点关联的边的数目称为这个顶点的次，记为a ( v 1 。如果一个图的所 有顶点的次都相同( 设为d ( v ) = k ) ，则称它为正则的( k 正则的) 。 用占表示图的边的数目，显然有d ( y ) = 2 占。在图g 中的一个顶点和边的序 ：孑 列q 与札。呼一i 巧使得峙y ，i = 0 ，l ，弓e ，j = o ，l ，l - 1 ，并且满足 p ，= ( v ，v 一) ，_ ，= o ，1 ，l - 1 ，1 ，则称它为v o 和h 的一个途径。 如果在一个途径中没有重复出现的边，则称为路。如这个序列中v 0 = m ，则称 为闭的。称闭径为环游，闭路称为圈。 若一个图g = ( 矿，e 1 的任何两个顶点都有g 中的一条路连接，则称g 是连通 的。 因为“两个顶点间有一条路连接”，或“两顶点是连通的”确定顶点集上的 个等价关系。则在此等价关系下被分划为v = k + + e ，并且遂产生的一个划 分e = 巨+ + 互，使得g f = ( 巧，互) ，l i j ，为g 的子图。这时，g ：，1 s f j ，被称 为g 的连通片或连通分支。 如果图g = ( 矿，e 1 的一个顶点v v 具有这样的性质：在g 中将v 和与它关联的 边去掉所得子图即g y 的连通片数比g 的至少多一个，则v 被称为g 的一个割点。 如果图g = ( 矿，e 1 的一条边点e e 具有这样的性质：在g 中将e 和与它关联的 顶点去掉所得子图即g e 的连通片数比g 的至少多一个，则p 被称为g 的一个割 边。 若给定图g = ( y ，e ) 的每一条边e = ( ”，y ) e 以个方向，如从鼯到v 或从 ，到 “分别记为( “，v ) 或“) ，则所得的图被称为有向图。e = ( 蜘v l v u ，v e v ) ，称为 弧集。 一个连通且无圈的图，称为树，记为丁。如果图g = ( v ，e ) 的一个子图丁是树 而且它的节点集y ( r ) = v ，则称r 为g 的一个支撑树。同时，r = ( 矿，e 、e ( r ) ) 称为 g 的一个上树。 因为p = ( “，v ) e e ( n = e ( r ) 在丁上有且仅有一条连“和v 的路，从而e 与 r 形成恰好一个圈。这个圈被称为g 对于f 的一个基本圈。 一个边的子集s e ，如果从g 中将s 中的边去掉即得g s = ( 矿，f 、s ) 的连 通片数比g 的多并且s 的任何子集均不再有此性质，则称s 是g 的一个上圈。 因为一个图g 有一个支撑树f 当且仅当g 是连通的，和从中去掉任意一条边 均使丁剩下的部分由两个连通片组成，则r 的任一边e 与r 中的边形成恰好一个上 圈，称这个上圈为g 对于r 的基本上圈。 图g 的基本圈和基本上圈的数目与r 的选择无关。 若一个图是具有这样的一个图形，它的边仅在顶点处相交，则该图称为平面 图。如果一个图能画在平面上使得它的代表边的曲线仅在端点相交，则称这个图 为可嵌入平面的，或称平面图。平面图g 的这样一种画法称为g 的一个平面嵌入【5 】 记为u ( g 。 所有顶点度不大于k 的可平面图，称为k 平面图。 一个平面图把平面分成若干个连通的区域，这些区域的闭包称为g 的面， 记为厂。其中，唯一一个无界面称为无限面，记为厶。 用b ( 厂) 表示平面图g 中面厂的周界。若g 是连通的，则可以认为是一条闭途 径，g 在6 ( ，) 中的每条割边都被这条途径经过两次；当b ( s ) 不包含割边时，这条 途径是g 的一个圈。 称面，与它的周赛上的顶点和边是关联的。称一条边分隔和它关联的面。面厂 的度d ( f ) 是指和它关联的边的条数( 即d ( f ) 中边的条数) ，其中割边被计算两次。 假如图g 的一个嵌入u ( g ) 中所有的边均用由水平或竖直线段组成的折线段表 示，则称它为g 的纵横嵌入。每条边无折的嵌入称为网格嵌入【5 l 。 如果g 本身就是一个平面嵌入，则当它的个与g 拓扑等价的纵横嵌入满足 条件：纵横嵌入的无限面与g 的无限面相对应，则称此纵横嵌入为g 的一个纵横 扩张，记为r ( c ) 。 在一条折线上，纵线段与横线段的交汇处，称为一个折；总折数达到最小的 纵横扩张称为最小折数纵横扩张。每条边上均无折的纵横扩张称为网格扩张。 称节点次不大于4 的图为常规的。 1 3 运输问题 给定图g = ( 矿，e ) ，在它的顶点集v 中，有s 个发点( 或源) ，构成源集s ；t 个 收点( 或汇) ，构成汇集t ；其余的点称为中转站。 对于每一个源v ，有一个给定的正数口( v ) ，称为发量。对于每一个汇 ，有一 个给定的正数6 ( 订，称为收量。 对每一条边p 蠡，有一个权c ( 力，且d ( 帕= 6 ( 。设通过边p 的流量为 磊吾 躺，则运输问题的模型1 4 】为： m i n c ( 0 j ( p ) 【 “6 f 口( d ，v e s ； j ；缸。一圣x 2 o ，v 叭 u n( 1 ) 1 “辟 “ i 一6 ( 订，v t l瓤力o 其中，e 和e 分别表示从y 发出的边和进入 ，的边的集合。 模型( 1 ) 的一个可行解对应的图，称为流向图，其中有流向的边称为弧。基可 行解对应的图称为基流向图。 若在两个顶点“和v 之间既存在从1 , 1 到v 的非零流，又存在从v 到“的非零流， 则称“，y 问存在对流。显然，在基流向图中没有对流，且有流向的边不能构成圈。 令兄( c ) = ( c ) + 以p ) 一以( c ) ，友( c ) = n 0 ( c ) + 以( c ) - n _ ( c ) ：其中+ ( c ) ， 月一( c ) 和( c ) 分别表示圈c 中与顺时针方向一致的弧的总数，逆时针方向一致的弧 的总数和空白边的总数。 把仅含有一条空白边的圈称之为基本圈。显然，若c 是基本圈，则n o ( c ) = 1 。 若在圈c 中，丑d ) 0 以0 ) 0 ，则称c 为规范圈。 对运输问题已知下列结果： 定理1 3 1 1 7 1 运输问题的一个可行解是非退化的基可行解，当且仅当在它的 流向图中，有流向的边构成图g 的一个支撑树。 4 定理1 3 2 1 7 j 运输问题的一个可行解是最优解的充分必要条件是在其流向图 中无对流且每一个圈都是规范圈。 定理1 3 3 f 7 0 在基流向图中，对于由空白边( m ，v ，1 所确定的圈c 而言， 允( c ) = 乃，五( c ) = 以。 定理1 3 4 1 7o 若在基流向图中，对每一空白边f h ，y i ) 均有以o 和a 。2 0 ，则 此流向图对应的基可行解是最优解。在非退化的情形，反之亦然。 由定理1 3 1 可知，对于运输问题的一个非退化的基可行解总可以通过在其退 化的可行解所对应的流向图中的空白边( 无流向的边) 上补画零流向( 流量为零的流 向) 而得到。 引理1 3 1 i l 州运输问题的一个非退化的基可行解是最优解，则在其基流向图 中无对流且每一个基本圈都是规范圈；若在基流向图中无对流且每一个基本圈都 是规范圈，则此流向图对应的基可行解是最优解。 证明：由定理1 3 2 和定理1 3 - 3 和定理1 3 4 即得。 2 广平衡图模型 2 1 广义平衡图的运输模型 设g = y ，e ) 是个舡平面图，自然是常规的，( g ) 是它的一个平面嵌入，f 是它的面集，工为无限面。 对任意的v ev ，令d e f ( v ) = 4 一d ( v ) ；称d c f ( v ) 为顶点y 的亏数。 对任意的，f ，令【r e s r e s ( ( 厂) 一f ) = m d ( f ) + - 4 4 ，, 厂f ：兀f o ；称螂( ) 为面厂的赢数。其 中，d ( 厂) 表示，的边界上边的个数。 对于嵌入( g ) ，引进一个新图( 芦g ) = ( 矿( ) ，石( ) ) ，假若记 只= 矿i v v 矿，d e f ( v ) o ， e ( _ ，f ) = 9 ，) 1 w 一( 厂) ，v 厂e ， ， e = ( 正，) i b z ，石e f ，z a 4 圻 ， 其中，( v , f ) 表示从v 到厂的方向。u ) 为面边界上属于的节点的集合。 ，a 嘶表示z 与乃相邻，称( f g ) 为( g ) 的广义平衡图。其中y ( ) = u f 。 e ( ) = e ( k f ) u 。 由性质：d e f ( f ) - r e s ( f ) = r 器( 厂) 可建立广义平衡图的运输问 蜀；印箭) 。g 勰 题模型2 1 如下： 使得 6 ( g ) ) = l n i i l ，蜥 u ，疗肛 而= d e f ( v i ) ，m 一； “扣_ 呻，丘l 而+ = “，) e e ( _ - f ) ，u( i , ) e e x 4 z 。，x 口。一x i 瑚( 乃) ，乃罡； o ，昂； r e s ( f ：) 1 i f o 其中，z + = ( o ，1 ，2 ， i 是相应于边( 叶，乃) 的变量，均是相应于边，) 的 变量。 若均 o ，则在( g ) 的纵横扩张，( g ) 中，。和乃边界的公共边上有均个折的 6 方向是从z 内的角到乃内的角 f o ， 圻= 么 铲小阪麓1 2 ， 一 2 。24 一正则图的广义平衡图模型 在4 正则图的平面嵌入( g ) 中，d e f ( v ) = 4 一d ( v ) = o ，且对v ，e 矿( ，酊) ，在 它的纵横嵌入y ( g ) 中有4 ，= 。其中，v 在面厂的边界上一故2 工( ，乃) 卸， 以： y l v v e v ，d e f ( p ) o = o 。从而，4 - 正则图( g ) 的广义平衡图| ( g ) 的模型 如下： h r ( o ) ) = r a i n 乃 f 均= 嬲( 乃) ，乃e ， j ( 正乃k 5 l 乃6z + ，v z ，f ) e ( n ) 并且，4 正则图g 的广义平衡图g ) 恰好是它的对偶图 ( g ) 中的有流向的边一一对应。 ( 3 ) ，( g 中的有折边和 3 纵横扩张的最小折数 3 14 一正则平面图的4 个初始图 阶为1 的4 正则平面图，如鸟，中( g i ，。) 所示，h 是它的节点，f i ( i = o ，1 ，2 ) 是它 的三个面，其中二为无限面。 声( g 1 ，) 伊 五扣6 n ( g l l ) 广( q ) 结论3 1 1 在呸。中所示的纵横扩张r ( g i j ) 是阶数为1 的4 _ 正则平面图 ( g 1 ，) 的最小折数纵横扩张，最小折数为6 证明：乌，中的 广( g i ，) 给出了广义平衡图模型坛。) 的一个唯一可行解。 因此，。( g 1 。) 是( g j ，。) 的唯一纵横扩张，其最小折数为6 。 昏骠镪 謦留 阶为4 的4 正则平面图，如，中( g ，。) 所示，h ，屹，v 3 ，是它的节点， , ( f - - o , 1 ，2 ，3 ，4 ，5 ) 是它的面，其中工为无限面。 结论3 1 4 在知j 中所示的纵横扩张y ( g j ) 是阶数为4 的4 - 正则平面图 p ( g 。) 的最小折数纵横扩张，最小折数是8 。 证明：在图鲡，中的 广( 芦锦，) 给出了广义平衡图( g 0 ) 的一个可行解t 且 ，。( 麒葡，) 即为其对应的一个解。下证其最优性。 由定理1 3 1 ，在 r ( 卢g ，) 中，令正正为零向弧似) ，则在n ( g ) 只需要 验证三个基本圈q ( 二z 工正厶) o = 1 ，2 ，3 ) ；其中，五( 乌) = 2 ，九( e ) = o ( i = 1 ，2 ，3 ) ， 9 故它们均为规范圈。由引理1 3 1 可知，( g ) 为最优解，即，。( g 。) 是最小折 数纵横扩张，且其折数是8 。 3 2 构造方法及应用 3 2 1 构造方法 下面我们研究如何由已知的4 个初始图得到所有阶的本文要讨论的4 - 正则图， 即4 个图类。 构造方法如下：在己知的4 正则平面嵌入( q 。1 中，任取一个节点v ，按顺 时针方向记与y j 关联的4 个面分别为厶，厶，厶，厶：在与吩相连的四条边上各增 加一个节点，按顺时针方向记为k 。，k 。，_ 。；连接( k 。，) ，( ，。) ， ( k 。) ，( y 4 k + 2 , v 4 。) ，则可得到新的平面嵌入( g 川) ，如鳞川中所示。 显然可见在( q 川) 中会比原平面嵌入( q ) 增加4 个面，这四个面与叶相 关联，按顺时针方向记为凡，正。，正。+ 2 ，厶+ ，。同时，( q 川) 的阶数比( q 。) 增 加了4 。 研一 引理若y + ( q ) 是平面图( q 。) 的最小折数纵横扩张，则由构造方法得到 的y ( g 川) 是乒( g 舢) 的最小折数纵横扩张，折数增加4 。 证明：由卢( q 得到的4 - 正则图的平面嵌入( q 。) 所对应的广义平衡图 n ( q 川) 模型中的一组可行解可以由n 。( q 。) 的一组可行解得到。 事实上，在g ，。中新增加的四个面工。和工。，工。：，工。+ ，分别与面 厶，兀，厶，兀各有一条公共边( v 4 。，) ，( ，k 。) ，( 。) 和( v 4 。戌。) 。在 广( 呸。) 中相应地增加四条流量为1 的弧( 五。，兀) ，= ( o ，l ，2 ，3 ) ，和四条空白 边。，正。) ，正。) 。，工。) ，。，五。) 。即得n ( g l 。) 的一组可行解， 如鳞川中 p ( g n ) ) 所示。相应地，在y ( g 。) 中增加四条一折边( v 4 。，t 4 。) ， n 。，u 。) ，v 4 ，v 。：) 和( v 4 k + 2v 4 。) ，则对应解的纵横扩张y ( 卢g i 舢，) 即得，如 岛。中y i ( g ) ) 所示。 o 下证y ( p g + 。) 的最优性。只需验证由空白边的所确定的四个基本圈 q ( 正w 正k + l + l 厶。厶正wj ( ，= o ，l ，2 ，3 ) ，( i = l ，2 ，3 ，4 ) 。 若厶无是一条空白边，则有t 心) = 2 ，丑( q ) = 2 ，( f = l ，2 ，3 ，4 ) ，q 为 规范圈，由定理1 3 2 可知，此解为最优解。若丘兀是一条顺时针方向的弧，则 有五如) = 2 ，置如) = 0 ：否则，有五( 乌) = 0 ，足( q ) = 2 ，( i = l 234 ) ：不论哪 种情况，o 都为规范圈。由引理1 3 1 可知，此解为最优解。 综上，。( pg f m ) 的最优性得证，且折数比y ( g j ) 增加了4 ，在y ( g 0 + ，) 中新增加的4 个1 折边分别为n ，v 4 i ) ，“i ，h 。) ，n 。，1 ；4 。) n k + 2h ) 。 3 2 2 构造方法的应用 在y l # 蹋。) 中在与唯一的一个节点相连的每一条边上均增加一个节点，按顺 时针方向记为v 2 ，b ，k ，吩；连接( 屹，b ) ，( v 3 ，) ，( k ，v 5 ) ，( 屹，v 2 ) ；与匕关联的三个面 顺时针记为五，z ，工，五( 为了描述的方便f o 记了两次) ：新产生的四个面按顺时针 方向记为五，正，正，五；则此时( q ，：) 产生，如岛：中的( g 1 ：) 所示，它的阶为5 a 在p ( g i ：) 中的7 个面中，新增加的四个面按顺时针方向记为五，正，五，工，它 们的在边界上分别包含新节点和节点v 的4 个面；在面的边界上包含新节点但不包 含节点b 的面仍记为石，z ，五 匹日嘞 矿( 硒：) ，。( 鹏：) 结论3 2 1 在乌：中所示的纵横扩张，( q ：) 是阶数为5 的4 正则平面图 ( g i ：) 的最小折数纵横扩，最小折数为i o 证明：g i ，：中的( _ l g l ：) 给出了p ( g i ：) 的广义平衡图n ( p g 。：) 的一组可行 解，y ( 芦g 1 ：) 即为解，它为一( g i ：) 的一个纵横扩张。 下证其最优性。在n ( g i ：) 中有四个基本圈c l ( 五正工正兀) ，巳( o , a ：, o ) ， c 3 ( 工正正z 工) ，c 4 ( 兀五工正工) 。其中，当i = l ，3 时，以( c ) = 0 ，丑( q ) = 2 ；而 当f = 2 ，4 时，“) = 2 ，允( c i ) = 0 ；故c i ( f = 1 ，2 ，3 ，4 ) 均为规范圈。由引理1 3 1 可知，y ( 卢g l ，：) 为最优解。 至此，得到了( g 1 ：) 的最小折数纵横扩张，最小折数为1 0 。 在p f g ) 中任取一个节点，不失一般性地取h ，与k 关联的四个面按顺时针 方向记为工，z ，五，正；在与v l 相连的每一条边上均增加一个节点，按顺时 针方向记为屹，v 4 ，h ，。依次连接h ，v 4 ) 和( v 4 ，v 5 ) ，( v 5 ，) ，( v 6 ，屿) a 则4 - 正则平面 图( g ，：) 就构造出来了，它的阶为6 ，如岛2 中( g ：) 所示。 在( g ：) 中的8 个面中，新增加的四个面按顺时针方向记为a ，正，兀， ，它 们的在边界上分别包含新节点和节点v 1 的4 个面；在面的边界上包含新节点但不包 含节点v l 的面仍记为兀，z ，五，五。 鲕- 结论3 2 2 嘲在鲕，：中所示的纵横扩张y ( 卢g 。) 是阶数为6 的4 正则平面图 ( g ，：) 的最小折数纵横扩，最小折数为1 2 。 证明：岛。中的( g ：) 给出了( g ，：) 的广义平衡图( g ：) 的一组可行 解，广( g ：) 即为其对应的一解 下证y ( g ：) 的最优性。在( , u g h ，：) 中只需要验证四个基本圈 q ( z 正工正正) ，岛( 正正兀五五) ，c 3 ( 五五石工五) ，( 五z a ，f o ) 即可。易得这四 个基本圈满足丑( q ) = 0 ，丑( q ) = 2 ，( i = 1 ，4 ) ；丑( q ) = 2 ，丑( 岛) - - - 0 ，( i = 2 ，3 ) ， 它们都是规范圈；故厂( a g n ：) 是最优解 至此，得到了( g ：) 的最小折数纵横扩张，最小折数为1 2 。 在y f g r ) 中任取一个节点，不失一般性地取q ，与q 关联的四个面按顺时 针方向记为工，z ，正，石；在与u 相连的每一条边上均增加一个节点，按顺 时针方向记为v 4 ，v 5 ，v 6 ，屿。依次连接( 心，岵) 和( 屿，v 6 ) ，( v 6 ，v 7 ) ，( 叶，) 。则4 _ 正则平 面图p ( g ，：) 就构造出来了，它的阶为7 ，如2 中芦( g ：) 所示。 在( g ：) 中的9 个面中，新增加的四个面按顺时针方向记为五，正，石， ，它 们的在边界上分别包含新节点和节点y l 的4 个面；在面的边界上包含新节点但不包 含节点v 的面仍记为五，石，五，五。 2 静 殛 入 囝删 垫夏至适态堂亟堂鱼i 金塞2 熟趱芷韭丝量尘堑堑 石圆圆 p ( )q 嘎) r ( 蝇z ) 证明：。中的( g ，：) 给出了卢( g 珂：) 的广义平衡图_ j v ( u g m ：) 的一组可行 解，( g ：) 即为其对应的一解。下证y ( 卢g ：) 的最优性。在矿( g ，：) 中，令 工五为零向弧( 正五) ，二五为零向弧( 石五) ；只需要验证四个基本圈c l ( 正正五正) ， c 2 ( f , l a l 石) ，岛( 五五石厶工) ，c 4 ( 正正五厶五) 。易得这四个基本圈满足 五如) = o ，无如) = 2 ，( i = i ，2 ) ；丑如) = 2 ，丑如) = o ，( f = 3 ，4 ) 。它们都 是规范圈，故y ( 卢g ：) 是最优解 至此，得到了( g ：) 的最小折数纵横扩张，最小折数是1 2 。 在y f 岛) 中任取一个节点，不失般性地取v l ，与v 1 关联的四个面按顺时 针方向记为厶，五，正，疋；在与h 相连的每一条边上均增加一个节点，按顺 时针方向记为v 5 ，心，v 7 ，y 8 。依次连接( v 5 ，v 6 ) 和( y 6 ，v 7 ) ，( 叶，v 8 ) ，( h ，) a 则4 - 正则平 面图( g 0 。) 就构造出来了，它的阶为8 ，如鲸：中( g ：) 所示。 在卢( g ，：) 中的1 0 个面中，新增加的四个面按顺时针方向记为五，石， ，五， 它们的在边界上分别包含新节点和节点v l 的4 个面；在面的边界上包含新节点但不 包含节点h 的面仍记为五，五，五，五。 v 2 五 弘 愀匆一正卅 匕剁7 i v 4 7 ( 鹏让) 结论3 2 4 在鲡，：中所示的纵横扩张，( g ：) 是阶数为8 的4 正则平面图 ( g ：) 的最小折数纵横扩张，最小折数是1 2 。 证明：鲡2 中的j ( g ：) 给出了( g ：) 的广义平衡图( 艉：) 的一组可行 解，( g ：) 即为其对应的一解。下证y ( g ：) 的最优性。在( g ：) e f ， 令正z 为零向弧( 正石) ，正五为零向弧( 六正) ；只需要验证四个基本圈 c i ( 石六二石z ) ，c 2 ( 石z 五兵五) ，c ，( 五五 五五) ，c 4 ( 石石五五石) 。易得这四个基本 圈满足丑b ) = o ，是 ) = 2 ，( i = 1 , 2 ) ；丑( q ) = 2 ，允( q ) = o ，( i = 3 ，4 ) 。 它们都是规范圈，故y ( g ：) 是最优解。 至此，得到了( g 0 ，) 的最小折数纵横扩张，最小折数是1 2 。 3 3 有关4 类4 一正则图的结果 定理3 3 1 按构造方法得到的阶为4 h 一3 的4 正则平面图类虽的纵横扩张 ，( g i ) 的最小折数是4 n + 2 ，o = 1 ，2 ，3 ) 。 证明：( 用数学归纳法) 当盯= 1 ，2 时，由岛。和岛：所示知定理显然成立。假设定 理对n = k 成立，下证定理对疗= 七+ 1 也成立。 由归纳假设可知( g l j ) 具有最小折数纵横扩张y ( g f ) ，折数为4 k + 2 。由引 理可知，( 鹏舢) 为平面图g i 川) 的广义平衡图矿g i 舸) 对应模型的一个最 优解，且其最小折数为4 七+ 2 + 4 = 州七+ 1 ) + 2 ；由归纳法原理知定理成立。 定理3 3 2 按构造方法得到的阶为4 一一2 的4 正则平面图类鲡的纵横扩张 ，( g 。) 的最小折数为4 ( n + 1 ) ，( n = 1 ，2 ，3 ) 。 证明：( 用数学归纳法) 当 = 1 , 2 时，由j 和：所示知定理成立。假设定理对 露= k 成立，下证定理对月= k + 1 也成立。 由归纳假设知，p ( g ) 具有最小折数纵横扩张y ( g n ) ，且其折数为 4 + 1 ) 。由引理知，( g 川) 为( g “。) 的广义平衡图n ( g m ) 对应模型的一 个最优解，且其最小折数为4 ( k + 1 1 + 4 = 4 + 2 ) ；由归纳法原理知定理成立。 定理3 3 3 按构造方法得到的阶为4 以一1 的4 正则平面图类的纵横扩张 y ( g 皿，。) 的最小折数为4 ( h + 1 ) ，( h = 1 ，2 ，3 ，) 。 证明：刀= l 时由，所示知定理显然成立。假设定理对”= k 时成立，下证定 理对n = k + 1 也成立。 由归纳假设知，( g 。) 具有最小折数纵横扩张y ( 卢g 。) ，且其折数为 4 + 1 ) 。由引理知y ( p g n ) 为卢( g 。) 的广义平衡图n + ( g 。) 对应模型的 一个最优解，且其最小折数为4 ( k + 1 ) + 4 = 4 ( | i + 2 ) ；由归纳法原理知定理成立。 定理3 3 4 按此构造方法得到的阶为4 h 的4 正则平面图类知的纵横扩张 y ( g ，) 的最小折数为4 ( n + 1 ) ，( n = l