（基础数学专业论文）图的双极定向及其算法.pdf

北京交通大学硕士学位论文中文摘要 中文摘要 摘要：双极定向在v l s i 设计及其它工程计算中都有着广泛的应用，同时也是 许多画图算法的基础，因而近年来越来越受到人们的重视，得到了广泛而深 入的研究。 双极定向的概念最早南b r o o k s ，t u t t e 等人在1 9 4 0 年提出，当时讨论的是，j 个纯数学的问题，1 9 6 7 年，a l e m p e l 及s e v e n 等人在一篇关于平面检测的文章 中提出了双极标数的概念。e v e n 和t a r j a n 在1 9 7 6 年给出了计算无向连通图的双 极标数的线性算法。从此，双极定向被广泛地应用在v l s i 设计及图的可视性 表示、正交画图等画图算法中。 本文在分析了图的基本圈的结构的基础上，提出了两种基本构型。通过 对这两种构型的优化，给出了一个图的双极定向的算法。全文共分四章： 第一章介绍了一些基本概念及其相关背景。 第二章介绍了两种双极定向的基本算法，并对算法进行了改进，给出了 具体的算例。 第三章利用吸收规则，分析了图的圈的结构，构造了图的双极定向的新 算法，并对算法进行了简单分析。 第四章提供了一些需要进一步研究的问题。 关键词：双极定向；双极标数；吸收规则 分类号：0 1 5 7 5 北京交通大学硕士学位论文 a b s t r a c t a b s t a c t ：b i p o l a ro r i e n t a t i o n sn o to n l yh a v eaw i d er a n g eo fa p p l i c a t i o n si nv l s i d e s i g na n do t h e re n g i n e e r i n gc a l c u l a t i o n s ，b u ta l s ot h eb a s i so fm a n yd r a w i n ga l g o r i t h m s s om o r ea t t e n t i o nh a sb e e np a i di nr e c e n ty e a r s t h e c o n c e p to fb i p o l a ro r i e n t a t i o nw a sf i r s ti n t r o d u c e db yb r o o k s ，s m i t h ，s t o n ea n d t u t t e ，a sap u r e l ym a t h e m a t i c a lt r e a t m e n ti n1 9 4 0 i n1 9 6 7 ，a l e m p e la n ds e v e np r o p o s e dt h ec o n c e p to fs t n u m b e r i n g si na na r t i c l ea b o u tp l a n a r i t yt e s t i n g i n19 7 6e v e n a n dt a r j a np r o p o s e da na l g o r i t h mt h a tc o m p u t e sa ns t - n u m b e r i n go fa nu n d i r e c t e db i c o n n e c t e dg r a p hi nl i n e a rt i m e s i n c et h e n ，t h eb i p o l a ro r i e n t a t i o nw a sw i d e l yu s e di n v l s id e s i g na n dg r a p hd r a w i n ga l g o r i t h m ss u c ha sv i s i b i l i t yr e p r e s e n t a t i o n s ，h i e r a r c h i c a ld r a w i n g sa n do r t h o g o n a ld r a w i n g s b a s e do nt h ea n a l y s i so ft h ef u n d a m e n t a lc i r c u i to fag r a p h ，t h i st h e s i ss h o w st w o b a s i cc o n f i g u r a t i o n so fac i r c u i t b yt h eo p t i m i z a t i o no ft h e s et w oc o n f i g u r a t i o n s ，a n a l g o r i t h mo ft h eb i p o l a ro r i e n t a t i o ni sg i v e n t h e r ea r ef o u rc 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 dt h e i rb a c k g r o u n d t h es e c o n dc h a p t e rs h o w st w oa l g o r i t h m so ft h eb i p o l a ro r i e n t a t i o n ，a n dg i v e sa s p e c i f i ce x a m p l ee a c h i nt h et h i r dc h a p t e r , w ea n a l y z e dt h ef u n d a m e n t a lc i r c u i to fag r a p ha c c o r d i n gt o t h ea b s o r p t i o nr u l es h o w ni n 3 , 4 1 ，a n dp r o p o s e dan e wa l g o r i t h mo ft h eb i p o l a ro r i e n t a t i o n t h 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 ft h ew h o l ea r t i c l ea n dl i s ts o m ep r o b l e m n e e df u r t h e rs t u d y k e y w o r d s ：b i p o l a ro r i e n t a t i o n s ；s t - n u m b e r i n g s ；a b s o r p t i o nr u l e c l a s s n o ：0 1 5 7 5 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。 特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：导师签名： 签字日期：年月日 签字日期：o9年月多日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成 果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研 究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书而使用过的材料 与我+ 。同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。 学位论文作者签名：签字日期：年月日 致谢 本论文的工作是在我的导师刘彦佩教授的悉心指导下完成的，刘彦佩教 授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感 谢两年来刘老师对我的关心和指导。 刘彦佩教授悉心指导我们完成了科研工作，在学习上和生活上都给予了 我很大的关心和帮助，在此向刘老师表示衷心的谢意。 郝荣霞老师对于我的科研工作和论文都提出了许多的宝贵意见，在此表 示衷心的感谢。 在实验室工作及撰写论文期间，张建根等同学对我论文中的研究工作给 予了热情帮助，在此向他们表达我的感激之情。 另外也感谢北京交通大学理学院的各位老师，他们在两年里给了我非常 多的帮助使我能够专心完成我的学业。 北京交通大学硕士学位论文 第1 章引言与综述 1 1 研究现状 第1 章引言与综述 给定一个无向图g = ( v e ) ，若给其每一边定向，使其只有一个源， 即所有的边为发出边，和只有一个汇，即所有边为进入边，且得到的图中 没有有向圈，这样的定向叫做双极定向。双极定向在图论中有很多重要 的应用，许多图论算法，如分层画图 i h ( h i e r a r c h i c a ld r a w i n g ) ，可视性表 示 9 1 ( v i s i b i l i t yr e p r e s e n t a t i o n ) 及正交绘图u o ) ( o r t h o g o n a ld r a w i n g ) 等都是以双 极定向为基础的。 双极定向的概念最早由b r o o k s ，t u t t e 等人在1 9 4 0 年提出【1 2 】，当时讨论的是 一个纯数学的问题，然而，这已经提出了导致其后几十年至今仍富有活力的 图论，及其运筹学中一些重要的课题。 1 9 6 7 年，a l e m p e l 及s e v e n 等人提出了双极标数的概念【1 5 】。并证明了给定 一个连通图的任两个极点，就可以得到它的一个双极标数，且设计了时间复 杂度为o ( m n ) 的递归算法。e v e n 和t a r j a n 在1 9 7 6 年提出了在o ( m + 疗) 次内得到 连通无向图的双极标数的算法 6 1 ，e b e r t 在这个基础卜进行了一些简化【1 6 1 ，随 后t a r j a n 又对此作了进一步的改进【1 8 】。1 9 8 6 年t a r j a n 在对平面图的情况提出了 一个线性算法【1 9 】，该算法可以得到一个平面图的双极定向。 刘彦佩教授在研究图的纵横嵌入过程中也对双极定向提出了新的研究 思路，1 9 9 4 年提出吸收规则的构造方法【2 1 ，在1 9 9 8 年又对这一方法进行了改 进【4 】。 在以后的研究中，对双极定向的内部特性的研究，比如最长路径等，越 来越引起人们的重视。2 0 0 5 年，c p a p a m a n t h o u 和i g t o l l i s 提出了一种参数化的 双极定向算法【1 3 1 ，该算法的复杂度也为o ( m n ) 。 1 2 基本概念 在数学上，一个图常记为g = ( v e ) ，是e h - - 集合y 和e 所组成的使得其 中e 是由所有y 中元素对形成的集合的一个子集。y 和e 分别称为g 的顶点 集和边集，它们的元素分别称为g 的顶点和边。 北京交通大学硕士学位论文第1 章引言与综述 如果允许y 中的一个元素与它本身组成一对，且e 中有这样的元素，称 这种边为环边，称这样的图为带环图。 若e 中之元素允许重复出现，则这种重复出现的边称为重边。具有重边 的图称为带重图。既无重边又无环的图，称为简单图。 设v = ，l ，v 2 ，则v 的基数i v l = n 称为g 的阶。这里，我们只研 究n 为有限的自然数，或者说是有限图的情况。因此，l e l _ m 也是有限的， 称m 为g 的度。 用( v i ，v j ) 表示顶点v i 与v ，之间有一条边，这时，称它们是相邻的。而 称，v i 或v j 与这条边( v i ，v j e ) 是关联的。有时，为方便，常想象每条 边( v i ，v j ) e 是由两条半边( v i ，v j ) 和 而 不与半边( v i ，v j ) 关联。与一个节点关联的边的数目称为这个顶点的次，记 为d ( v ) 。如果一个图的所有顶点的次都相同( 设为d ( v ) = k ) ，则称它为正则 的( 露一正则的) 。 用s 表示图的边的数目，显然有烈v ) = 殄。在图中的一个顶点和边的 序列v o e o v l e l y l l e f - l 使得v i kf = 0 ，1 ，f e e ，j = o ，1 ，z l 并且 满足e j = ( v ，v j + 1 ) ，j = 0 ，1 ，f 一1 则称它为v o 和的一个途径。 如果在一个途径中没有重复出现的边，则称为路。如这个序列中v o = l y l ， 则称为闭的。称闭径为环游，闭路称为圈。 若一个图g = ( v e ) 的任何两个项点都有g 中的一条路连接，则称g 是连 通的 因为“两个顶点间有一条路连接”，或“两顶点是连通的”确定顶点集上的 一个等价关系。则在此等价关系下被分划为v = + 坎+ k ，并且遂产 生e 的一个划分e = e l + e 2 + e ，使得g f - ( ，蜀) ，1si s 为g 的子 图。这时g j ，1 fss 被称为g 的连通片或连通分支。 如果图g = ( ve ) 的一个顶点l ，v 具有这样的性质：在g 中将l ，和与 它关联的边去掉所得子图即g l ，的连通片数比g 的至少多一个，则l ，被称 为g 的一个割点。 如果图g = ( ve ) 的一条边e e 具有这样的性质：在g 中将e 和与它 关联的顶点去掉所得子图即g e 的连通片数比g 的至少多一个，则e 被称 为g 的一个割边。 若给定图g = ( v ) 的每一条边e = ( u ，) e 以一个方向，如从u 到v 或 从l ，到u 分别记为( u ， ，) 或( ，口 ，则所得的图被称为有向图。e = ， ，) ivu ，v e l 称为弧集。 一个连通且无圈的图，称为树，记为丁。如果图g = ( ve ) 的一个子 2 北京交通大学硕士学位论文第1 章引言与综述 图丁是树而且它的节点集v ( t ) = t 则称r 为g 的一个支撑树。同时，一t = ( v e e ( r ) ) 称为g 的一个上树。 因为e = ( u ，v ) e e ( t ) = e ( t ) 在g 上有且仅有一条连u 和v 的路，从 而e 与丁形成恰好一个圈。这个圈被称为g 对于r 的一个基本圈。 一个边的子集s e ，如果从g 中将s 中的边去掉即得g s = ( v e s ) 的 连通片数比g 的多并且s 的任何子集均不再有此性质，则称s 是g 的一个上 圈。 因为一个图g 有一个支撑树丁当且仅当g 是连通的，和从巾去掉任意一 条边均使丁剩下的部分由两个连通片组成，则丁的任一边e 与亍中的边形成 恰好一个上圈，称这个上圈为g 对于r 的基本e 圈。 图g 的基本圈和基本上圈的数目与丁的选择无关。 令丁( ve ) 是图g 的以t 为根的树，对于任意的点u ， ，v ，记l c a ( u ， ，) 为 r 中u 和v 的最近的共同祖先。若e = ( u ，v ) 是一条非树边，且l c a ( e ) = ，。 则由e 和r 构成的基本圈为从f 到“的一条路，接下来是e 和从v 到z 的一 条路。令( z ，a ) 是路z 到u 的第一条边，( f b ) 是路z 到v 的第一条边( 这两 条边中有可能有一条不存在) ，称( z ，a ) 和( f ，b ) 是e 的基本圈的基边，相应 的a 和b 称为e 的基本圈的基点。 若一个图是具有这样的一个图形，它的边仅在顶点处相交，则该图称为 平面图。如果一个图能画在平面上使得它的代表边的曲线仅在端点相交，则 称这个图为可嵌入平面的，或称平面图。平面图g 的这样一种画法称为g 的 一个平面嵌入，记为i z ( g ) 。 所有顶点度不大于k 的可平面图，称为k 一平面图。 一个平面图，把平面分成若干个连通的区域，这些区域的闭包称为g 的 面，记为厂其中，唯一一个无界面称为无限面，记为尼。 用6 ( 厂) 表示平面图g 中面厂的周界。若g 是连通的，则可以认为是一条 闭途径，g 在易( d 中的每条割边都被这条途径经过两次；当6 不包含割边 时，这条途径是g 的一个圈。 称面，与它的周界上的项点和边是关联的。称一条边分隔和它关联的面。 面，的度d 是指和它关联的边的条数( 即d 中边的条数) ，其中割边被 计算两次。 假如图g 的一个嵌入g ( g ) 中所有的边均用由水平或竖直线段组成的折线 段表示，则称它为g 的纵横嵌入。每条边无折的嵌入称为网格嵌入。如果平 面上的一个网格，仅由两个平行线族所组成，则称它为仿射网。相似的，如 果两组平行线是相互垂直的，则称它为一个纵横网。 3 北京交通大学硕士学位论文第1 章引言与综述 如果g 本身就是一个平面嵌入，则当它的一个与g 拓扑等价的纵横嵌入 满足条件：纵横嵌入的无限面与g 的无限面相对应，则称此纵横嵌入为g 的 一个纵横扩张，记为y ( g ) 。 在一条折线上，纵线段与横线段的交汇处，称为一个折；总折数达到最 小的纵横扩张称为最小折数纵横扩张。每条边上均无折的纵横扩张称为网格 扩张。 称节点次不大于4 的图为常规的。 4 北京交通大学硕士学位论文第2 章图的双极定向及现有算法 第2 章图的双极定向及现有算法 给定一个连通的无向图g = ( ke ) ，设其有n 个节点，m 条边，给图的一 个定向满足如下两个条件： ( 1 ) 有一个源且只有个汇； ( 2 ) 该定向中没有有向圈。 这种给图g 的边定向的方式叫做双极定向( 见图2 1 ) 。 图2 1 ：图的双极定向 一个图g = ( ve ) 的双极标数即给图的所有节点标数使其满足： ( 1 ) 源j 标为g ( s ) = 1 ，汇t 标为g ( r ) = 以； ( 2 ) 对vl ，v 一 j ，n ，存在两条边v ) 和似y ) ，使得g ( 力 g ( d g ( ) ，) 。 容易证明，图g 的双极定向和双极标数是等价的。实际上，对于双极向 总可以按如下过程对其节点标数： 首先，将源s 标为l 和将汇t 标为_ r l 。然后，按 标数规则假若l ，2 ，ll f 厂( 1 ，) ，即u 是v 的孩子。若u 和y 之 间存在一条由树边组成的路( 有可能为空的) ，则记为vw 口对d f s 树的每 条非树边( “， ，) ，有如下关系成立 l ql ，营uw ，i ，w “ ( 2 1 1 ) 我们已知，d f s 生成一个支撑子树，且给原图的每一个顶点指定一个唯一的 值厂( 1 ，) ，这些值在双极标数中是非常重要的。对vx v ，定义其低值为 l o w ( x ) = m i n ( f ( x ) u f ( y ) 1 3 w ，石wwawq 纠)( 2 1 2 ) 对任一给定的节点，有可能出现两个节点的低值相同的情况。从( 2 2 ) 式可以 看出，节点x 的低值或者是其d f s 值八x ) 或者是在d f s 遍历中先于x 被访问到 的节点y 的d f s 值，( ) ，) ，x 和y 点的关系可以如图2 所示 图2 2 ：x 和y 有相同的低值 由以上的定义，可以得到如下引理 6 p k - 11上tj ， ， ，、，：一 北京交通大学硕士学位论文 第2 章图的双极定向及现有算法 定理2 1 1 如果图g 是连通的且 ，- w ，若八d l ，则l o w ( w ) 八d ；若八1 ，) = 1 ，则l o w ( w ) = 八d = 1 证明：对于第一种情况，当厂( v ) 1 时，令c 是d f s 树中在 ，前面的一 点，即厂( c ) 厂( 1 ，) 因为该图是双连通的，从w 到c 必有一条不包含 ，的路， 且该路结束于一条终点为c 的非树边。故c 可以从w 经过一条非树边到达， 由定义知l o w ( w ) = f ( c ) ，又因f ( c ) f ( w ) ，故有l o w ( w ) f ( v ) 。 对于第二种情况，在d f s 数的标数中没有比1 小的节点，故若f ( v ) = l ， 且v _ w ，则必有l o w ( w ) = f ( v ) = l 。 图g 中所有节点的l o w ( v ) 的值可以在o ( m + ，1 ) 次时间内得到。接下来就 可以开始计算图的双极定向给定一个无向连通图g = ( k e ) ，令( s ，f ) 是其中 的一条边。首先，执行d f s ，使得d f s 树的根为t ，且第一条边为t s ，同 时，计算每一个节点，的低值l o w ( v ) 。这一步是下面步骤的基础。 算法最重要的部分是，对于一个节点v ，返回v 到不同节点w 的路。初 始，我们把图中节点j 和t 及边( s ，力标为已用过，此外所有的节点和边标为 新的。每一次调用p a t h ( v ) 都返回一条由新边组成的路，再把这条路中包含的节 点和边标为已用过。求鳓以嘶v j 的算法由以下给出。 算法2 1 p a t h f i n d e r ( v ) 1 ：i f ，qw 以n e ww i t hwwvt h e n 2 ：m a r k ( v ，w ) a so l d ； 3 ：p = v ，w l ； 4 ：e l s ei f3 v - w 阢n e wt h e n 5 ：m a r k ( _ l ，们a so l d ； 6 ：p = f uw ； 7 ：w h i l e wn e w d o 8 ：f i n dn e w ( w ，x ) w i t h 叭曲= l o w ( w ) i ( 1 0 w ( x ) = l o w ( w ) aw _ 曲) ； 9 ：m a r kwa n d ( w ) a so l d ； 1 0 ：p = pu ( w ，曲； 1 1 ：w = 工： 12 ：e n dw h i l e 1 3 ：e l s ei f vqw t i cn e ww i t hvwwt h e n 1 4 ：m a r k ( ，w ) a so l d ； 7 北京交通大学硕士学位论文第2 章图的双极定向及现有算法 1 5 ：p = ，w ； 1 6 ：w h i l e wn e w d o 1 7 ：f i n dn e w ( w ，曲w i t hx w ； 1 8 ：m a r kwa n d ( ，峨曲a so l d ； 1 9 ：p = pu ( 鹕曲； 2 0 ：w = x ： 2 1 ：e n dw h i l e 2 2 ：e l s e 2 3 ：p = 0 ； 2 4 ：e n d i f 2 5 ：r e t u r n p 在执彳t p a t h ( v ) 的过程中，或者生成一条由v 点指向其他节点w 的边组成的 路，或者返回一条空路。当p a t h ( v ) 被调用，却返回一条空路时，没有其他的边 从 ，点发出，此时最后的i f 部分被执行。 上面已经提到，p a t h ( v ) 是被算法主体调用中的一步。主算法中用栈来 存储已用过的节点初始设置栈中包含j 和t 两点，且s 在t 的上面。 栈顶的节点，不妨称之为 ，被取出且调用p a t h ( v ) ，如；果p a t h ( v ) 返回一条 路p = ，l ，v 2 1 ， v 3 ，v 4 ，i v k _ i ，v k ，则把收- l ，墩- 2 ，v 2 ，v l 依次压入栈中，这里 的y = v l ，且节点收不入栈。当返回牢路时，把v 标为下一个町用的数字，且 不再放回到栈中 计算双极定向的主算法利用p a t h f i n e r ( v ) 来计算双极定向算法步骤如下： 算法2 2 s t n u m b e r ( g ，只d 1 ：c o m p u t et h el o w p o i n t sl o w ( v ) f o ra l ln o d e sv ； 2 ：m a r ks ，ta n d ( s ，t ) a so l da n da l lo t h e rv e r t i c e sa n de d g e sa sn e w ； 3 ：i n i t i a l i z eas t a c kr ： 4 ：r = p u s h ( t ) ； 5 ：r = p u s h ( s ) ； 6 ：f = 0 ： 7 ：w h i l er 0d o 8 ： ，= p o p ( r ) 8 北京交通大学硕士学位论文 第2 章图的双极定向及现有算法 9 ：p = v l ，v 2 ， v 3 ，v 4 ，f l ，v , = p a t h f i n d e r ( v ) ； 1 0 ：i f p 0t h e n 1 1 ：f o rj = k ld o w n t old o 1 2 ：r = p u s h ( v j ) ； 1 3 ：e n d f o r ： 1 4 ：e l s e 1 5 ：f = i + l ： 1 6 ：g ( v ) = f ； 1 7 ：e n di f 1 8 ：e n dw h i l e 下面，证明该算法最终得到一个双极标数。 定理2 1 2 算法s t n u m b e r 给图的定向过程得到的恰是图g = ( v e ) 的双极 标数。 证明：节点v 在栈中同一时间不能出现在小同的地方，一旦 ，入栈，只 有y 标号以后1 ，下面的节点才能被标号，故该算法给图的节点的标数是有序 的。又，顶点x 只有： e p a t h ( x ) 返刚为空时才被标号，此时与x 相关联的所有边 都被标记为已用过，这就保证了图中所有的边都被访问过。 首先，显然j 的标号为l ，因为s 总是在堆栈的顶端，直到所有像( 5 ，w ) 这 样的边都被标记过，此时，p a t h ( s ) 返回为空，且s 第一个被从栈中永久删 除，故其标号为i 。在栈中相邻的节点在图中也是相邻的，则j 的某个邻接 点，不妨记为r ，取代j 留在栈项，直到所有从厂发出的边被标记为已用过。 由于在，之前除s 外没有其他点被标号，故r 被标为2 。这个过程一直继续下 去，直到节点t 最后被标为n 。标号的过程保证了对于所有的节点y 文t 至 少与一个标号小于自己的节点和一个标号大于自己的节点相邻。 综上所述，该标数过程得到的是是图g = ( ke ) 的双极标数。 该算法的运行时间复杂度为o ( m + n ) ，主要是深度优先搜索遍历的时 间和主算法本身的时间。主算法本身耗费的时间主要由p a t h f i n d e r ( v ) 来决 定，p a t h f i n d e r ( v ) 执行的时间与所找到的路中的边的数目一致。又因每条边只 出现在一条路中，t 攻p a t h f i n d e r ( v ) 耗时为o ( m + n ) t 1 7 1 ，则该算法的时间复杂度 为o ( m - i - n ) 。 9 北京交通大学硕士学位论文 第2 章图的双极定向及现有算法 2 1 2 一个例子 下面，我们给出t a r j a n e v e n 算法的一个例子，如图2 3 所示 图2 3 ：图g 及其d f s 树 我们计算其2 1 定向，首先生成其d f s 树，并计算每个节点的低值( 图2 3 ) ， 算法的执行过程见下表： 步骤栈路结果 l 1 1 ，2 2 3 _ 5 9 _ 1 2 1 , 9 ，5 ，3 ，2 2 _ 4 3 1 , 9 ，5 ，3 ，4 ，2 n u l l g ( 2 ) = l 4 1 , 9 ，5 ，3 ，4 l n u l l g ( 4 ) = 2 5 1 , 9 ，5 ，3 3 _ 8 _ 7 _ 6 _ 5 6 1 , 9 ，5 ，6 ，7 ，8 ，3 l n i h i ， g ( 3 ) = 3 1 7 1 ，9 ，1 0 1 0 - 9 1 8 1 ，9 ，1 0 l 1 0 _ l 1 9 1 1 , 9 ，1 0 l n u l l g ( 1 0 ) = 8 2 0 1 , 9 9 _ l 2 l 1 , 9 i n u l l g ( 9 ) = 9 2 2 l n u l l g ( 1 ) = 1 0 由表中可知，最终得到的图g 的2 1 标数为 9 2 1 = 【1 0 ，1 ，3 ，2 ，7 ，6 ，5 ，4 ，9 ，8 】 1 0 北京交通大学硕士学位论文第2 章图的双极定向及现有算法 2 2s 1 n ：法 上面给介绍的是用双极标数的方法给图定向的算法，下面我们给出一个 给图直接定向的算法为了描述此算法，给出如下定义。 对一个图g = ( ve ) ，记g ( y ) 是节点v 的邻居的集合，s 是图的源，t 是 图的汇。若图g 是单连通的，可设g 包含一个块集召和割点集c ，则割点块树 定义为t = ( 口uc ，该树有例+ i c l 个节点，例+ i c i - l 条边，如图2 4 所示。 在这个定义中，割点块树是一棵无根树，我们可以定义其根为t ，如果t 在块 中，则把含有t 的那个块作为根。最后，称割点块树中除了根以外的，由唯一 的一个割点定义的块为叶块，即叶块只包含一个割点。与d f s 树相仿，割点块 树可以用递归的方法在o ( m + n ) 的时间内得到。 图2 4 ：1 连通图和它的以风为根的割点块树 定理2 2 1令g = ( ke ) 是有咒个节点的不可分离图，s 和t 是它的两个 节点。如果删去s 及其相邻的边，则至少有一个j 的邻居在割点块图的一个叶 块中，且该点不是割点 证明：如果g 一还是不可分离的，则定理显然成立此时，根为t 的割 点块树只包含一个独立的点，它既是割点块树的根又是割点块图的叶块。 如果g 一 j 是单连通的，设割点c 定义了割点块树的一个叶块f ， 且( s ) nf = 0 。若删除c 以后g 不再是连通的，则g 本身就是不可分离的， 这与题意矛盾。如果v ( s ) nf = c ，结果仍与上面相同，所以，至少有一 个s 的邻居在割点块图的一个叶块中，且该点不是割点。 北京交通大学硕士学位论文 第2 章图的双极定向及现有算法 定理2 2 1 是这个算法的基础，我们称这个算法为s t n 法。给定不可分离 图g = ( v e ) ，求其双极定向首先，取该图的割点块树的根为t 或者是包 含t 的块，对割点块树中的叶块，递归的删去其中的点，直到碰到t 为止。 我们递归的生成图g i 1 = g f l ，i = l ，2 ，n ，g l = g 令n = s ，在此 过程中，持续更新根为t 的割点块树。此外，我们维持一个结构q 来决定下 一个点的选择，首先令q 包含图g 的源s 。选择v i 满足 v i 磷nq 一磷，i = 1 ，2 ，n 一1 ( 2 2 1 ) 其中群是第i 次迭代中的第f 个叶块，h ；是定义研的那个割点。当一个v i 被 从图中删除时，为了选择下一个源，按如下方式来更新q q = at 3 盹。( v i ) 一t ) 一 v i ，i = 1 ，2 ，n 一1 ( 2 2 2 ) 该过程一直继续下去，直到q 为空。令f = ( v 7 ，e 7 ) 是由以上过程得到的 有向图，其中 ，一j e = lj ( n ，( v j ) ) ( 2 2 3 ) 罱 则最后得到的图f 就是一个双极定向。证明方法见文献 1 4 】。 下面给出该算法的伪代码： 算法3s t n ( g ，s ，d l ：a = f s ； 2 ：i = 0 ： 3 ：i n i t i a l i z ef = ( 矿，e 7 ) t ob et h ef i n a ld i r e c t e dg r a p h ； 4 ：i n i t i a l i z et h eb l o c k - c u t p o i n tt r e ett ob eg r a p hg ；i t sc u t p o i n ti ss i n kt ； 5 ：w h i l eq 0d o 6 ：f o ra l ll e a f - b l o c k s 磷d o 7 ：f = f + 1 ： 8 ：f i n d ，f b e n 一 j l f l 9 ： g ( v e ) = f ： 1 0 ：v = v 一 比 1 1 ：矿= 矿ui 比j 1 2 ：f o ra l le d g e s ( d e d o 1 3 ： e = e 一 ( v e ，0 1 2 北京交通大学硕士学位论文第2 章图的双极定向及现有算法 1 4 ：f = fu ( r e ，d 1 5 ：e n d f o r 1 6 ：q = quf n ( v e ) 一t 一1 w 1 7 ：e n d f o r l8 ：r ( f ，钟1 ，磋2 ，辟7 ) = u p d a t e b l o c k s ( g ) 1 9 ：e n dw h i l e 2 0 ：r e t u r n 只g ； o “ 0q 一 絮疽 鳟；辛 占。 澎? 澎甲矿工一。 图2 5 ：s t n 的执行过程 1 3 鑫冀糍。 一膨 北京交通大学硕士学位论文 第2 章图的双极定向及现有算法 定理2 2 2 算法s t n 可以在o ( m n ) 时间内实现。 证明：在算法执行过程中，有行一1 个节点被删除，每一次迭代的耗时主要 在更新割点块树上，为o ( m + n ) 故整个算法可以在铆一1 ) o ( m + n ) = o ( m n ) 时 间内实现。 图2 5 是该算法执行的一个例子。这个算法允许我们控制所得图的某些参 数特性，比如每次新点的选择，对于最后得到的双极定向的最长路是极其重 要的。 北京交通大学硕士学位论文第3 章吸收规则法 3 1吸收规则 第3 章吸收规则法 图g = ( k e ) 有割点，可以将它的每一个不町分离块作为节点，我们称将 一个图的块和割点作为节点，而将割点与块之间的关联定为边，得到的图称 为割点一块图。 定理3 1 1 一个图g = ( ke ) 是双极可定向的，当且仅当它的割点一块 图b ( g ) 本身是一条路。 证明：首先，一个图g = ( k e ) 的割点块图显然是一棵树。若这个图是不 可分离的，则它本身就是一个块，其源和汇可以视为割点，则源和汇及块所 对应的点，形成一棵树，且该树恰是一条路。若图g 是1 连通的，设其割点 块图g 是一棵树，若图g 有双极定向，则g 中只能有2 个度为1 的点，此时 树g 7 为一条路。 反之，若图g 的割点块图g 7 是一条路，可以取这条路的一端为源一端为 汇，把这条路定为有向路。对于每一个块，在路上有两个割点与其关联，规 定其内部边的方向都与有向路的方向相同。这样得到的定向恰有一个源和一 个汇，且没有有向圈，即为g 的双极定向。 假若一个图有双极定向，且可以使其中双极定向的源和汇是相邻的，则 称它是邻极的。相应的，这样的一种定向被称为邻极定向。 定理3 1 2 一个图g = ( v d 是邻极的，当且仅当它没有割点，或者说是 不可分离的。 由这两个定理，可以只研究邻极定向而不失一般性。因为若否，总可以 从b ( g ) 的一端所相应的g 的那一块开始任选一个节点，但不能是g 的割点， 作为源。并引进一条从此源到次块上那个割点的边。在此带一新边的块上， 求一个邻极定向，使得那个割点为汇。然后，以此汇为源，对与它关联的那 个未定向的块作为同样处理，并求得一个邻极定向。直到相应b ( g ) 另一端的 块。在其上任取一点为汇，用同样的处理方法，而得到它的一个邻极定向， 这样只要将那些附加的边去掉即可得到g 的一个双极定向。 1 5 北京交通大学硕士学位论文 第3 章吸收规则法 下面，就介绍一种以任一条边两个端点作为源和汇，在一个不可分离图 上，求一个邻极定向的方法 首先，将这条选定的边规定为从源到汇的方向，并且，标注此两节点已 用过，然后，用 吸收规则对任何一个已经用过的节点“，设存在一条无内点为用过节点 的路p ( u ，l ，) 剑用过节点 ，若在已用过节点的导出子图中，有一条有向路是 从u 到l ，则将p ( u ， ，) 上所有边均规定为从u 到v 的方向。否则，即不存在 从u 到l ，的有向路，则在e ( u ，v ) 上任选“到v 或v 到u 的方向以规定其上边的 方向。 直到不能进行为止。 由于在这个过程中，只要有一条边未规定方向，则必然存在一个p ( u ，l ，) 含 此边且e ( u ，) 上仅“和 ，是已用过的节点。到过程不能进行时，g 的每一条 边均规定了方向。再则，容易看出，在这种边的定向中，在g 上不会出现有 向圈。而且，它只有一个源和一个汇。由过程之初，可知此源和此汇是相邻 的。从而，根据吸收规则所得的图g 是邻极定向的。 3 2 两种圈的结构 吸收规则的关键是如何选取一条无内点为用过节点的路p ( u ，y ) ，且 当u 和v 之间有多于两条路时，避免给这些路定向时出现有向圈。在一个 图g 中，若两节点u 和1 ，之间有两条不同的路，这两条路恰构成一个圈。考 虑到图g 的一个树丁和每一条非树边都构成一个圈，我们主要分析树和非树 边的关系。 令丁( ve ) 是图g 的以t 为根的树，对于任意的点u ， ，v ，l c a ( u ，们是丁 中h 和，的最近的共同祖先。若e = ( “，订是一条非树边，且l c a ( e ) = z 则由e 和丁构成的基本圈为从z 到u 的一条路，接下来是e 和从 ，到z 的一 条路。令( f ，a ) 是路z 到“的第一条边，( z ，b ) 是路，到y 的第一条边( 这两 条边中有可能有一条不存在) ，称( 厶口) 和( l b ) 是e 的基本圈的基边，相应 的a 和b 称为e 的基本圈的基点。 对每一条非树边e ，均有和树r 构成的一个圈，我们可以很容易的给 这个圈定向使之不是一个有向圈。然而，一条边有可能出现在几个圈中， 当有多于两条的非树边的最近的共同祖先相同时，有可能出现有向圈。 此时，有两种情况设非树边x 和y 的最近的共同祖先相同，不妨设其 1 6 北京交通大学硕士学位论文第3 章吸收规则法 为l c a ( x ) = l c a ( y ) = z ，当i f 的两条基边恰与y 的两条基边重合时，图g 中 有可能出现有向圈，设这两条基边为( l a ) ，( z ，b ) ，分下面两种情况讨论： ( 1 ) 两条基边都存在，如图3 1 ( a ) 所示，此时给圈定向为从z 到a 、b 的 两条有向路，工和y 均定向为从，到a 所在的有向路上的某点到z 到b 所在的 有向路上的某个点的方向，或者，均为其反向： ( 2 ) 只有一条基边存在，如图3 2 ( b ) 所示，此时必有x 和y 的某个端点 与，重合，规定图的树边为从z 到基点方向的一条有向路，非树边定义为 从，到另一个端点的方向； ( a )( b ) 图3 1 ：可能出现有向圈的情况 非树边和树组成的圈按照以上方法定向，自然不会出现有向圈，然而对 图中所有的基本圈的并，则有可能出现形成有向圈的情况。对于这种情况， 可以用下述方法来避免。对于按上面方法定向的基本圈，可以看做一个不可 分离块，该圈中的源和汇视为割点，由前面吸收规则中所讲的割点块图的构 造方法，可以得到已定向部分的割点块图，再根据新得到的图把定向的过程 继续下去，直至最后所有的边被定向，而在这个过程中，不会出现有向圈。 3 3 算法的实现 下面我们来看给出一个任意连通图，怎样求它的双极定向。其算法描述 如下： ( 1 ) 找出g 的支撑树t = ( ke 7 ) ，其过程如下：首先找出v t 的诱导子图 的支撑树，再把节点t 和边( j ，t ) 添加在该树上。最后把丁转化成以t 为根的有 根树。 ( 2 ) 对每一个顶点v v ，以t 为根，给每一个顶点任意标数，对每个非树 边“，1 ，计算l c a ( u ，v ) ，并把得到的l c a 值按照从小到大的顺序重新排序。 1 7 北京交通大学硕士学位论文第3 章吸收规则法 ( 3 ) 把边( 文t ) 定向为j 到t 的方向首先考虑与t 相关联的非树边，必有圈 存在，即在j 和t 之间存在一条无内点为用过节点的路p ( s ，力，规定该路的方 向为从s 到f ，标记路p ( s ，t ) 上的边标记为已用过，记已用过边的集合为q 。 ( 4 ) 对ve q ，若存在一条非树边与之相临，则存在一个由该非树边构成 的圈c ，设p ( u ， ，) 是圈c 上的已定向的一条路且其方向为从“到 ，则圈c 上 的未定向边也定向为从u 到v 的方向。 若两条非树边e l ，e 2 满足l c a ( e 1 ) = l c a ( e 2 ) = z ，分以下两种情况讨论： ( a ) 若p l ，e 2 有两条基边，设这两条基边所在的路分别为p l ，p 2 ， 则e i ，e 2 均定向为从p l 到尸2 的方向； ( b ) 若若e l ，e 2 只有一条基边，此时p i ，e 2 均有一个端点为z ，此时规 定e l ，e 2 的方向为从z 到另一个端点。 把已用过的边标记为已用过，更新集合q 。 图3 2 ：给l c a 相同的非树边的基本圈定向 ( 5 ) 一直继续过程( 4 ) 直到所有的边均被定向为止； ( 6 ) 删除边( s ，力，最后得到的即为图g 的一个双极定向。