（运筹学与控制论专业论文）立方图中处处非零三流.pdf

硕士学位论文 m a s t er ，s t h e s i s 摘要 本文证明了g 2 推出3 一n z f ，当且仅当g 叠a ，在此基础上进一步证明了g f k 3 1 推出3 一n z f ，当且仅当h 叠a 。，其中h 是g 的任一分支。 本文分为三部分，第一部分主要给出图论涉及到的常用概念及某些关于流的已 证结论和猜想，并在此基础上以图论的一般研究方法为主，结合平方图、立方图的 定义及其特有性质，给出g 2 推出3 一n z f 的判定定理以及g 忙3 ) 推出3 - m 猡的 判定定理，其创新方式在于对任何高阶图g 2 ) ，都可以通过去边的方法降为 边数更低的图，然后以其去边图g 为立足点，进而考虑g 伍2 ) 推出3 - m 伊，g 所必需具备的性质。第二部分主要是给出g 2 推出3 - n z f ，其去边图g 所必需具有 的性质，即g 2 推出3 一n z f ，当且仅当g 薯a 。而且，在k = 2 的基础上，给出了 g 。仅3 ) 推出3 一n z f 的推论。第三部分主要给出g 伍3 ) 推出3 一n z f 的证明， 即g 伍3 1 推出3 一n z f ，当且仅当h 薯a 。，其中是g 的任意一个分支。 关键词：平方图；立方图；3 - n z f ；m o d k - f l o w 硕士学位论文 m a s t e r s t h e s i s a b s t r a c t i nt h ep a p e r , w ep r o v et h a tg 2a d m i t s3 - n z fi fa n do n l yi fg 正a m o r e o v e r ， w ep r o v et h a tg o 3 ) a d m i t s3 - n z fi fa n do n l yi fh a 。i nw h i c hhi sa n y b r a n c ho fg ： t h ep a p e ri sd i v i d e di n t ot h r e ep a r t s ：t h ef i r s to n e ，w eg i v et h ec o m m o n l yn o t a t i o n s a n dt e r m i n o l o g i e s ，s o m cp r e v i o u sc o n c l u s i o n sa n dc o n j e c t a r e sa b o u tt h ef l o w s ，o nt h eb - a s eo f w h i c ha c c o r d i n gt og e n e r a lr e s e a r c ht e c h n i q u e so f g r a p ht h e o r y , a sw e l la st h ec o n c c p t i o n so f t h es q u a r eo f g r a p h sa n d t h ec u b eo f g r a p h s ，w h i c hw i l lb eu s e di nt h ep - r o o f i n t h e t h e o r e m t h a tg 2a d m i t s3 - n z fa n dg ( t 3 ) a d m i t s3 - n z f ，i t s i n n o v a t i o nw a yl i e si nf o ra n yh i g h e ro r d e rg r a p h , i tm a yb ed e c o m p o s e dt oag r a p hw h o s e v e r t e x e so re d g e sa r el e s s ，t h e nv i e w i n gt h ec o m p o s i t i o ng r a p hga st h eb a c k i n g ，t h u s w ec o n s i d e rt h ep r o p o s i t i o nt h a tgs a t i s f i e si f a n do n l yi fg ( k 2 ) a d m i t s3 - n z f t h es e c o n dp a r t ，w em a i n l yg i v et h ep r o p o s i t i o nt h a tt h ee d g ed e l e t i n gg r a p hgo fg 2 s a t i s f i e si f a n do n l yi fg 2a d m i t s3 - n z f ，t h a ti s ，g 2a d m i t s3 - n z fi f a n do n l yi f g 叠a ，m o r e o v e r o n t h e b a s e o fk = 2 ，i t g i v e s t h e c o r o l l a r y t h a tg ( _ j 3 ) a d n l i t s3 - n z f t h el a s tp a r t , w em a i n l yg i v et h ep r o o f t h a tg ( k 3 ) a d m i t s3 - n z f ，t h a ti s ， g ( k 3 ) a d m i t s3 - n z fi f a n d o n l y i f 日仨a i n w h i c hhi s a n y b r a n c h o fg k e y w o r d s ：t h es q u a r e o f g r a p h s ；t h e c u b e o f g r a p h s ；3 - n z s ；m o d k - f l o w 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作撇：拿畚1 刚 魄狐阵川日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权 中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 导师签名：孛却从 日期。严易月日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发饥并可按“章程”中的 规定享受相关权益。回童途塞握窒厦迸唇! 旦主生；旦二生；旦三生蕉鱼! 导师签名：锄1 jk 日辄济6 月，日 | 闪日春补 _ ，6厶可午娩胁 者期作日 a_7日春胁 禽 务泳 签 ：者期 作日 硕士学位论文 m a s t e i r s t h e s i s 1 1 常用概念 1 引言 给定图g = o ，e ) ，矿表示g 的顶点集合，e 表示g 的边的集合，i 矿( g 】o ( g ) ) 表 示g 的顶点个数，l e ( g ) i ( e ( g ) ) 表示g 的边的条数。见表示顶点个数为刀的路，q 表 示顶点个数为珂的圈，e 表示任两点之间都有边相连的 阶完全图，g h ，叶) 表示 v l ，v 2 ，v ， 的点导出图，即保持顶点 q ，屹，v ， 以及他们之间连边得到的图， g q ，包，b 表示 巳，吃，气 的边导出图，即保持 q ，巳， 对应的顶点和其 自身得到的图，o ( g ) 表示g 中所有奇点构成的集合，( g ) 表示g 的连通分支个数， ( 肘肘) 表示把吖缩成一点，其余点边均保持不变得到的图( 这样可能会出 现重边) 。如无特殊说明，这里所有考虑的图一般都是简单图，即无重边、无环的 图。 定义1 1 1 设g = 缈，e ) ，任给v v ，与v y 相邻的点对v 的度数贡献为1 ， 特别地，若v 处有环，则每个环对v 的度数贡献为2 。为方便起见，v 的度数简记 为d 。( v ) 。( g ) 表示g 中点的最大度数，j ( g ) 表示g 中点的最小度数。如果g 中 所有点的度数都是偶数，则称g 是偶图。 定义1 1 2 设g = 缈，e ) ，任给v v ，则g ( v ) 表示g 中与v 相邻的点的集合， 即g ) = u l m , e ( g ) 。 定义1 1 3 g i = 以，目) ，g 2 = 以，易) ，定义g l ug 2 = ( k u ，置u 岛) ，称 g iu g 2 为g l 和g 2 的并。 定义1 1 4i j g i = 以，蜀) ，g 2 = 以，e ) ，* g g a g = 为g 1 和g 2 的不交并，即 硕士学位论文 m a s t e r s t h e s i s g , g 2 = ( ku 砭，( 置u 岛) ( 置n 巨) ) 。 定义1 1 5 设g = o ，e ) ，见( g ) 表示g 中度数为打的集合，也可记作圪。 定义i 1 6 设g = g ，r ；e ) 是一个二部图，如果对于任意的“s ，v 仨r ，都有 钾e ，则称g 是完全二部图。若矧= 册，i r l = 一，则简记为k m ，。特别地，当例 = 1 时，称完全二部图k l ，为星，星k i j 也称为爪。 定义1 1 7 设g l ，g 2 是两个p 阶图，若y ( g 。) 和矿( g 2 ) 之间存在一一对应关系， 使对g i 中任一对点，他们在g l 中相邻当且仅当他们的对应点在g ：中相邻，就称g l 和g 2 是同构的，记为g i 兰g 2 ；否则，g l 和g 2 不是同构的，记为g l 鼍g 2 。 定义1 i 8 若肘的点边均在g 中，则称m 是g 的子图，简记m c g ；否则， m 不是g 的子图，简记为m c g 。 定义1 1 9 设g 。= 以，e 。) ，g 2 = 畋，易) 是两个点不交的图，则定义g i + g 2 = ( k u k ，岛u 易u 易) ，这里e = 如i nk ， g e k 。 定义1 1 1 0 设g = 缈，e ) ，若e ，则g e 表示从图g 中丢去占中所有 边得到的图，也可记为g e ；若矿v ，则g 一矿表示去掉v 中的点以及与y 中 点关联的所有边得到的图，也可简记为g v 。 定义1 1 1 1 若已是一个疗圈，记既= k i + g ，称之为轮。特别地，当以= 4 时，= k l + c 4 定义1 1 1 2 设g = o ，e ) 是给定的图，若g 的某些点、边可以排成如下的交错 序列【v ，e ，v j 2 ，e ，v ，气 + 。) ，使边气= 、_ 。( ，= l ，2 ，| i ) ，则称之为联结、和 v 。的一条链，简称h ，v “) 链，点v f l 和v j i + 。称为这条链的端点。我们把这条链记为 v f i 、。若链中的点都是不同的，则称之为初等链。若链中边不同，则称之为 2 硕士学位论文 m a s t e r s t h e s i s 简单链，也称之为路，记为飞飞、v 。若点、边交错序列( v ，v ，气 + 。) 中， 、= 、。，则称之为圈，为v l z v t 2 、以后我们提到的链或圈，除非特别交代， 均指初等链或初等圈。 定义1 1 1 3 在图g = 缈，e ) 中，如果g 中至少有一条“，v 一路，则从“到1 ，的距 离表示“蓟v 的所有路中最短路的长度。若不存在这样连接“，v 的路，则“到v 的距 离为+ ，即如( 甜，v ) = 佃。为方便起见，从“到v 的距离简记为如0 ，v ) 。 定义1 1 1 4 给定图g = o ，e ) ，如果g 中任何两点之间都至少有一条路相连， 则称g 是连通的，否则g 不是连通的。在g 中，其极大连通子图称为g 的连通分支。 定义1 1 1 5 给定图g = o ，e ) ，如果g 是连通的无圈图，p l u 称g 为树。g 中 度数为i 的点称为g 的悬挂点。 定义1 1 1 6 在图g = 缈，e ) 中，若去掉某条边8 会使g 的连通分支增加，则称 e 是g 的一个桥。若图g 不含这样的边，则称g 是无桥图。 定义1 i 1 7 假设d 是g 的定向，称在d 的定向下g 的定向边为弧，记d ( g ) 为 g 中所有弧的集合。v e e ( g ) ，若d ) = 斗v ，则称该定向d 以1 ，为头，以甜为 尾。v v y ( g ) ，称e + ( v ) 为d ( g ) 中以v 为尾的所有弧的集合，e 。o ) 为d ( g ) 中以1 ， 为头的所有弧的集合。设u 矿( g ) ，记i u ，矿( g ) 、( ，l 为d 中u 蛰j v ( g ) 、u 所有有向 弧的集合。 定义1 1 1 8 设d 是g 的定向，且，；e ( g ) j z ，v e e ( g ) ，- k f ( e ) 后， v v e 矿( g ) ，+ ( v ) = 厂0 ) ，一( v ) = ，g ) ，设( d ，) 被称为g 的k - f l o w ，当 睡e + ( y )盹占一( 叶 且仅当 ( e ) = ，( e ) ，v v e v ( g ) ，即 f e 矿( )托r ( v ) f + ( v ) = f 一( v ) 硕士学位论文 m a s t e r s t h e s i s 设( ，y ( g ) ，定义，+ p ) = ，+ ( v ) ，厂p ) = 厂( v ) 。 v e u 眶u 定义1 1 1 9 设d 是g 上的一个定向，是d 上的一个赋权函数，则 ( 1 ) 整数流是g 上赋权函数为整值函数的流。 ( 2 ) 整| i 一加w ，或七一f l o w 是g 上的整流( d ，) ，v e e e ( g ) ，i ，g 】 0 ，则称v 是g 上( d ，厂) 的潮；如果 厂+ ( v ) 一厂( v ) o ，则称v 是g 上( d ，) 的汐。 定义2 1 9 设d 是g 的一个定向，且厂：e ( g ) _ z ，昂e ( g ) 。设是 由把d 中属于磊的弧反向得到的定向，矗定义如下：当p 舞岛时，危= ( e ) ；当 p e o 时，矗= 七一，( e ) 引理2 1 1 0 设g = 缈，e ) ，d 是e ( g ) 上的定向，是d 上的赋权函数，r f ： e ( g ) _ r ，其中r 是实数集。如果( d ，) 有一个潮，或汐，则( d ，) 有一个汐，或 潮。而且，如果厂是一个非负的实函数，则对( d ，厂) 的任何潮u ，都有一条从“到v 的有向路，其中，v 是( d ，f ) 的汐。 证明：设 是( d ，厂) 的潮，由f + 缈( g ) ) = ，缈( g ) ) 知，必存在v 矿( g ) ，使得v 是( d ，) 的汐。不妨设，是d 上的正赋权函数。设【厂主矿( g ) 是g _ k u 至少存在一条 有向路到达的所有点的集合。若v v u 都不是( d ，) 的汐，否则结论成立。由u 定 义知，i u ，v ( g ) w i = 。i ，+ ( v ) 一厂( v ) i _ 厂+ ( v ) - ：- ( v ) - - - ，( e ) o ， v e u - l v ( o ) w 。叫 矛盾。故存在v u ，厂+ ( v ) 一，一o ) o ，即存在( d ，厂) 的汐v ，使得在( d ，) 中有“ 到v 的有向路。 引理2 1 1 1 9 1 设( d ，) 是gm o d k - f l o w ，扇e ( g ) ，则，矗) 也是g 的m o c l k 一加w 。 引理2 1 1 2 q 若g 是一个无桥的简单图，g 推出3 - 加w ( d 0 ，f o ) ，当且仅当 7 硕士学位论文 m a s t er s t h e s i s g 有一个部分胁d 3 一d ，- j - s u p p ( f o ) = s u p p ( d 1 。 特别地，g 有3 一n z f ，当且仅当g 有一个m o d 3 一d 。 证明：必要性。设( d ，厂) 是g 的3 一n z f ，且v p e e ( g ) ，o ( p ) 3 ，并设 易= p e ( g ) l 厂( e ) = 2 。由引理2 1 1 1 知，( 礓，矗) 是一 个 m o d 3 一n z f ，v p e ( o ) ，矗0 ) = l ，这样，是g 的一 ：t m o d 3 一d 。 充分性。如果g 有一个定向d ，且p + ( v ) 1 - 1 e 一( v ) j ( r n o d 3 ) ，v v 矿( g ) 。只需 定义：v e e ( g ) ，厂0 ) = 1 。显然，( d ，厂) 是g 的一个胁d 3 一n z f ，故g 推出3 一 n z f 。 引理2 i 1 3 设g 一，e o e ( g ) ，则g 2 推出3 - f l o w ( d ，f ) ，s u p p ( f ) = e ( g 2 ) 瓴 。 证明：以下对陋( g ) f 数学归纳。 显然，对满足g 2 = 蜀的g 成立。因此，不妨假设p ( g ) i 5 ，d 是g 2 的一个 定向。 设e = x y ，a a x ) = 如( y ) = 3 。于是g 。由两个分支组成，不妨记为g l 和g 2 。显 然g - ，g ：a 。不失一般性，设e ( g 1 ) a 由归纳假设，g 2 推出3 - f l o w ( d ，z ) ， f = 1 或3 其中s u p p ) = 五( g 1 2 ) ) ，s u p p ( 五) = e ( g 2 2 ) p 。只需重合x 和， y 和) ，返回到g 2 中，则可以得到g 2 的3 - f l o w ( d ，f ) ，其中d = d 1 u b ，f = a “，s u p p ( f ) = e ( 0 2 ) 、 。 引理2 1 1 4 如果g 推出胁蹴一加巾，) ，v e e ( g ) ，都有o ，g ) k ， 则存在g 的边子集晶，使得魄，矗j 是一个正整流。 证明：设( d ，) 是g 的非零的胁蹴一f l o w ，0 厂0 ) 0 。由引理2 1 1 0 知，必存在“v ( o ) ，0 ) 一疗0 ) 5 。考虑如下情况： 情况1j 一条路= v i v 2 ，所3 ，v = h ，对某个，2 t 肌一1 且如h ) - - - - 2 ，2 一 k 一 m - 1 ，如“) 2 ，如( v 埘) 2 。显然，v l ，至少有一个三次点。如 果如“) = 3 ，f = l 或埘，设g “) 矿( 己) = 叶，h ”) 显然，g i = g 屹，一l ， 9 4 7 ( 由结论3 ，2 次点不含于任何3 一c i r c u i t ! ) a 由结论1 ，g l 是连通的，故g 1 2 推 出3 - n z f ( d ，z ) 。由引理2 1 1 8 知，p m 2 ：有3 - n z f ( d ，五) 。于是g 2 确；3 - f l o w ( d ，) ，s u p p ( f ) = s u p p ) u s u p p ( 五) ，由结论3 和4 ，占( g 2 ) s u p p ( ，) = v 2 v 1 ， 屹h ”，一i ，一l v 肿”) ，由引理2 1 1 7 知，g 2 推出3 一n z f ，矛盾。 1 5 硕士学位论文 m a s t er ，s t h e s i s 情况23 1 m - - c i r c u i t c = v l v 2 v 3 v 胂v l ，m 5 ，如“) = 2 ，i i m - 1 ，如 ( v 册) = 3 ，v = v ，对某个f ，1 ，s 肌一1 。假设v o 心( v 胛) 矿( c ) ，由结论i ，如( v 0 ) = i 。由引理2 i 1 8 知，g 2 推出3 一n z f ，矛盾。 结论6 设p = 砂e ( g ) ，比( x ) = 如( y ) = 3 ，则p 含于一个长度为3 或4 的圈 里。 若不然，假设g l 是通过g 去掉边e ，增加一个新点y 7 和新边砂7 得到的。因为 g 不含2 次点且如( y ) = 2 ，则g lg a 7 由结论1 知，e 不是g 的割边a 由( 1 ) 知， g 1 2 推出3 - n z f ( d ，石) ，重合y 和y 7 ，得到的g 2 的3 一：o w ( o ，正) 仅失去两条边矾， x y 2 ，g ( y ) = x ，y t ，儿 ( 砂不可能含于g 中一个3 或4 的圈中) ，由引理2 1 1 7 ， g 2 推出3 一n z f ，矛盾。 结论7 搬矿( g ) ，如( x ) = 3 ，j g o ) n 巧i 2 。 若不然，i e 谚t u = u i ，u 2 ，岣) = g ( x ) n z , 。设g l = g 、p ) ，由结论i 知，g l 是 连通的。因为g 不含2 次点，所以g l a 7 ，e g t 2 推出3 一：z f ( d ，f ) ，由结论6 ， x m ( 1 i 3 ) 含于一个长度至多为4 的圈里。考虑如下三种情况。 情况1g 明至少含两条边。 假设“。“2 ，啦地e ( g ) ，若蚱g ) 、u ，j = 1 或3 。若7 = 蚝7 ，则g 2 u u b ，x ) 兰如，由引理2 1 1 7 ，g 2 推出3 一n z f ，矛盾；若；吩，则g 地7 均吻蚝吩，】 是一条4 一p a t h ，由引理2 1 1 7 知，g 2 推出3 - n z f ，矛盾。 情况2g 【明仅含一条边。 假设“。“：e e ( g ) ，由结论6 知，每条碱含于长为3 或4 的圈中( i = 1 ，2 ，3 ) ，故 1 6 硕士学位论文 m a s t er sn i e s i s 我们设z ( g ( 甜：) n g ( 吨) ) x ) 。显然，g = g 2 ( ，u x ，z 兰毛，设坼g ( 坼) ( u u ：) ) ，i = 1 或3 。若。吩，由引理2 1 - 1 2 1 1 1 ，存在g 1 2 上的3 一dd 1 ，f fs u p p ( d 1 ) = e ( g 1 2 ) 。设q ( 屹) = 的 2 ，d l ( 均z ) = 吩斗= ，沿着m 甜：删。，吩弘做圈 操作，得到g 2 上的部分3 一d3 2 ，使s u p p ( d 2 ) = s u p p ( d 1 ) u 矾，x u 2 ，i l l 3 ，材 。由 g 2 的结构知，存在形( 1 ) 釜睨g 2 ，u t u 3 是w ( 1 ) 的中心边，由引理2 1 1 7 ，存在g 2 _ t 的3 - d3 3 ，使s u p p ( d 3 ) s u p p ( d 2 ) u u , u , 。类似地，存在g 2i 拘3 - dd 4 ，使 s u p p ( d 3 ) c - s u p p ( d 2 ) u 坼吨 。同理，存在g 2 雕 3 - db ，d f - s u p p ( d s ) c _ s u p p ( d 4 ) u “码 ，o os u p p ( d ，) = e ( g 2 ) ，由引理2 1 1 2 【1 】，g 2 推w , 3 - n z f ，矛盾。若 = 屿，类似可证。 情况36 u 】不含边。 设毛( g ( q ) n g ( 毪) ) x ) ，乞( g ( 坼) n g ( 蚝) ) 工) ，设g j = g 、 工m ， 则g ：仨a ，且g 2 2 推出3 一n z f ( d ，石) 。显然，e ( g 2 ) 、s u p p ( z ) = x m 。因为x 五( 矿) e ( g “。，u 2 ，u 3 ，x ，刁) 】) ，w 兰，x 是它的中心，由引理2 1 1 7 ，g 2 推出 3 一n z f ，矛盾。 最后，由结论2 ，5 ，7 知，v v e v ( g ) ，如( v ) = 1 或3 ，每个3 次点至多与两个 3 次点相邻。因此g 暇】是一条路或一个圈，从而g r - c i r c u i tx o x , x r - i ，在此 基础上增加薯虬( 0 _ i r - - 1 ) ，虬吩o ，) 或路而一增加而h ( 1 f p 1 ) ，k 巧( f ，) 得到，显然后者是4 7 中的图。由引理2 1 1 8 知，g 2 推出3 - n z f ，矛盾。 推论2 1 2 0 若艿( g 2 ) 4 ，则g 2 推出3 一n z f 证明：反证法。若g 2 不推出3 一n z f 。则g 彳，。 1 7 硕士学位论文 m a s t er ，st h e s i s i 当g 兰c 4 时，万( g 2 ) = 3 ，矛盾。 2 当g a 时，必存在悬挂点v ，使得略：o ) = 3 ，从而6 ( g 2 ) 曼3 ，矛盾。 3 当g 岳a ，g 若e 时，由4 7 定义知，必然存在g a ，g 是由g7 增加悬挂 点连边得到的，于是必存在悬挂点v y ( g ) = y ( g ) ，使得叱，( v ) = 吒。( v ) = 3 ，从 而占( g 2 ) 3 ，矛盾。故当万( g 2 ) 2 4 ，则g 2 推出3 一n z f 。 推论2 1 2 1 若g 是一个连通图，则g 3 推出3 - n z f ，当且仅当g 正a 。 推论2 1 2 2 若g 是一个简单图，则g 3 推出3 - n z f ，当且仅当g 7 萑a ，其中 g 是g 的任一分支。 硕士学位论文 m a s t er s t h e s i s 3 立方图及推广 3 1 处处非零三流的立方图 定义3 1 1 g 3 = g u w 1 2 如( ”，v ) 3 ，“, v e y ( g ) ，由定义，g 3 = g 2 u w l 吃( “，v ) = 3 ，“，v 矿( g ) 。 定理3 1 2 若g 2 ( ) v ( g ) l - - 5 ，u ( g ) = 1 ) 推出3 一n z f ，则g 3 推出3 一n z f 。 证明：设g 2 ( p ( g ) f 5 ，u ( g ) = 1 ) 推出3 一z f ( d ，) 。由定义知，g 3 - - g 2 u w l 吃( v ) = 3 ，“，v 矿( g ) ) 知，只需考虑e 4 = e ( g 3 ) 、e ( g 2 ) 。设e = 圳，显然， 如( “，v ) = 3 。设p = v l v 2 v 3 v 4 是a 中长为3 的路，其中，材= v 1 ，v = v 4 。由l 矿( g ) i 5 ， ( g ) = l ，设v 7 矿( g ) 、矿( p ) ，考虑如下两种情况。 情况i 若v v 2 e ( g ) ，由g 3 的构造知，存在形= - w 1 g v l ，v 2 ，匕，v 4 ，v 7 ) ，p 是矿1 的中心边，由引理2 1 1 7 ，则“e ，厂) c 懈存在，即存在g 3 上的3 一f l o w ( d ，厂) ，使得s 印p ( ，) u e 量s u p p ( f ) 。着v k e ( g ) ，类似可证。 情况2 v v l e ( g ) ，同上，存在啊兰矿量g “，屹，v 3 ，v 4 ，v ，p 是矿的中 心边，由引理2 1 1 7 ，则( 扣 ，) 一c 砌，理譬存在，a p ；融g 上的3 一f l o w ( d 。，厂) ， 使得s u p p ( ) u p )s u p p ( f ) 。若v k 占( g ) ，类似可证。 定理3 1 3 若g 4 7 ，i 矿( g ) i 5 ，( g ) = 1 ，则g 3 推出3 - n z f 。 证明：1 若g a ，由a 定义知，v v 矿( g ) ，如( v ) = 1 或3 ，由定理1 2 1 知， p ( g ) j - = o ( m o d 2 ) ，以下用数学归纳法证明。 当i 矿( g ) l = 6 时，g 3 兰瓦，显然结论成立。 1 9 硕士学位论文 m a s t e r st h e s i s 假设当矿( g ) = 七6 时，结论成立。 当y ( g ) = 七+ 2 时，由彳定义，必存在v 矿( g ) ，使o ) = “，屹，码 ，吃“) ：1 ， 2 1 或2 ，如以) = 3 。：t r i g = g 、“，v 2 ，显然，g 一。由归纳假设，g , s 推出 3 一n z f ，由定理1 2 4 啪，g , sm o d 3 一d d ，使s u p p ( d ) = 占( g ，3 ) 。显然，e ( g 3 ) 、 e ( g 。) 2 ，w 2 ，v l v 2 ，h b ，h 0 ，h b ”，鸣v 3 ，v 2 v 3 ，v 2 v 3 ” 。对w 1 v ：作c 咖“f f d p p 删幻行， 得到g 3 上的部分3 一d q ，使s u p p ( 日) = s u p p ( d ) u w l ，1 ，v l v 2 。设b ( 吩v 3 ，) ：码 斗，d l ( 吩b 。) 2v 3 _ ，对吃坞v 】，v 3 v 3 屹作c i r e u t 一印卯删鲫，得到g 3 的部分 3 一d d 2 使8 u p p ( d 2 ) = s u p p ( d 1 ) u “v 3 ，v l 吃。，o ，b o 。设d 2 ( v l v 2 ) ：v l 斗v 2 ， 对啊v 2 v ，作咖c “豇一o p e r a t i o n ，得到g 3 上的部分3 一d b ，使s u p p ( d 2 ) ：s u p p ( d 1 ) u 、v 3 7 ，v l v 3 ，v 2 v 3 ，屹 a 设d 2 ( v l v 2 ) = v i v 2 ，对v 。v 2 作c 咖“打一叩溯砌忍，得 g 3 的3 一d ，使得s u p p ( d ) = 占( g 3 ) = e ( g ”) u q ， ，：，h v 2 ，v l v 3 ，h b ，h b ”，v 2 v 3 ， 屹屹7 ，v 2 v 3 ” 。由定理i 2 4 1 4 1 ，g s 推出3 一z f 。 2 若g 彳，但g 雀彳，由的定义，不妨设g = g u h iv 1 2 ，v 2 。，e 2 ， g 7 4 ，且，巧：一“) ，如，“，) = 如以：) = 】，：1 ，。由1 知，g ，推出 3 一z f ( d ，厂) ，使得s u p p ( ) ；e ( g 6 ) 显然，g 3 = g 3u v 。v m ，v 。v ，： 。设u g ，“) h ，h ： ，g ，“，) = ，7 ，”，v , i ，由g 3 的构造知，存在睾( 1 j g g r v l ， v i l ，v l z ，y 1 3 ，h 3 j j ，h - v l ：是形o 的中心边，由引理2 1 1 7 知，“v l 。h 2 ) ，厂) 一曲册夥存 在，即存在g 3 上的( d l ，石) ，使得s u p p 研) = s u p p ( f ) u v 。h ： 。若 v 2 ，v ，h ： 量8 u p p ( 彳) ，则e ( g 3 ) 2 e ( g 。) u v l v i z ，q 。t ： = s u p p ( ) u q ，q ：，v ，一： s u p p ( 石) e ( g 3 ) ，即s u p p ) = e ( g 3 ) ，于是g 3 推出3 一n z f 。不妨设s u p p ( 石) n 硕士学位论文 m a s t e r s t h e s i s v 2 。，v f lv ，： = 矿，由g 3 的构造知，存在呒兰2 g v 2 ，v 2 l ，v 2 3 ，o ) ，v 2 3 乞，(v2)v2。，2，6，v23)：k：，v：，”，v：，v2lv2：是(2的中心边，由引理2117v2 v211 7 乞，“) v 2 l ，： ，。，：，) = p 。，v 。，v ： ，v 2 1 是( 2 ) 的中心边，由引理 知，( “。) ，z ) 一曲。馏e 存在，即存在g 3 上的( d 2 ，五) ，使s u p p ( f 2 ) = s u p p ( f 1 ) u v 2 。 ，着 嘞，v ，。叶： s u p p ( 五) ，贝l js u p p ( f 2 ) = e ( g 3 ) ，于是g 3 推出3 - n z f 不妨设 v 3 。v 3 ：，v h v t ： n s u p p ( 五) = 声，由l e ( g 3 ) 、e ( g 。) i 5 时，若g 诺a ，由定理2 1 1 9 ，g 2 推出3 - n z f 。由定理3 1 2 ， g 3 推出3 一n z f 。若g a ，由定理3 1 3 ，g 3 推出3 一n z f 。 当矿( g ) i - 3 时，易知g 3 推出3 - n z f 综上所述，g 3 推出3 一n z f ，当且仅当v g g 时，都有g 芒a ，其中，g 是 g 的任意一个分支。 3 2 立方图推广 定义3 2 1 g = g u u v 2 - d o ( “，v ) s 七，“，v 矿( g ) ，由定义，g = g 3 u w 2 1 硕士学位论文 m a s t e r ，st h e s i s 1 4 如( “，v ) s 七 v 矿( g ) ) 。 定理3 2 2 若g 是一个连通图，则g 3 ) 推出3 一n z f ，当且仅当g g a ” 证明：必要性是显然的。 充分性。：g g g a ”，由定理3 1 4 知，g 3 推出3 - n z f ( d ，f ) ，使s u p p ( f ) = e ( g 3 ) 。当j j 3 时，g 2 = g 3 u 删1 4 s 如( “，v ) _ i ) 。只需考虑p g = g 飞g 3 即可， 不妨设g = g g 3 = 巳，巳，e t ，其中，q ；“，叶，1 s j ta 设如( 地，v 1 ) = ，3 ，s 七，从而存在路w 2 w t ，w o = 地，= v l 。由g 3 的构造，存在兰形( 1 ) g ，“。v 】是形