（运筹学与控制论专业论文）关于纵横扩张的优化.pdf

摘要 随着 计算 机的 发展， 超 大规模集成电 路( v l s i ) 的 集成度 愈来愈高， v l s i 布局优化亦就更为重要.国外有些专著把这一间题视为未来新型计 算机设计成败的关键 在3 0 年代，k u r a t o w s k i , wh it 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 ma 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 l a , l . g .t o l l i s 和 j . s . v i t t e r ; 和 i l e x i n都给出了有 关纵横扩张的线性算法.但这些算法都不能得到最小折数 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 e d i b 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 o v a r g i u 设 计了 一 个多 项 式时 间 算 法， 在 平 面嵌 人 没 有给 定的 倩 况下， 求两类图( s e r i e s - p a r a l le l g r a p h 和3 一 平面图 ) 的最小 折数纵横扩 张 . 本文主要研究了纵横扩张的折数优化间题.全文共分五章: 第一章介绍了一些基本概念及相关的定理. 4 第二章在刘彦佩教授对图的可嵌入性研究的基础上建立了广偶图的 运输问题模型，得到了最小折数纵横扩张的判别准则.根据 4 一 正则平面 图的性质，得到了它的判别准则 第三章利用 牛正则平面图的判别准则， 求出了四类 牛正则纵横扩张 的最小折数. 并在线性时间内构造了它们的最小折数纵横扩张. 且推广了 这一结果. 迄今为止， 还没看到有关最小折数纵横扩张的并行算法， 第四章提供 了 一 个 成本 为 9 l 3 ) 的 并 行算 法， 求解 平面 嵌 入的 最小 折数 纵横扩张 第五章提供了一些需进一步研究的问题 关健词广偶图，规范圈，可规范圈，标准边割，可调序列 ab s t r a c t n o w , t h e i n t e g r a t i o n d e g r e e o f v l s i b e c o m e s h i g h e r a n d h i g h e r w i t h t h e d e v e l o p m e n t o f c o m p u t e r . t h e o p t i m i z a t i o n o f v l s i i s m o r e i m p o r t a n t . t h i s p r o b l e m is r e g a r d e d a s a k e y t o n e w - s t y l e c o m p u t e r i n s o m e w o r k s i n o t h e r c o u n t r y . k u r a t o w s k i , wh i t n e y a n d ma c la n e s o l v e d t h e p l a n a r e m b e d d i n g p r o b le m i n d e p e n d e n t l y i n t h e 1 9 3 0 s . s c h o l a r s b e g a n t o r e s e a r c h r e c - t i l i n e a r e m b e d d i n g s o f a g r a p h i n t h e 1 9 8 0 s . l .v a l i a n t p r o v e d t h a t a g r a p h h a s a r e c t i l i n e a r e m b e d d i n g if , a n d o n l y if , i t i s 4 - p l a n a r . t h e n r . t a m a s s i a d e s i g n e d a n a l g o r it h m t h a t f o r m s t h e m i n i m u m b e n d r e c - t i l i n e a r e x t e n s i o n o f a p la n a r e m b e d d i n g i n o ( n l o g n ) . r .t a m a s s i a a n d i . t o l l i s p r o v i d e d a l i n e a r a l g o r i t h m t o c o n s t r u c t a r e c t i l i n e a r e x - t e n s i o n o f a p l a n a r e m b e d d i n g . t h e r e s e a r c h f o r t h e r e c t i l i n e a r e x t e n - s i o n s o f g r a p h s w a s f u r t h e r d e v e lo p e d i n t h e b e g i n n i n g o f 1 9 9 0 s . y . p l i u e s t a b l i s h e d t h e r e l a t e d t h e o r y . s u b s e q u e n t l y , y . p . l i u , mo r g a n a a n d s i me o n e ; k a n t ; r . t a m a s s i a , i . g. t o l l i s a n d j . s . v i t t e r ; a n d h e x i n p r o v i d e d s o m e l i n e a r a l g o r i t h m s t o g e t t h e r e c t i l i n e a r e x t e n s i o n s o f g r a p h s . h o w e v e r , t h e s e a l g o r i t h m s c o u l d n o t o b t a i n t h e m i n i m u m b e n d r e c t i li n e a r e m b e d d i n g . a . g a r g a n d r .t a m a s s i a p r o v e d t h a t t h e r e c t i l i n e a r e x t e n s i o n o f t h e 4 - p l a n a r g r a p h w i t h o u t g i v e n p l a n a r e m - b e d d i n g s is n p - h a r d , a n d t h a t t h e r e c t i l i n e a r e x t e n s i o n o f t h e 3 - p l a n a r g r a p h i s p o l y n o m i a l i n 1 9 9 4 . g i u s e p p e d i a a t t i s t a , g i u s e p p e l i o t t a 6 a n dr a n c e s c o v a r g i u p r o v i d e d a p o l y n o m i a l a l g o r i t l u n t o c o n s t r u c t t h e m i n i i n u i n b e n d r e c t i l i n e a r e x t e n s i o n s o f s e r i e s - p a r a l l e l g r a p h a n d 3 - p l a n a r g r a p h s w i t h o u t g i v e n p l a n a r e m b e d cl i n g s i n 1 9 !9 t h i s a r t i c l e c h i e fl y r e s e a r c h t h e b e n d o p t i m i z a t i o n o f t h e r e c t i l i n - e a r e x t e n s i o n . t h e r e a r e fi v e c h a p t e r s i n t h e a r t i c l e : 丁 h e fi r s t c h a p t e r i n t r o d u c e s s o m e b a s i c c o n c e p t s a n d r e l a t e d t h e - or i es i n t h e s e c o n d c h a p t e r t h e t r a n s p o r t a t i o n m o d e l o f t h e g e n e r a l i z e d c l u a l g r a p h i s c o n s t r u c t e d o n比 e b a s i s o f t h e y . p . l i u s r e a .s e a r c h f o r e m b e d a b i l i t y i n g r a p h s . t h u s . t h e c r i t e r i a , o f t h e m i n i m u m b e n d r e c t i l i n e a r e x t e n s i o n c a n b e o b t a i n e d . a c c o r d i n g t o t i l e p r o p e r t 一 o f 4 - r e g u l a r p l a n a r g r a p h . i t s c r i t e r i a a r e o b t a i n e d t h e t h i r d c h a p t e r g e t s t h e m i n i m u m b e n d r e c t i l i n e a r e x t e n s i o n s o f f o u r t y p e s o f =1 - r e g u l a r p l a n a r e rn b e d d in g s . t h e e x t r a c t i o n o f m in i - n o u n b e n d r e c t i l i n e a r e x t e n s i o n s i s i n l i n e a r t i me . f u r t h e r . t h e r e s u l t i s g e n e r a l i z e d b i l l n o w . n o p a r a l le l a l g o r i t h m i s s e e n o n t h e t o p i c .八p a r a l l e l a l g o r i t h m w i t h c o s t o ( n ) i s g i v e n t o s o l v e t h e m i n i m u m b e n d r e c t i- l i n e a r e x t e n s io n i n c h a p t e r f o u r . t h e fi f t h c h a p t e r p r o v id e s s o m e p r o b l e m s f o r f u r t h e r r e s e a r c h k e y w o r d s g e n e r a l i z e d d u a l g r a p h : n o r m a l c i r c l e : s t a n d a r d i z e d c i r c l e : s t a n d a r d e d g e c u t : a d j u s t a b l e s e q u e n c e 非常感谢导师刘彦佩教授对我的关怀与帮助. 是他引 我走上了科学研究的大门. 他的严谨治学的态度， 求真务 实的工作作风， 对我产生了深刻地影响， 我将铭记刘老师 的教诲，努力工作，不断进取， 我由衷感激修乃华， 冯衍全， 常彦勋， 郝荣霞和何卫 力等老师的支持与帮助，并向所有关心与支持我的人们 表示深深的谢意， 第一章引言与综述 ,j 1 . 1 引言 在各种超大规模集成电路 ( v l s i ) 的布局中，常将元件视为 平面上的点，元件间的导线视为平面上的曲线，电路板视为平 面. 这样， 就把一个电路变成了一个图.由于电路上的导线不允 许交叉， 相应地， 平面上的曲线也不允许有交叉. 这就需要研究 图的平面嵌入问题.这引起了数学界的广泛关注. 在3 0 年代，k u r a t o w s k i h l l , wh i t n e y 和m a d a n e ll s 分别 解决了图的平面嵌入存在性问题，8 0 年代，开始出现单层双面 的模型， 即导线的走向为水平和竖直两个方向. 水平线分布在一 面，竖直线位于另一面， 这些导线用水平和竖直的折线连接起 来. 在一条导线上水平和竖直线段的交汇处需打孔. 不同的导线 在除元件处外不能有交叉. 相应地， 用纵线和横线表示边的平 面嵌人，即为纵横嵌入. 学者们开始研究图的纵横嵌入的有关 问题.l . v a li a n t ll 7 证明了 一个图 有纵横嵌入的充要条件是它是 4 - 平面的. 随后，r .t a m a s s i a l 1 8 1 设计了一个算法， 在0 ( n lo g 哟 时间内构造一个平面嵌入的最小折数纵横扩张甲 r . t a r n a s s is 和 i .t o l l i s l t e l 提供了一个线性算法，构造平面嵌入的纵横扩张 9 0 年代，对于图的纵横嵌入的研究更趋深入. 刘彦佩教授建立 了有关的基本理论，可知下列重要结果: 定理 1 . 1 . 1 1+ 1 连通4 一 平面图皆 是3 一 可嵌入的 硕士研究生学位论文2 0 0 2年 定理 1 . 1 .2 14 1 一个3 - 连通4 - 平面图g = ( v , 助是2 一 可嵌入 的，当且仅当g与i i 。 不同构 此后， y .p . l i u , m o r g a n 二 和 s i m e o n e p 0 1 , k a n t l , t a m a s s i a t o l l is 和 v it t e r z 2 和 h e x in 12 31 都给出t 有关纵横扩张的线性 算法 但 这些 算法都不能 得到最小 折数，1 9 9 4 年，a .g a r g 和 r .t a m a s s ia l2 4 l 证明了若平面嵌入没给定， 4 一 平面图的 最小折数纵 横嵌入问题是n p - 困难的，3 一 平面图的最小折数纵横嵌入问题 可在多 项式时间内 解决1 9 9 8 年，g i u s e p p e d i b a t t is t a , g iu s e p p e l io t t a 和f r a n c e s c o v a r g i u l l 设计了一个多项式时间 算法， 在平 面嵌入没有给定的情况下， 求两类图 ( s e r ie s - p a r a ll e l g r a p h 和3 - 平面图)的最小折数纵横嵌入. 随着计算机的发展， 超大规模集成电路的集成度愈来愈高， v l s i 布局优化亦更为重要.国外有些专著把这一间题视为未来 新型计算机设计成败的关键. 要彻底解决v l s i 布局优化问题， 还需许多数学工作者的不懈努力. 戈 1 . 2图及纵橄扩张 一个图 g就是指一个集合v及其上的一个二元关系r . v是 顶点集， 其中的元被称为顶点 ， 任意的。 v e v , 若( 。 ， 司 r, 则。 与。 有一边相连. 顶点， 和。 称为是这条边的端点， 这条边 称为端点。 和v 的关 联边. 所有边的集合记为e ， 记g = ( v , e ) 在一个图中，与顶点。 关联的边的个数， 称为顶点。 的度，记 为d ( v ) 若对 任意的 v 有武 司= k ， 称此图 是k 一 正则的 用 关于级梭扩张的优化 。 表示图中边的数目，显然有 又d ( u ) = 2 e . e v 若一条边的两个端点重合， 则称之为环. 若两个端点之间的 边多于一条，则称有 重边. 既无重边也无环的图称为 尚单的甲 在 g中， 若w=u p e l u l e 2 二e k u k 是一个顶点和边的交替序 列，使 。 ， =( u i - 1 , u . ) , d 。 二1 . 2 ， 一 ， k 称 y v为从 。 。 到 。 * 的途径.。 。 和 : 。 分别称为 w 的起点和终 点. w 的长度为k . 在一个途径中， 若任意两条边皆不相同， 则称 之为迹 若在迹中任意两个顶点皆不相同， 则称之为路 起点和 终点相同的途径， 迹和路分别称为迁，回和圈. 若一个图中任意 两个顶点之间存在一条路，则称此图是连通的. 图g的每一个 连通的部分， 称为它的一个连通分支. 若去掉一条边后使得连通 分支增加，则称此边为口的 刻边. 若去掉某些边后使得连通分 支增加，则称这些边为( 11 的一个边刻- 对于两个图 ， =戈 v , , e , ) 和g=( v , 助、 若v , c v , i ; , c e 则称 g : 是g的一个 子图. 若v , 二v ， 则称g : 为g的支撑子图. 对任意的e , ce ， 称 “ ， 二( v i , e , ) 为g的边导出 子图， 其中vi 是所有与e , 中的边关联的顶点的集合一 在一个图g中， 若去掉 一个顶点后的边导出之图仅有一个公共点，则称此顶点为 g的 刻点 连通无圈图称为树 一个树又是一个支撑子图， 称为支撑 树 对于图的每一个支撑树， 每一条不在支撑树上的边与此支撑 硬士研兔生学位论文2 0 0 2年 树恰形成一个圈，称为这条边所在的 基本圈 一个有向图 g二( v , e ) 是指集合v上的一个二元有序关系 r ， 若。 r v , 则称有一个从。 到。 的弧， 记为( 。 ， 岭 。 和v 分别称 为这个弧的起点和终点. e = ( v , 州u r v , v u , v e v 是弧集 对于图g ， 给它的所有顶点处的关联边规定一个循环序， 若 可以把它划在平面上，使得代表边的曲线除端点外无其它公共 点， 则称为图g的一个平面嵌入 ( 或平面图 ) ， 记为川 哪 g称为 可平面图. 所有顶点度不大于 k 的可平面图，称为k - 平面图 一 个平面图， 把平面分成若干个连通的区域， 这些区域称为面. 其 中，唯一一个无界面称为无限面， 记为f o . 在每一个面的闭包上 的边集称为这个面的边界. 面 f 的边界上边的数目称为了 的度， 记为d ( f )若在g的一个平面嵌入中， 所有边都用由 水平和竖直 的线段组成的折线来表示，则称此嵌入为 纵横嵌入 无限面确 定的纵横嵌入称为级横扩张， 记为-y ( g ) . 在一条折线上， 纵线 段与横线段的交汇处，称为一个析. 每条边上的折数都不超过， 的纵横嵌入，称为卜 嵌入_ 所有边都无折的纵横扩张和纵横嵌入 分别称为 网 格扩张和 网格嵌入 折数达到最少的纵横扩张称为 最小拆数的 x 1 .3 线性规划 线性规划的一般形式是: m i n 了二( 1 . 1 ) 关于纵横扩张的优化 其中， 。 是。一 维列向 量， t 表示向 量的 转置， a=( a t a 2 . . . a n ) 为一个秩为。的mx n 矩阵，b 和a ; , i = 1 , 2 , . . . , n 是。一维列 向量，他们都是常量. 设b为a的一个非奇异子矩阵，则称b 是线性规划间题的 一个基 . 不失一般性， 令b=a, a 2 , ， .a 司， 称a , (j = 1 , 2 ， 二 ， 叫为 基向 量， 与 基向 量a ， 相应的 变 量为基变 全， 否则为 0基变1 相应于基的一个解二 =( b - l b , 0 ) 称为线性 规划的一个基解. 满足约束条件 ( l 2 ) , ( 1 . 3 ) 的 解， 称为线性规划 问题的可行解. 满足条件 ( 1 .3 ) 的基解称为塞可行解. 对应于基 可行解的基称为可行基. 基解中非零分量的个数小于 二时，这 个基解是退化的， 否则， 称为昨退化的. 类似地， 基可行解中非 零分量的个数小于。时， 称为退化的基可行解， 否则， 称为 非 退化的基可行解. j 1 . 4 运翰问题 给定图 构成 源集 s 站 对于f 4- - g=( v , e ) ， 在它的顶点集l 中， 有， 个发点( 或 源 ) ， t 个收点( 或汇 ) ， 构成汇集t 一 个源 。 ， 有一个给定的 一个汇， 1 ， 有一个给定的正数b ( 劝 正欲 a ( v ) 称为 收贵 其余的点称为中转 称为岌黄一 对于每 对每一条边。 e e , 有一个权 c ( e ) . 且 ea ( v ) 二e b ( v ) ,ft 设通过边。 的流量为a ( e ) , 硕士研究生学位论文2 0 0 2年 则运枪间题的模型 16 1 为: m in 艺c ( e ) 二 ( 。 ) a ( v ) , 。 s ; e 以司一 。 仁 e 才e e e 0 , 。 ev ( s u t ) ; ( 1 . 4 ) 一 6 ( 。 ) ， 。 t 了.，.j、. 一- 、.，户 e 了.、 工 x ( e ) 全0 其中，e , 和e p 分别表示从。 发出的边和进入。 的边的集合. 棋型( 1 .4 ) 的 一个可行解对应的图 ， 称 为流向图， 其中 有流 向的边称为弧. 基可行解对应的图称为基流向图 . 若在两个顶点 u .。 间，既存在从， 到 。 的非零流又存在从。 到。 的非零流，则 称。 ，。 间存在对流 显然.在基流向图中没有对流，且有流向的 边不能构成圈. 如果一个基可行解是退化的， 必须从空白边上给 出 流量为零的 弧 ( 称为0 一 流弧 ) 的 方向 指定一个顶点为每一个 支撑树的根. 当去掉支撑树的一个弧后， 支撑树分为两个分支， 称包含根的那个分支为根分支_ 如果。 一 流弧总是指向根分支， 这个基流图称为 规范流向图 令 户 一 ( c ) =m o ( c ) +m 一 ( c ) 一。 十 ( c ) p + ( c ) =m o ( c ) +m + ( c ) 一。一 ( c ) 其中，。 十 ( c ) ， 二 一 ( c ) 和。 。 ( 自分别 表示圈c中 与顺时针方向 一 致的弧上的总权，与逆时针方向一致的弧上的总权和空白边上 关于纵徽扩张的优化 的总权.若在圈c中，p - ( c ) _ o , p + ( c ) o , 则称 c为正规圈 定理1 . 4 . 1 (7 1 运输间 题的一个可行解是非退化的 基可行解充 分必要条件是在其流向图中，有流向的边构成一个支撑树. 定理1 .4 . 2 17 运箱间 题的一个可行解是最优解的充分必要条 件是在其流向图中无对流且每一个圈都是正规圈. 定理1 . 4 . 扩 运输间题的一个基可行解是最优解的充 分必要 条件是在其基流向图中每一个基本圈都是正规圈. 1 . : 本文的主要结论 本文在基础上，主要研究了纵横扩张的优化间题. 全文 共分五章 : 第一章介绍了有关的基本知识 第二章建立了广偶图的运输问题棋型如下: , , ( y ( g ) ) 二 : m t n 2 ; j e ( j +y i ) (f; , f , ) e e =d e f ( v ; ) , 、 l 斗 ( ,. f , ) e e ( v + 一 f ) ， 九任及 艺丁 :， +l nj 一y i p ) ( . ; , f e ) e e ( v + - f d ( f ; , f t ) f ) f t 凡， ( 2 . 1 ) ， i i 任凡 九方 tes叭ies -一 r . r , y ii z + i d ( v . i f l ) , ( f . , 1 i ) e ( h ) 一、.己t，.吸 其中z + = 0 , 1 , 2 , ， 硕士研究生学位论文2 0 0 2年 进而得到了最小折数纵横扩张的充要条件: 定理2 . 2 . 5一个平面嵌入的纵横扩张是最小折数的当且仅 当在其广偶图模型的流向图中，无对流且无可规范圈. 定理2 . 2 . 8 p ( g ) 的h ( p 伪棋型的一个基可行解所对应的纵 横扩张是最小折数的当且仅当在其广偶图模型的基流向图中， 所有基本圈都不是可规范圈. 定理 2 . 2 . 1 0川卿 的一个纵横扩张城句是最小折数的当且 仅当 在y ( g ) 中 无之字形折， 无可调序列且所有边割都是标准的 根据4 一 正则平面嵌入的性质，得到了它的最小折数纵横扩 张的充要条件: 定理 2 . 3 . 5 4 一 正则p ( g ) 的h ( p g ) 的模型的一个可行解所 对应的纵横扩张是最小折数的当且仅当在其广偶图模型的流向 图中，无对流且所有圈都是规范圈. 定理2 .3 .8 4 一 正则川 句的广偶图模型的 一个基可行解所对 应的纵横扩张是最小折数的当且仅当在其广偶图模型的基流向 图中，所有基本圈都是规范圈， 定理2 .3 .e牛正则p ( g ) 的一个纵横嵌入袱 g ) 是最小 折数的 当 且仅当 在袱 g ) 中， 无之字形折且所有边割都是标准边割 定理2 .3 .8 4 一 正则川 司 的广偶图 棋型的 一个基可行解所对 应的纵横扩张是最小折数的当且仅当在这个纵横扩张中，所有 基本边割都是标准边割. 关于纵横扩张的优化 第三章在线性时间内求出了四类 4 一 正则图的最小折数纵横 扩张，并推广到一般情况 定理 3 . 1 . 4对第一类平面嵌入图有b =v +6，其中b 纵横 扩张的最小折数. 定理 3 . 2 . 2对第二类平面嵌入图有b =。 十5 . 定理 3 . 3 .2对第三类平面嵌入有 b =。 + 4 定理 3 . 4 . 2对第四类平面嵌入有b =。 +5 第四章设计了一个并行算法，求解平面嵌入的最小折数纵 横扩张. 第五章结束语 除非特别声明，本文考虑的是无环，无 1 度点的连通平面 图. 第二章 最小折数纵横扩张 2 . 1 广偶图模型 设g二( v e ) 是一个4 一 平面图， u ( g ) 是它的一个平面嵌人， f 是它的面集，f o 为无限面 对任意的。 e v ， 令d e f ( v ) =4 一 d ( v ) , 称d e f ( v ) 为顶点。 的亏数 4 对任意的f c f ， 令 一4 , f 96 f o 十4 , f二f o 吮 称r e s ( f ) 为面f 的底# (4 1 +二 v iv v e v , d e f ( v ) 0 ) ; e ( 长 一f ) = ( ， ， ， f ) (v v 狡( f ) , v f f j , e * = ( f f i ) iv f i , f ) f , f , a d j f i ) j.百番.1苦、.十， 其中，v + ( f ) 表示v + 中在f 的边界上的点的 集合f ;a d j f j 表示 介与九的边界有公共边 定义2 .1 . 1称h ( t , g ) = ( 叫h ) , e ( h ) ) 为p ( g ) 的广 an ， 其 关于纵棋扩张的优化 v( h ) =v + u f ; e ( h) =e ( v +。f ) ue 了.t.、，. 显然，广偶图是无向图.令 ( f l r e s ( f ) 0 , f e f ) f i r e s ( f ) a f e f , r e s ( f 卜0 s o 知， 在广偶图中， 总发量等于总收量， 可建立供求平衡的广偶图 的运输问题模型如下: h ( y ( g ) ) =rr i川 艺 ( :y +i + y ) ( 六, ! , ) e c - 硕士研究生学位论文加 0 2年 e x ;i =d e f ( v ; ) , 。 : v + ( d ; ,f i ) e e ( v + -f ) r e s ( f i ) , f i f - e 2 u+( y i ， 一y p ) = ( ， f i 卜e ( v + 一 f ) 0 ,几e f o , ( 2 . 1 ) r e s ( f i ) , ! ， f + x ii , y v z + , v ( v九 ) ， ( 人 ， 九 ) e ( h ) 其中z +=和 , 1 , 2 . 如果y ii 。 ， 那么在川 句 的纵横扩张 7 ( g ) 中，f : 和九边界的公共边上有y i， 个折的 方向 是从f 内的 二 / 2 角到九内的3 7r / 2 角 如果y i j 0 ， 那么 在川 句的 纵横扩张 7 ( g ) 中，f : 和f ; 边界的公共边上有y ) ; 个折的方向是从f i 内 的二 / 2 角到 f . 内的 r ;i 。 ， y +i _ 。 ， 因此 3 1r / 2 角由 于v v ; e v + , d e f ( v ;) = 1 或2 ， 且 x ,i = 0 , 1 或2 一 且令 j : : ， =0 t 8=1 几i =2 l x 2 . 2 最小折数纵横扩张判定定理 引理2 . 2 . 1 对于平面嵌入川g ) 的任意一个纵横扩张袱 c ) 存在模型( 2 . 1)的一个可行解与之对应 关于纵横扩张的优化 il明 由1a ( g ) 可建立相应的广偶图x ( i .g ) . 根据- y ( g ) ， 对 x ( p 司上相应的变量赋值 令 0 , a , , t i 1 , a , f i 2 ， a , ，了 ， =二 / 2 二二 汀 =3 x / 2 且y ii =b,， 其中，b ,i 从f : 内的二 / 2 角到几 y . , 0 . 当d e f ( v i ) =1 时， 表示在人 和几边界的公共边上， 折向 是 内 的3 叮 2 角的折的数目 显然，t i ; 之 0 ， 。 处的三个角是二 ， 7r / 2 , ;r / 2 , 则有 当d e f ( v ,) =2 时， 种情况都满足 艺二 。 ( ; , f i 卜e ( v + -. f ) v . 处的两个角是 =d e f ( v ; ) 二 ， 二 ; 或 ir / 2 , a i r / 2 . 易知这两 又二 :， = d e f ( v i ) ( , ; , f i ) e e ( 价 一 f ) 对 d fl 。 f 、在 网 格 嵌 入 电 可 推 知 (，bfi)e 采一 ; 7一 res (fi) . 若在它的边界的某条边上引进一个折，不妨设此折在f ， 内的角 是 叮2 ， 由这种由纵线和横线构成的多边形的性质知，或者是在 某条边上增加一个折， 使其在! i 内的 角是3 7x / 2 ; 或是在i i 内 某 顶点处的角由叮2 增加到二 ; 或者在九内 某顶点处的角由二 增 加 到 3 7r/ 2 则 有 。，)。 爪一 f x ,i- -,f )+ 、，:，霖 : .(y o， 一 y ii) 一 re s (f i ) 对 折数大于一时同 样成立. 总 之，几 ， ， y i， 是模型( 2 功的 一个 可行 解 . 硕士研究生学位论文2 0 0 2年 引理2 . 2 . 2对于一个平面嵌入h ( g ) 的广偶图模型的 一个可 行解， 存在一个 p ( g ) 的纵横扩张与之对应. 证明 在这个可行解中 ， 对任意的y .j , 如果y +j 0 ， 那么在 j : 和寿边界的公共边上增加y +， 个2 度点， 得到一个平面嵌入 川 g 司， 下面构造川 g 司 的网 格扩张 在w ( g w ) 中 ， 根据已 知的 可行解， 把每一个角的 度数标出 ， 选择无限面上一点。 及其上与之关联的边e =( 。 ， ， ) ， 在e 上。 。 处分别标以l , r根据川g 司 中的旋， 在其它与、 关联的边上， 在。 处作标记. 按顺时针方向标记规则如下: l+二 / 2 +2 k 7r =u . l一二 / 2 +2 k ir =d, l+二 +2 k 二 二r ; “+二 / 2 +2 k 7 r =r . u一二 / 2 + 2 k 7 r =l . u+二 +2 k 7r =d ; r+7r / 2 +2 k 7r =d , r一， / 2 + 2 k 7r =u , r+， + 2 k tr =l ; d+7 r / 2 +2 k 7r =l , d一二 / 2 +2 k 7r =r , d+二 +2 k 7r =u 其中，k 是整数.在一条边的两个端点处一个标为l ， 一个标为 r 、 或者一个标为u ， 一 个标为d . 因 为川 g 司是连通的， 所以 可 以得到所有边的走向. 依据标记l , r , 1j , d 把川 g 司的顶点 集分类， 规定， 若一条边 的两个端点分别标记为u , d ， 这两个端点属于同样一类， 且若。 ， 。 都与。属于同 一类， 则。 与， 也属于同一类 这样， 可把p ( g w ) 的顶点集分为若干类， 设为v i , v z ， 一， v 把每一类顶点集作为 一个顶点， 若在川 叫 中存在边。 =( 。 v ) ， 二 任v , v 任v i , e # j , 且。 在。 处的标记为l , 则存在从v , 到v i 的 弧， 这样得到一个 关于纵橄扩张的优化 图，记为 g i . 类似地，规定，若一条边的两个端点分别标记为l , r , 这两 个端点属于同样一类，且若 u ,v 都与 叨属于同一类，则 。与 : 也属于同一类 这样，可把p ( g 司 的顶点集分为若干类， 设为 w ， ， 14 1 2 , ， w ， ， 把每一类顶点集作为一个顶点， 若在 ( g w ) 中 存 在边e =( ?t , v ) 、 任 w , , v 任 w i , , j4， ， 且e 在u 处的标记为d ， 则 存在从哄 到w l 的弧， 这样得到一个图 ， 记为g 2 . 若在g 1 中 仅有一个源， 不妨设为v o ， 令2 ( v o ) = 。 ， 然后求出 从源到其它每一顶点v, , 的 最长有向路-t ( v i) - 否则， 在g ， 中 增加 一个源6 ， 增加从 ， 到其它源的弧 令 s ( s ) 二0 ， 然后求出从源 到其它每一顶点v , 的最长有向路x(v ) 若在 ; 中 仅有一个源， 不妨设为w o ， 令a m) =0 , 然后求 出从源到其它每一顶点w i 的 最长有向 路y ( 叽) . 否则， 在g 2 中 增加一个源s , 增加从s 到其它源的弧 令， ( s ) = 0 ， 然后求出 从源到其它每一顶点w ; 的最长有向 路j ( w i ) 对川 g w ) 中 任意顶点。 ， 令其坐标为( 2 ( 叫， y ( w j ) ) , ” v , , 。 i v ; , 则得p ( g w ) 的网格嵌人 仅保留u ( g ) 中的 顶点， 即 得li ( g ) 的一个纵横扩张. 由于运输间题存在最优解，因此任意4 一 平面图都有最小折 数纵横扩张. 定理 2 . 2 . 3 f t ( p g ) 的模型的一个可行解是非退化的基可行 解当且仅当在这个解的流向图中， 有流向的边构成x ( a g ) 的一 个支撑树. 硕士研究生学位论文2 0 0 2年 证明 由定理 1 .5 . 1 可知. 定义 2 . 2 . 4令 人 一 ( c ) 礼( c ) =n o ( c ) 十。 _ ( c ) 一。 + ( c ) =n o ( c ) +n + ( c ) 一， 、 一 ( c ) 其中，。 十 ( c ) 。 一 c ) 和 。 o ( c ) 分别表示圈c中与顺时针方向一 致的弧数， 与逆时针方向一致的弧数和空白边数. 若在圈c中， a _ ( c ) 0 , a + ( c ) 0 ， 则称c为规范圈 . 否 则， 是柞 沈范圈 、 不 满足规范圈的方向 称为可调方向 在非规范圈上， 若含有v + 中 的点，则在可调方向上必含以此点为起点的非。 一 流弧，称这样 的非规范圈为可况范圈 那些不含v + 中的点的非规范圈属于可 规范圈甲 定理 2 . 2 . 5一个平面嵌入的纵横扩张是最小折数的当且仅 当在其广偶图模型的流向图中，无对流且无可规范圈. 证明 对于任意给定的平面嵌人p ( g ) , 设h ( a g ) 是它的广偶 图， 令c ( e ) 表示e 边上的费用由 于对任意( v , f ) f ( v + 一 f ) .c ( ( v , f ) ) = 0对任意 ( 9 , f ) e , c ( ( 9 , f ) ) =1 . 且在h ( m g ) 的每 一个圈中都含有偶数条 e ( v + 一 f ) 中的边且不影响规范性 因此， 每一个规范圈都是正规圈. 可规范圈保证了调整后解的可 行性，再由定理1 .5 .2 即得此结论. 定理2 . 2 .6 p ( g ) 的川p 伪模型的 一个基可行解所对应的纵 横扩张是最小折数的当且仅当在其广偶图模型的基流向图中， 关于纵横扩张的优化 所有基本圈都不是可规范圈. 证明 由定理 1 .5 . 3 及2 .2 .5 可得. 在h 协 句中， 如果某个圈c是可规范的， 不妨设， 顺时针 方向的弧数大于其它弧与边的数目 和. 令。 是顺时针方向弧中 流量的最小值，令顺时针方向弧的流量都减去 。 ，其它的弧和 边对应流量都加上。 ，那么，c可调整为规范圈. 定义2 . 2 . 7在川 句的纵横扩张洲句中， 设。 在面f . 和九 的公共 边界 上， 如果e 上既有折向为从了 . 内 的叮 2 角 到f ， 内的 3 叮 2 角的 折，又有折向为从人内的3 叮2 角到九内的叮 n 角的 折，则称 。 为之字型折 若已知 。 是之字形折，且在折处的角中有 d 个 刁2 角在 f 内， 有。个rr / 2 角在几内， 不妨设，l 。 ， 则已 边上的折可减 少为d 一。个. 定义2 . 2 . 8设。 l e 2 e 3 . . . e 。 是袱 句 的一个边割， 其中 。 : 和 e , + 1 在 f + + 1 的边界上， 如果。 ， 上有折，且折处在f ， 内的角都是 7r / 2 ， 那么 称。 : 为正向 边; 若折处在人内 的角 都是3 7r / 2 ， 那么 称 。 ， 为 负向边 如果在一个边割中，正向边的数目 不大于负向 边与无折边数目的和，称为标准边刻. 已知。 l e 2 e 3 一。 。 是非标准边割， 设t 是正向边上折数的最小 值， 令正向边上的折数都减去t ， 其它边上的折数都加上l ， 可调 整为标准边割. 定 义2 .2 .9 设 序 列。 = 几 ， v i 禹: ， f l ， ， f ;， 一， f ;. , u k , f lk + r ， 一 硕士研究生学位论文2 0 0 ?年 若: : 在 九 内的角皆大于叮2 ， 且负向边的个数超过其它边的数 目，则称 q为可调序列. 已 知q为可调序列， 设l 是。 : 在九 、 内的角所对应变量与负 向边上的折数中的最小值， 令。 . 在九 内的角所对应变量与负向 边上的折数都减去 l ， 其它边上的折数都加上l ， 则序列变为不可 调的. 定理2 .2 . 1 0川 句的一个纵横扩张-y ( g ) 是最小折数的当且 仅当在-y ( g ) 中 无之字形折，