（运筹学与控制论专业论文）图的完全可定向性.pdf

图的完全可定向性 摘要 设d 是简单图g 的一个无圈定向若改变d 中的一条弧的方向会产生有 向圈，则称这条弧为d 的相依边用d ( d ) 来表示d 中相依边的条数，d l i l i n ( g ) 和 d l i l 戤( g ) 分别表示g 的所有无圈定向中相依边数的最小值和最大值若对满足 d i n i n ( g ) 七d m 娃( g ) 的所有七，都存在g 的无圈定向d 使得d ( d ) = 七，则称g 是完全可定向的 图的完全可定向问题首先由f i s h e af r a u g h n a u g h ，l a n g l e y 和w e s t 2 】开始研 究的最近，台湾一些学者给出若干有趣的研究结果【8 1 0 ，1 2 ，1 3 】本学位论文研 究一些特殊图的完全可定向问题，如圈的平方、圈的立方、2 - 夕f 、平面图、无爪 3 退化图等 本文共分5 章在第l 章中，我们给出所用到的基本概念，简述了相关领域的 研究现状并呈现了本文的主要研究结果 在第2 章，我们证明了无爪3 一退化图和不含飓( 2 ) 作为导出子图的2 - 夕 平面 图是完全可定向的 在第3 章，我们证明了：若d m 联( g ) 6 ，则g 是完全可定向的 在第4 章，我们确定了f z r i i i n ( 砩) 的值并证明了当他7 时碟是完全可定向 的 在第5 章，我们确定了如i n ( 锑) 的值并证明了当n 9 时砩是完全可定向 的 关键词：图；无圈定向：完全可定向；相依边；圈 i f u l l yo r l e n t a b i l i t yo fg r a p h s a b s t r a c t l e tdb ea na c y c l i co r i e n t a t i o no fas i m p l eg r a p hg a na l eo fdi sc a l l e dd e p e n d e n ti fi t sr e v e r s a lc r e a t e sad i r e c t e dc y c l e l e td ( d ) d e n o t et h en u m b e ro fd e p e n d e n t a r c si nd d e f i n ed m i n ( g ) ( a m a ) 【( g ) ) t ob et h em i n i m u m ( m a x i m u m ) n u m b e ro fd ( d ) o v e ra l la c y c l i co r i e n t a t i o n sdo fg w ec a l lg f u l l yo r i e n t a b l ei fg h a sa na c y c l i co r i - e n t a d o nw i t he x a c t l y 七d e p e n d e n ta r c sf o re v e r yks a t i s f y i n ga m i n ( g ) k 戕( g ) f i s h e r , f r a u g h n a u g h ，l a n g l e ya n dw e s t 【2 】f i r s ti n v e s t i g a t e dt h ef u l lo r i e n t a b i l i t y o fg r a p h s r e c e n t l y , s o m et a i w a n e s ea u t h o r sh a v eo b t a i n e ds o m ei n t e r e s t i n gr e s u l t s o nt h i sd i r e c f i o n i nt h i sm a s t e rt h e s i s ，w es t u d yt h ef u l lo r i e n t a b i l i t yo fs o m es p e c i a l g r a p h ss u c ha st h es q u a r eo fac y c l e ，t h ec u b eo fac y c l e ，c r a w - f r e e3 - d e g e n e r a t eg r a p h s a n d2 - o u t e r p l a n a rg r a p h s t h et h e s i sc o n s i s t so ff i v ec h a p t e r s i nc h a p t e r1 ，w ec o l l e c ts o m eb a s i cn o t a t i o n a n dg i v eac h i e fs u r v e yi nt h i sd i r e c t i o n m a i nr e s u l t so b t a i n e di nt h i st h e s i sa r es t a t e d i nc h a p t e r2 ，w ep r o v et h a te v e r yc r a w - f r e e3 - d e g e n e r a t eg r a p h sa n d2 - o u t e r p l a n a r g r a p h sw i t h o u tk 3 ( 2 ) a sa ni n d u c e ds u b g r a p ha r ef u l l yo r i e n t a b l e i nc h a p t e r3 ，w ep r o v et h a ti f 缸“( g ) 6t h e ngi sf u l l yo r i e n t a b l e i nc h a p t e r4 ，w ed e t e r m i n et h ev a l u eo fd m i 。( 砩) a n dp r o v et h a t 砩i sf u l l yo r i e n t a b l ef o ra n y 礼7 i nc h a p t e r5 ，w ed e t e r m i n et h ev a l u eo fa m i n ( 砩) a n dp r o v et h a t 砩i sf u l l yo r i e n t a b l ef o ra n yn 9 k e yw o r d s ： g r a p h ；a c y c f i co r i e n t a t i o n ；f u l l yo r i e n t a b l e ；d e p e n d e n ta r c ； c y c l e ， ， ， 目录 摘要 i a b s t r a c t i l 目录 1 绪论1 1 1 基本概念1 1 2 完伞可定向的研究概况3 1 3 本文主要结果5 2 无爪3 - 退化图和2 - 外平而罔的完全可定向性 6 2 1 两个引理6 2 2 完伞可定向性1 2 3 关于如舣的极值1 6 4 砩的完全可定向性2 0 4 1 砩的最小相依边数2 0 4 2 砩的完全可定向性2 2 5 砩的完全可定向性2 4 5 1 碟的最小相依边数2 4 5 2 诣的完全可定向性4 8 攻读学位期间取得的研究成果6 1 致谢配 浙江师范大学学位论文独创性声明6 3 学位论文使用授权声明6 3 i 学位论文诚信承诺书“ i v 1 1 基本概念 1绪论 本节给出一些图论的基本术语与符号把一个有序对g = ( ue ) 称为一个 图，其中y 是一个集合，e 是由y 中元素组成的某些无序对的集合y 中的元素 叫做图g 的顶点，e 中的元素叫做图g 的边通常地，用v ( e ) 和e ( g ) 分别表示 一个图g 的顶点集合和边集合，用i g i 和0 g 0 分别表示g 的顶点数和边数没有 重边和环的图叫做简单图本文仅考虑顶点数有限的简单图 对于图g 的顶点t 和u ，若e = 牡u e ( g ) ，则称u 和u 在g 中相邻，或t 和 互为邻点这时又称仳和 是边e 的两个端点，或u 和秒分别与e 相关联对于 一个顶点u y ( g ) ，t ，在g 中的度记为d g ( u ) ，简写为d ( ) 若d ( v ) = k ，则称 为g 的一个k 点用a ( g ) 和6 ( g ) 分别表示g 的最大度和最小度用n ( v ) 表 示u 的所有邻点的集合任意两个点都相邻的图叫做完全图，一般用符号珞来 表示顶点数为n 的完全图对于整数k 0 ，设v ( c ) = uk u uk ，对于 1 i k ，若k 中任意两个项点t ，u 都不相邻，则称g 是七部图对于七部图 g ，设1 i j k ，若对任意牡k 和 k 都有t e ( g ) ，则称g 是完全 七一部图，并且若有i i = i i = = i v k l = n 0 ，则称g 是完全等k - 部图，记为 k k ( n ) 图g 中的一个点边交替序列w = d o e l u l e 2 e 七仇叫做一条途径，其中 e = 优一l 仇e ( g ) ，1 i k 若珈= 班，则称硼为一条闭途径又若途径 t i 上的顶点珈，u l ，忱，仇互不相同，则称叫为一条( 咖一仇) 路，记作r ，称 伽，坝分别为路r 的起点和终点起点和终点相同的路称为圈路( 圈) 上的边数 为路( 圈) 的长度g 的围长是指图g 中最短圈的长度，用g ( g ) 来表示；若g 无圈， 则定义g ( g ) = 0 0 对于图g = ( y ( g ) ，e ( g ) ) 和图h = ( v ( ) ，e 7 ( ) ) ，若有y ( 何) y ( g ) ， e 7 ( 日) e ( g ) ，则称图是图g 的一个子图对于整数k 0 ，若g 的任意子 图日中都存在点t ，使得d h ( v ) k ，则称g 为七一退化的设y ( g ) ，把图 g 中属于的顶点以及与y 中的点关联的边都删除所得到的图记作g y ， 或g y 7 同样地，设冬e ( 日) ，把图g 中属于e 7 的边都删除所得到的图记 1 绪论 作g e 7 或g 一( 日) 特别地，当v 7 = 乱l 时，把g y 7 简记为g 一仳；当 = u 时，把g 一简记为g u y 对于y 7 y ( g ) ，把由y 作为顶点集， e 7 = e l e = i , v e ( g ) ，乱，v v 7 ) 作为边集的图叫做g 中由顶点子集y 7 导出 的子图或者称为生成子图，记作a v 】同样地，对于e 7 f ( g ) ，把由e 7 作为边 集，v 7 = u e l e e 7 】作为点集的图叫做g 中由边子集导出的子图，记作 g 【】 若对于图g 中的任意两个顶点乱和 ，g 中都存在一条( 让一v ) 一路，则称g 为连通图，否则称为非连通图非连通图g 的极大连通二f 图又叫做g 的连通分 支著g 是连通的且不含有圈，则称g 为树由若干棵树所组成的图称为一个 森林，即森林巾的每个连通分支是一棵树对于非完全图g ，毋y 7 y ( g ) ，若 g y 7 非连通，则称y 7 是图g 的顶点割若l v 7 l = k ，贝l j 称y 为g 的k 点割对 于g ( 表示阶数为咒的完全图) ，把图g 中顶点数最少的点割所含的点 数称为图g 的连通度，记作k ( g ) 定义的连通度为n 一1 ，非连通图的连通度 为o 若g 满足k ( g ) k 0 ，则称g 是k 连通的 对于整数m 2 ，g 的m 次方图，用g m 来表示，是指v ( a m ) = y ( g ) ，在g m 上两个不同点相邻当且仅当它们在g 上的距离不超过m 特别地，称g 2 为g 的 平方图，g 3 为g 的立方图对于长度为礼的圈g ，我们用暖来表示它的平方图， 用锑来表示它的立方图 对无向图g 的每条无向边指定一个方向，由此得到的有向图d ，称为g 的定 向图；反之，如果把一个有向图d 的每条有向边的方向去掉，由此而得到的无向 图g ，称为d 的底图给定图g 的一个无圈定向d ，用v ( d ) 与e ( d ) 分别表示 d 的点集与弧集用u _ 表示以u 为尾以u 为头的弧，在不清楚钆，u 方向的情 况下，有时也用u v 表示有向边点u 的入度d d ( v ) 是指在d 上以 为头的弧数， 出度d 去( u ) 是指在d 上以 为尾的弧数若d + ( u ) = d a ( u ) ，则称u 为d 上的一 个源；若d d ( v ) = d a ( v ) ，则称u 为d 上的一个汇对于s ，t y ( d ) ，用尸；：州) 表示 d 上从8 到t 的一条有向路；若d 上不存在从s 到t 的有向路，那么就表示只“1 不存在 设d 是g 的一个无圈定向，若改变d 中的条弧的方向会产生有向圈，则 称这条弧为d 的相依边用r ( d ) 表示d 上的所有相依边的集合，d ( d ) 表示d 中相依边的条数，即d ( d ) = i r ( d ) i 由相依边的定义可知，给定一条以z 为尾，以 y 为头相依边，那么d 中必包含一条长度至少为2 从x 到y 的有向路用如i n ( g ) 和如。( g ) 分别表示g 的所有无圈定向中相依边数的最小值和最大值若对于满 2 1 绪论 足如i n ( g ) k e m 蚁( g ) 的所有k ，都存在g 的无圈定向d ，使得d ( d ) = k ，则 称g 为完全可定向的，或称g 是完全可定向图 设咖是图g 上v ( g ) _ 1 ，2 ，七) 的一个映射，若对任意边u u e ( g ) 都 有e p ( u ) ( ) ，则称是g 的一个正常顶点k 染色若图g 有k 染色，则称g 是七一可染的；定义g 的色数x ( a ) 为x ( g ) = m i n klg 是七一染色的 文中其它未加说明的符号和术语请参阅文献【l 】 1 2 完全可定向的研究概况 随着信息科学和计算机科学技术的迅猛发展，图论作为其重要理论基础日益 得到国际数学界和理论计算机科学界的高度重视和广泛研究图论不仅在计算机 科学、信息科学、编码和密码学、通讯工程、d n a 的基因谱的确定和计数、工 业生产和企业管理中有重要应用，而且在其它科学技术领域如物理、化学、生 物、金融学、社会学等也有广泛的应用图的完全定向性的研究可以为图论，乃 至数学的发展提供一种新的思维、新的方法 设p 是一个有限偏序集，它的偏序关系为将p 的元素作为点，两点n ，b 相邻当且仅当或口 口，这样所得的图称为有限偏序集p 的h a s s e 图，也 称为覆盖图 f i s h e r , f r a u g h n a u g h ，l a n g l e y 和w e s t 【2 1 首先研究了图的完全可定向性，证明 了下面三个有趣的结果： 定理1 1 【2 】厶埘( g ) = i l g i i i g i + c ，其中c 表示图g 的连通分支数 定理1 2 【2 】如i i i ( g ) = 0 当且仅当g 是覆盖图 定理1 3 【2 】若x ( g ) 因 此，r ( d ，) = r ( d ) u ( z ，t | ) ，( y ，t ) ) 因为( x ，t ) ，( y ，1 i ) 譬r ( d ) ，所以d ( d ) = i r ( d ，) i = i 兄( d ) i + 2 = d ( d ) + 2 情形2 z _ 可 易见( z ，牡) ，( z ，仳) r ( d ) ，因此r ( d ) u ( z ，u ) ，( z ，u ) r ( d ) 若( y ，t i ) r ( d ) ，则可类似证明d 存在包含( z ，y ) 或( z ，y ) 的有向圈，矛盾因此，( y ，t 1 ) 岳 r ( d ) 设( s ，t ) er ( d 7 ) r ( d ) 且( 5 ，t ) 不是( x ，仳) 或者( z ，u ) 那么在d 上存在 从s 到t 长度至少为2 的一条有向路q 同样，我们能证明( s ，t ) 是d 上的一条 相依边，矛盾于( s ，t ) 的选择 现在，我们知道r ( d 7 ) r ( d ) u ( z ，t | ) ，( z ，u ) ) 因此，r ( d ) = r ( d ) u 【( z ，t ) ，( z ，u ) ) 因为( z ，t ) ，( z ，t i ) 隹s ( d ) ，所以d ( d ) = i r ( d ，) i = i 兄( d ) i + 2 = d ( d ) + 2 ( 2 ) 由( 1 ) 知，厶i n ( g ) d m m ( g ) 蟊i i n ( g ) + 2 并且，如戤( g ) = i i c i i i g i + 1 = ( i l c l i + 3 ) 一( j g l + 1 ) + 1 = i i c l i i g i + 3 = 如“( g ) + 2 不妨设g 是完全可定向的由( 1 ) 知，对于满足如i n ( g ) + 2 m d i i 煅( g ) + 2 = 站娃( g 7 ) 的每个m ，g 7 中都有一个使d ( d ) = m 的无圈定向d ，如果 厶i n ( g ，) d m i i i ( g ) + 1 ，那么易见g ，是无圈定向的所以不妨设如i n ( g ，) = 站i n ( g ) 为了证明g 7 是完全可定向的，只要找到g ，上的一个使得d ( d ) = 如i i n ( g ) + 1 的无圈定向d 由定义知，存在g 的一个使得d ( d ) = d m j l l ( g ，) = 如i n ( g ) 的无圈定向d 7 令j d 是通过删除d 顶点u 后而得到的有向图，则d 是 g 的一个无圈定向由于d ( d 7 ) = d m i n ( g ) = d m i n ( g ) d ( d ) d ( d ，) ，则d ( d ) = d ( d ) 且d ( d ) = d m i n ( g ) 这意味着r ( d ) = r ( d ，) 所以u z ，u y ，u z 圣r ( d ，) 由 于u x y u 是一个三角形，在d 7 中某条边是相依边由这两个结果可得x y r ( d 7 ) 类似地，我们可以断言y z r ( d 7 ) 因此，z 掣，y z 兄( d ) 不失一般性，假设d 中 有z _ y 此证明分为如+ 卜的两种情形 情形1 _ z 7 2 无爪3 退化图和2 - 夕 平而图的完全可定向性 在d 7 上，通过使z u ，牡_ y 和仳_ z 定义了g ，卜的一个定向d + ，即 d = d u ( z ，让) ，( 仳，i | ) ，( u ，z ) 首先证明d + 是无圈的事实上，如果d + 中存在 有向圈c ，那么由d 是无圈知，c 必定经过u 存在如下两种可能性： ( a ) c 含有向路( z ，乱，可) 则( c ( z ，乱，秒) ) u ( z ，y ) 有在d 上的有向圈，矛盾 ( b ) c 含有向路( z ，礼，z ) 则( c ( z ， ：z ) ) u ( z ，y ，z ) 有在d 上的有向圈，矛盾 下面我们需要证明r ( d ) = r ( d ) u ( z ) ) ，这将推出d ( d + ) = i r ( d + ) l = l 冗( ，) ) l + 1 = d ( o ) + 1 = d m i 。( g ) + 1 ，因此证明完毕不难得到( 仳，z ) r ( d + ) 且 r ( d ) r ( o + ) ，使得r ( o ) u ( u ，z ) r ( d + ) 由于改变( z ，u ) 方向会使得u 成 为源，所以( z ，让) 萑r ( o + ) 如果( 钆，y ) r ( d + ) ，那么存在从乱到y 长度至少为2 的一条有向路q 容易 得到q 含( 让，z ) 但是，( q ( “，z ) ) ) u ( y ，z ) 在，) 上含有一个有向圈，矛盾所以 ( 仳，y ) 聋s ( d + ) 设( s ，t ) r ( d + ) 兄( d ) 且( s ，t ) 不同于( 札，z ) 那么存在从s 到t 长度至少 为2 的一条有向路q 那么q 必定经过u ，因为否则( s ，t ) 属于r ( d ) 如果q 含 有( z ，札，可) ，那么令q 7 = ( q ( z ，仳，) ) u ( z ，可) 如果q 含有( z ，“，z ) ，那么令q 7 = ( q ( z ，乱，3 ，) ) u ( z ，y ，z ) 则q 7 在d 上存在从5 到t 长度至少为2 的一条有向路， 推出( s ，t ) r ( d ) ，矛盾于( s ，t ) 的选择因此，结果是r ( o + ) r ( d ) u ( 乱，z ) ) 所以d ( d + ) = i r ( o + ) l = i r ( d ) l + 1 = d ( d ) + 1 = 如i n ( g ) + 1 情形2 z 一剪 由d 的无圈性知，对于任何两个点s ，t y ( d ) ，在d 上至多存在毋叫) 和 p ( s ) 中之一鉴于这一事实，我们考虑以下两种子情形 情形2 1 在d 中p ( 掣) 和p ( 邵) 都不存在 在d 7 中令札_ z ，秕_ 掣和u z 定义了g 的一个定向d + ，即d = d u ( u ，z ) ，( u ，秒) ，( u ，z ) 由于仳是源，则d 是无圈的易验证( u ，y ) r ( d 4 ) 且 r ( d ) r ( d + ) ，凶此r ( o ) u ( 乱，箩) ) 兄( d + ) 设( u ，z ) r ( o + ) 那么存在从u 到z 长度至少为2 的一条有向路q 所以， ( u ，y ) q 或者( u ，z ) q 如果( t l ，y ) q ，那么( q ( u ，y ) ) u ( z ，y ) 含有d 中的 有向罔，矛盾如果( 札，z ) q ，那么q ( 仳，z ) 含有d 中从z 到z 的有向路，矛盾 于假设不存在r 邵) 因此，( u ，z ) 譬r ( o ) 类似地，可以证明( t l ，z ) 譬r ( o ) 设( s ：t ) r ( o + ) 兄( d ) 且( s ，t ) 不同于( 乱，y ) 那么d + 存在从s 到t 长度 8 ， 2 无爪3 退化i 冬l 和2 外平而| 冬l 的完伞可定向性 至少为2 的一条有向路q 由于u 是d 的源且q 不经过乱，所以q 也是d 的从s 到t 长度至少为2 的一条有向路因此( s ，t ) 兄( d ) ，矛盾于( s ，t ) 的 选择这证明了r ( d ) r ( d ) u ( t l ，可) 因此，r ( d ) = r ( d ) u ( u ，y ) ) 且 d ( n ) = i r ( d ) i = i r ( | 7 ) ) i + 1 = d ( d ) + 1 = d r n i n ( g ) + 1 情形2 2 在d 中只即) 存在 由前面的分析知道，p c 础) 在d 中不存在在d ，中令u x ，让_ y 和z _ t 后定义了g ，的一个定向d ，即d = du ( 乱，z ) ，( t z ，) ，( z ，u ) 首先需要证明d 是无圈的假设不成立，则d 含有一个有向圈c 由于d 足无圈的，那么c 必定经过让如果c 包含( z ，也，可) ，那么( c ( z ，t l ，秒) ) u ( y ，z ) 含 有d 的有向圈如果c 包含( z ，t i ，z ) ，那么( c ( z ，t j ，z ) ) u 只：，卫) 含有d 的有向圈 在两种情况下我们得出一个同样的矛盾 易得( t ，可) ，( z ，y ) r ( d ) 和r ( d ) r ( d ) ，因此r ( d ) u ( t | ，y ) ) r ( d 。) 为了证明r ( d ) r ( d ) u ( 札，) ，我们首先注意到( z ，t 1 ) 簪r ( d 。) 而且。如 果( u ，x ) r ( d + ) ，那么类似地可以证明d 存在一个含有( z ，y ) 的有向圈因此， ( 牡，x ) 簪r ( d + ) 设( s ，t ) r ( d + ) 兄( d ) 且( s ，t ) 不同于( t l ，可) 那么d 存在从s 到t 长 度至少为2 的一条有向路q 经过点t 我们断言( s ，t ) 不是( z ，y ) 且( 8 ，t ) 簪 尸；：邵) ，因为否则qu 尸；：妒) u ( x ，y ) 含有d 的有向圈如果p 含有( z ，u ，可) ， 那么( q ( z ，t ，可) ) u ( z ，y ) 在d 中存在一个从s 到t 的有向路如果p 含有 ( 名，t | ，z ) ，那么( q ( z ，t l ，z ) ) u 只郴) 在d 中存在一个从s 到t 的有向路我们得出 ( s ，t ) r ( d ) ，矛盾于( s ，t ) 的选择 现在我们已经证明了r ( d ) = r ( d ) u ( u ，秒) ) 因此，d ( d ) = d ( d ) + l = 如i n ( g ) + 1 口 引理2 4 设g 是一个图使得z 秒e ( a ) 且茁z ，y z 甓e ( g ) 令g 7 是由g 增加一 个与z ，y ，z 相邻的新顶点u 后得到的图 ( 1 ) 如果g 含有一个d ( d ) = k 的无圈定向d ，那么g 含有一个d ( d ) = k + l 的无圈定向d 7 ( 2 ) 如果g 是完全可定向的，那么g 也是完全可定向的 证明：由引理2 1 和2 2 ，不妨假设g 是2 连通的 ( 1 ) 不妨设在d 中有z _ 箩根据对称性，只需考虑以下三种情况： 9 2 无爪3 退化图和2 夕 平而图的完全可定向性 情形1 在d 中只舭) 存在 我们注意到最础) 在d 中不存在基于d ，通过使z _ 让，秒_ u 和札_ z ， 我们定义了g 7 的一个定向d 7 如果d 7 含有一个有向圈c ，那么c 必定含有 ( z ：乱，z ) 或者( y ，仳，z ) 对于前者，( c ( z ，札，z ) ) u ( 1 7 ，y ) u 只舭) 含有d 的有向圈 对十后者，( c ( 可，札，z ) ) u 只舭) 含有d 的有向圈因此，d 是无圈的 容易观察到( 乱，z ) 隹r ( ，) ) 且( z ，仳) r ( ，) ，) 注意到n ( d ) n ( o ，) 所以r ( o ) u ( z ，仳) r ( o ，) 设( ，“) 兄( d ，) 那么存在从剪到牡长度 至少为2 的一条含有( z ，u ) 的有向路q 但是，( q ( z ，札) ) u ( 3 7 ，! ，) 含有d 的 有向圈，矛盾因此，( ，u ) 隹r ( d ，) 设( s ，t ) r ( d 7 ) r ( d ) ( s ，t ) 不同于 ( z u ) 那么d 7 中存在从s 到t 长度至少为2 的一条有向路q 经过点札那么 ( s t ) 甓| p ：舭) u ( z ，y ) ) ，因为否则qu ( z ，可) u 只妒) 将会含有d 的有向圈如果 p 含有( z ，乱，z ) ，那么令q 7 = ( q ( z ，仳，z ) ) u ( z ，可) u 毋舭) 如果尸含有( y ，札，z ) ， 那么令q 7 = ( q ( y ，让，z ) ) u 只舭) 存每一种可能的情况下，q 7 含有d 的从s 到t 的有向路，这意味着( s ，t ) 兄( d ) ，矛盾于( s ，t ) 的选择 到目前为止，我们已经证明了r ( d 7 ) r ( d ) u ( z ，u ) ) 所以，兄( d 7 ) = r ( d ) u ( z ，仳) ) 因此d ( d ) = i r ( d ，) i = i r ( d ) i + 1 = d ( d ) + 1 情形2 在d 中尸；：钿) 存在但旦邵) 不存在 那么d 中尸( 舭1 不存在证明将分成两种予情形： 情形2 1 d 中只础) 存在 注意到p ( 刎) 和只邓) 内部顶点不相交，因为否则d 含有有向圈通过 令z _ u ，u _ 和“_ z 我们能构造g 7 的定向d 7 如果j ) 7 含有一个有 向圈c ，那么由d 是无圈的知，c 必定含有( z ，u ，可) 或者( z ，札，z ) 对于前者， ( c ( z ，牡，y ) ) u ( z ，可) 含有d 的有向圈，矛盾对于后者，( c ( z ，仳，z ) ) up ( 即) 含有 d 的有向圈，矛盾因此，d 7 是无圈的 容易观察到( z ，札) 垡n ( o ) 且( 仳，y ) ，( z ，) r ( ，) ，) 注意到r ( d ) r ( o ，) ， 所以有r ( o ) u ( 札，剪) 】r ( ) 设( 札，z ) r ( d ，) 那么d 7 存在从u 到z 长 度至少为2 的一条含有( 让，) 的有向路q 但是( q ( 乱，! ，) ) u 只：，y ) 含有d 的有 向圈，矛盾因此，( 牡，z ) 譬r ( d ，) 设( s ：t ) r ( d ) r ( d ) 且( s ，t ) 不同于( 让，可) 和( z ，y ) 那么d 7 中存在从s 到t 长度至少为2 的一条有向路q 经过点u 同样，( s ，t ) 譬p ( 舭) up ( 邵) ，否则qu 最：，v ) u 只邵) 含有d 的有向圈如果q 经过( z ，缸，可) ，那么令q 7 = ( q ( z ，u ，可) ) u ( z ，! ，) 如果q 经过( z ，u ，z ) ，那么令 l o ， 一 ， 2 无爪3 退化i 冬i 和2 夕h 平而i 冬i 的完令可定向性 q = ( q ( z ，仳，z ) ) up c 即) 则q 是d 从s 到t 的有向路，凶此( 8 ，t ) r ( d ) ，矛 盾于( s ，t ) 的选择 所以r ( d 7 ) n ( d ) u ( u ，可) ) 因此，r ( d 7 ) = r ( d ) u ( t l ，可) ) ，则d ( d 7 ) = i r ( d ，) i = i r ( d ) lq - l = d ( d ) + 1 情形2 2 d 中n ”) 彳i 存在 通过令一z ，札_ y 和牡_ z 定义了g 的一个定i 句d 冈为“是源，所 以，) 7 是无圈的易见( 札，y ) r ( d 7 ) 且r ( d ) r ( d ，) 所以r ( ，) ) u ( t l ，秒) ) r ( d ，) 设( u ，上) r ( d ，) 那么d 7 中存在从t i 到z 长度至少为2 的条有向路 q 含有( 缸，y ) 或者( 缸，z ) 对于前者，( q ( 牡，! ，) ) u ( z ，y ) 含有d 的有向圈，矛盾 对于后者，q ( t t z ) 含有d 从名到z 的有向路，矛盾于假设只w ) 不存在因此， ( “，z ) 隹r ( d ，) 设( t | ，z ) r ( d ，) 那么d 包含从“到z 长度至少为2 的一条 有向路q 含有( u ，x ) 或者( u ，可) 对于前者，q ( 牡，z ) 含有d 的从z 到z 的有向 路，矛盾于假设只邵) 不存在对于后者，q ( u ，z ) 含有d 的有向圈，矛盾因此， ( 乱，z ) 簪r ( d ，) 设( s ，t ) r ( ) r ( d ) ，且( 8 ，t ) 不同于( u ，y ) 那么d 7 含有从s 到t 长度至少为2 的一条有向路q 因为仳是源，所以q 不经过牡因此，q 也是 d 的从s 到t 长度至少为2 的一条有向路这可推出( s ，t ) r ( d ) ，矛盾于( 5 ，t ) 的选择 这表明r ( d 7 ) r ( d ) u ( t i ，! ，) ) 所以，r ( d ) = n ( d ) u ( u ，剪) 因此， d ( d ) = i r ( d ，) l = i 兄( d ) l4 - l = d ( d ) + 1 情形3 在d 中尸( 即) ，只郴) ，只 ) 和只硼) 都不存在 通过令札_ z ，t l _ y 和牡_ z 定义了g 的一个定向d ，因为牡是源，所 以d 是无圈的易见( 乱，y ) r ( d 7 ) 且r ( d ) r ( d ，) 所以r ( d ) u ( t l ，可) ) r ( d ，) 设( t ，z ) r ( d ，) 那么d ，存在从u 到z 长度至少为2 的一条有向路q 含 有( u ，y ) 或者( t l ，z ) 如果( u ，y ) q ，那么( q ( u ，y ) ) u ( z ，y ) 含有d 的有向圈。 矛盾如果( t l ，z ) q ，那么q ( u ，z ) 含有d 的从z 到z 的有向路，矛盾这些 矛盾推出( u ，z ) 隹r ( d ，) 设( t ，z ) r ( d ) 那么d 7 中存在从u 到z 长度全少 为2 的一条有向路q 含有( u ，z ) 或者( t t ，y ) 如果( u ，z ) q ，那么( q ( 仳，z ) ) 含 有d 中从z 到z 的有向路，矛盾如果( u ，) q ，那么( q ( 札，可) ) 含有d 中从 矽到z 的有向路，矛盾这些矛盾推出( u ，o ) 岳r ( d ，) 类似地，我们可以证明除 ( 牡，y ) 外不存在( s ，t ) r ( d 7 ) r ( d ) 因此，r ( d 7 ) r ( d ) u ( t l ，y ) 我们得到的 2 无爪3 退化图和2 - 夕 平面图的完全可定阳性 r ( d 7 ) = r ( d ) u ( u ，) ) ，且d ( d 7 ) = i r ( d ) l = i r ( d ) l4 - 1 = d ( d ) 4 - 1 ( 2 ) 由( 1 ) ，我们立刻得到d a n i n ( g ) d r a i n ( g 7 ) d r a i n ( g ) 4 - 1 而且，d m a x ( g 7 ) = i i g ，i i l g 7 i + 1 = ( i i g 0 + 3 ) 一( i g i + 1 ) + l = i i g 0 一l g l + 3 = d m 双( g ) 4 - 2 设 g 是完全可定向的由( 1 ) 知，对于如i 。( g ) 4 - 1 m d m 。( g ) + 2 = d m a x ( 0 7 ) 的 m ，g 7 中存在一个无圈定向d 7 使得d ( d ) = m 这表明g 7 也是无圈定向的口 2 2 完全可定向性 引理2 3 和2 4 对- j j 完全定向图的3 度点建立了两个有明的性质奉：1 了我们将 给出它们的一些应 j 如果图g 不包含i 3 作为导m 子图，则称g 是无爪的显然，一个无爪图的 子图也是无爪图丸爪图是一个重要的图类，它包含了所有图的线图，而线图本 身就是图论中的一个重要图类近年来，关于无爪图的研究有很多结果，如哈密顿 问题、完美图问题、控制数等，具体参见文献【1 4 1 5 引理2 5 【1 0 】设图g 含有一个度至多为2 的点牡如果g 一乱是完全可定向的，那 么g 也是 定理2 1 任何无爪3 退化图是完全可定向图 证明：我们利用项点数目i g i 来归纳证明如果i g i = 1 ，那么结果显然成立设 g 是无爪3 退化图且i g i 2 由于g 是3 退化的，那么存在点u v ( v ) 使得 d ( v ) 3 令h = g 一仉根据定义，h 也是无爪3 退化图由归纳假设，是完全 可定向图如果d ( v ) 2 ，那么由引理2 5 知g 是完全可定向图假设d ( v ) = 3 且 钞在g 中的三个邻点为z ，y ，z 由于g 是无爪的，那么z 可，妒或z x 中至少之一属 于e ( g ) 如果它们中至少有2 条属于e ( g ) ，那么引理2 3 断言g 是完全可定向 图如果它们中恰好有l 条属于e ( g ) ，那么引理2 4 保证g 是完全可定向图这 就完成了本定理的证明口 对于整数k l ，图g 称为后- 夕f 、平面图，如果g 有一个平面嵌入使得g 的所 有顶点位于在k 个面 尼， 上，即v ( c ) = y ( ) uy ( 五) u uy ( ) ，其 中y ( 五) 表示在面 j 的顶点集合当k = 1 时，g 是通常的外平面图外平面图 是一类重要的图类，它有着很好的结构性质，在实际问题中有广泛应用，关于它的 研究见文献【1 6 18 】 汤宇翔和王维凡在文献【1 9 】中研究了2 - 夕h 平面图的结构性质，并利用这些 性质给出了2 - 夕h 平而图的l ( 2 ：1 ) 标号数的好的上界 1 2 ， 2 无爪3 退化l 冬i 和2 - 夕 平而i 冬i 的完令可定向性 引理2 6 1 9 1 设g 是一个2 - 连通2 - 夕 平面图则6 ( g ) 4 ；且6 ( g ) = 4 当且仪当 g 同构于对某个n 3 回忆一下，每个外平面图g 都有6 ( g ) 2 对于n 3 ，设c = x l x 2 z n x l 和c = y l y 2 y y l 是两个点不交的n 一圈，使得c 7 在c 的内部令t t 2 n = c uc ”o x _ i y i it = 1 ，2 ，n 引理2 7 若g 是2 一连通的2 - 夕h 平【1 1 f 图且不同于所有礼3 的仍n 和嚷，则g 包含一个顶点 使得d ( v ) 2 ，或d ( u ) = 3 且口的邻点中至少有一对是相邻的 证明：如果g 是外平而图，那么结论显然成立所以，假设g 有一个平面 嵌入使得g 的所有顶点位于在两个面上，记这两个面为 和厶因为g 是 2 一连通的，所以 的边界是圈c = u o u l t l k - i u o ，七3 ，且 的边界是圈 c ”= r o y l 铆一l u l j 3 因此，v ( g ) = y ( ) uy ( 如) = v ( c ) ov ( c ”) = 咖，u 1 ，毗一l ，v o ，口l ，功一i ) 且i g l = k + z 6 假设c 有一条弦u i u j 使得j i + 2 ，其中下标取为模k 用m 表示由 讹，讹+ 1 ，) 导出的子图，用表示由 吻，u j + 1 ，t | t ) 导出的子图易见 舰和m 2 中至少有一个是点数至少为3 的外平面图，不妨设m 1 是与文献【1 9 】 中的引理3 的证明类似，存在u 。，其中t + 1 s j 一1 ，使得d g ( ) = 2 如果 伊+ 有弦。那么我们有类似的证明 现在假设驴和c ”都是无弦的这意味着任何边e e ( g ) ( e ( 伊) u e ( c “) ) ，一个端点属于y ( c ) 且另一个端点属于v ( c ”) 如果6 ( g ) = 2 ，证明完 毕如果6 ( v ) = 4 ，那么由引理2 6 知，g 同构于某个礼3 的