（应用数学专业论文）关于唯一泛圈有向图.pdf

致谢 在三年的学习研究中，我的导师施永兵教授给与了我无私的帮助和指导，在平时生 活中点滴的关心和学习中严谨的教导下使我打下扎实的数学基础，促进了我的不断进 步本文是在旋老师的悉心指导和帮助下完成的施老师在繁忙的工作中，多次对我进行 指导，不断提出新的思路与方法我才得以完成今天这篇论文没有他的教导和帮助。 也不会有今天我的成绩在此对我要对我的导师施永兵教授表示深深的敬意和感谢 此外，还要感谢所有曾在学习上给予我指导和帮助的老师和同学，还有数理信息学 院为我们提供了这样一个良好的学习和生活环境，为我们的学习和研究提供了良好的 硬件和软件环境，在此一并致谢 关于唯一泛圈有向图 王明磊 ( 上海师范大学数理信息学院，上海2 0 0 2 3 4 ) 摘要：1 9 7 3 年，r c e n t r i n g e r 提出了确定唯一泛圈图的问题，即确定简单 图g 使得对312 p 的每个j 恰有一个长为2 的圈本文将e n t r i n g e r 这个问 题推广到定向图中，研究了唯一泛圈有向图的若干问题一个唯一泛圈有向 图是一个定向图，且对3 茎l 茎”的每个f ，它恰好有一个长为l 的有向圈。 这里的v 表示有向图的顶点数设d 是有向图，d 中不在有向h a m i l t o n 圈上 的弧称为d 的有向桥，用b ( d ) 或b 表示d 的有向桥的集合若d 是最大唯 一泛圈有向图且b 是独立的，则称d 是包含独立桥的最大唯一泛圈有向图 用p ( v ) 表示具有”个顶点包含独立桥的最大唯一泛固有向图的数目用，( 一) ( 9 ( r ) ) 表示具有v 个顶点的唯一泛圈有向图最大( 小) 可能的弧数本文的 主要结果是：( 1 ) 通过构造几类唯一泛圈有向图证明了，( v ) = 2 ”一3 ( 2 ) 对 p 4 ，证明了p ( v ) s2 4 ( 3 ) 同时得到了g ( v ) 的上界和下界，即对p 3 ， 9 ( p ) + ：o 啦p 一2 ) ) 和对p 兰4 ，9 ( 功p + 詈) _ r 1 并且对每个3 兰p 2 0 ，确 定了g ( f ) 即若p ( v 1 3 兰p t 4 u 1 9 ，2 0 一 9 ，1 3 ) 时，9 ( p ) = p + t 0 9 2 ( 一2 ) 以及当p p 1 1 5 墨p 墨1 8 u 9 ，1 3 时，g ( p ) = p + l o 啦p 一2 ) + 1 关键词：有向图；有向圈；唯一泛圈有向图 2 1 引言 1 9 7 3 年，r ce n t r i n g e r 提出了确定唯一泛圈图的问题，即确定简单图g 使得对 3 2 p 的每个f 恰有一个长为f 的圈( 见文【1 】，芦2 4 7 ，问题1 0 ) 文 2 ，3 】中较系统地 研究了这个问题并得到一些结论本文将e n t r i n g e r 的这个问题推广到定向图中研究， 得到了摘要中所述的一些结果 2 定义与记号 本文讨论的有向图都是定向图，即通过给简单图的每条边都赋一个方向得到的图 一个唯一泛圈有向图是一个定向图，且对3 fs 的每个z ，恰好有一个长为z 的有向 圈，这里的v 表示有向图的顶点数由于每个唯一泛圈有向图恰好有一个有向h a m i l t o n 圈，所以我们约定本文讨论的有向图都恰有一个有向h a m i l t o n 圈，且用g 记之设d 是有向图，用v ( d ) 和a ( d ) 分别表示d 的顶点集和弧集为了方便，我们把有向图的 有向h a m i l t o n 圈g 看作平面上的一条j o r d a n 曲线，把d 中不在g 上的弧全画在d 的 内部，且称这些弧为d 的有向桥( 简称桥) 用b ( d ) ( 或b ) 表示d 的桥的集合若 b b ( d ) ，则b 的头和尾称为b 的接触顶点设b 和b 是d 的两条有向桥若存在四个 不同的顶点u ，口，u 和u 7 ，使u ， 是b 的接触顶点，u ，一是的接触顶点，并且 这四个顶点以循环顺序u ，u 7 ， ，w 7 出现在g 上，则称b 和6 ，是偏斜的若b 和6 ，不 偏斜，则称b 和6 ，是平行的若图d 中不存在两条桥是偏斜的，则称d 为外可平面有向 图若d 是外可平面有向图且添加任何一条弧都会使之变成非外可平面有向图，则称 d 为极大外可平面有向图 令b b ，则d 恰好包含两个圈( 不必有向圈) ，这两个只包含桥b 不包含b 中其余 桥的圈被记为g ( b ) 和- c ( b ) 令c 7 是d 的一个圈( 不必有向圈) ，则g 将平面分成三部 分，即c 7 的内部、的外部和c 自身用i n t c 表示的内部，e x t c 表示的外部 设s 是d 中的一些桥的集合，且s 中没有两条桥是相互偏斜的，则称s 是平行的 特别地，旧= l 时也称s 是平行的 令b l 和6 2 是s 中的两条平行桥，若存在b s 使得6 l i n t c ( b ) 且b 2 e ：z t c ( b ) ， 则称b l 和6 2 在s 中是独立的，否则称为相关的若平行桥集合s 中没有两条桥是独立 的，则称s 是相关的特别地，l sj = l 时也称s 是相关的若至少包含三条桥的平行桥 集合s 中没有三条桥是相关的则称s 是独立的特别地，平行桥集合s 满足i s i 2 时也称s 是独立的 根据上述定义，当平行桥集合s 满足i s 2 时，s 不仅独立而且相关特别需要 指出的是：当s 平行且满足i s l = 2 时，我们可以说s 是独立的，但不可以说s 中的两 条桥是独立的 我们约定h a m i l t o n 圈c 的方向为顺时针方向e 上沿顺时针方向的有向路( u l ， 2 ) 记为g u 1 ，1 1 2 】 4 3 几个关于礼( s ) 的命题 对s 口，用国表示包含s 中所有桥且不包含b s 中任一桥的有向图的集合 用n ( s ) 表示c s 中有向圈的数目定义岛= c ) ，从而n ( 0 ) = 1 对s 且且i s i = 1 ， 显然n ( s ) = 1 令a i = s 且，i s l ：i 礼( s ) ( i = 1 ，2 ，j 日f ) ，则a o = 1 ，a l = l b 对s b 且| s = i 1 ，则c s 中的有向圈称为i 桥有向圈若i b | = 七，则显然d 中存在r 个1 桥有向圈 令b 1 和b 2 是两条平行桥。若存在g 上的某条非平凡的有向路尸使得b 1u p u6 2 构 成一条有向路或一个有向圈，则称6 l 和k 是关于c 同向的( 简称同向) 否则6 l 和幻 是非同向的 以下两个命题显然成立 命题3 t设s b 且i s i = 2 若s 中两条桥是同向的，则n ( s ) = 1 若s 中两条 桥是非同向的，则n ( s ) = 0 命题32 设s b 且l s l 3 若s 是独立的，则n ( 司= 0 著s 是相关的且s 中 任两桥是同向的则n ( s ) = 1 命题3 3 对任意s b n ( s ) s l 证明：对旧曼1 ，命题显然成立令f s l 2 ，若s 中存在三条桥关联于同一顶点，则 显然n ( s ) = 0 因此假设s 中不存在关联于同一顶点的三条桥设i s l = t ，则s 中t 条桥 的2 t 个接触顶点。1 ，忱， n = ”o 按顺时针方向出现在g 上( 对于t 0 ，1 ，2 亡一1 ) ， 我们允许啦= 仉+ 1 ) 令最一c h ，轨+ l 】是g 上的有向池，”+ 1 ) 路，i = 0 ，l ，2 t 一1 ( 注意：若q = q + l ，则只= 仇，即只是平凡有向路) 若c s 0 且e 7 仍，则必 然恰好包含两条相继有向路只和只+ l 之一，对i = o ，1 ，。2 一2 ( 否则或者g 7 不包 含关联于w i + 1 的桥或者g 上的顶点哦+ 1 关联于g 上至少三条弧，矛盾) 由此推出或 u ：l p 2 一1 g 7 或u 一- i p , 2 tc 令d 1 = s u ( u 甚1 p 2 i 1 ) 和工) 2 = s u ( 叫三6 岛t ) ，则d l ， d 2 都是d 的有向子图显然c 7 一d 1 或c = d 2 由于s 中的元索都是有向桥，每条 有向桥的方向是唯一确定的，因此d t 和d 2 中至多只有1 个是有向固，因此l c 引l 即 礼( s ) 1 口 用m ( d ) 表示有向图d 的有向圈数，用9 ( v ) 表示有”个顶点的唯一泛圈有向图的 最小弧数 定理3 1设图d 具有p 个顶点2 + 七条弧的有向h a m i l t o n 图，则惫+ l m ( d ) 2 证明：显然m ( d ) = 冬。啦因为( 2 0 = 1 且a l = ，所以m ( d ) = 1 + + 叁2 a i l + k 由命题3 3 可知。t = s 且，l s i = ；n ( s ) ( ：) 因此m ( d ) = 挥koa i 兰江ko ( ：) = 2 口 定理3 ，2 设图d 具有v 个顶点+ k 条弧的唯一泛圈有向图，贝4 + l 0 9 2 ( 一2 ) 曼 a ( d ) 兰2 v 一3 这里扛表示不小于z 的最小整数 证明：若d 是具有v 个顶点的唯一泛圈有向图，则由定理3 1 可得七+ 3 曼p 曼2 + 2 困此 l 0 9 2 ( 2 ) ) ksp 一3 ，故+ l o g , 2 ( p 一2 ) ) a ( d ) i 茎2 一3 口 5 4 最大唯一泛圈有向图 具有”个顶点和最大可能条弧的唯一泛圈有向图称为v 个顶点的最大唯一泛圈有 向图，用f ( v ) 表示其最大可能的弧数 定理4l 对p 3 ，( p ) = 2 v 一3 证明：如下构造一个具有p 个顶点和v 一3 条桥的最大外可平面有向图d ：令 v ( d ) = u l ，u 2 ，u 。) ，c = v l 2 u 。u l 是d 的有向h a m i l t o n 圈选择g 上两条点不交 的路p 1 、p 2 满足y ( p 1 ) uy ( p 2 ) = y ( d ) ，添加v 一3 条尾在y ( p 1 ) 中、头在y ( p 2 ) 中的互不偏斜的桥显然，对任意s b 且i s i = 2 ，s 中的两条桥不同向，故 n ( s ) 一0 ；对任意s b 且ls 3 ，因为s 是独立的，故礼( s ) = o 因此d 中恰好 有l 启i + 1 = p 一3 + 1 = p 一2 十有向圈由于这些有向圈的圈长都不同，所以d 是一 个唯一泛圈有向图且a ( d ) = v + v 一3 = 2 v 一3 因此，( ) 2 v 一3 又由定理3 2 得 ，( p ) s2 v 一3 ，故，( y ) = 2 v 一3 口 若d 是最大唯一泛圈有向图且b 是独立的，则称d 是包含独立桥的最大唯一泛圈 有向图用p ( v ) 表示具有v 个顶点包含独立桥的最大唯一泛圈有向图的数目 定理4 2 对4 ，p ( v ) 2 4 证明：令d 是包含独立桥的最大唯一泛圈有向图，显然l b i = 一3 且b 是独立的 对p = 4 ，定理显然成立对兰5 ，令b l ，幻，b 一3 为d 的1 1 3 条桥，6 1 在有向3 圈 上且b i 与b i 一1 相邻对每个 = 2 ，3 ，p 一3 显然此时饥与b i 一1 位于d 的一个3 圈( 不 一定有向圈) 上，因此k 与b i 一1 只有两种可能的位置关系：b l 与b i l 的头位于同一顶 点或尾位于同一顶点敌可推得至少存在2 4 个包含独立桥的最大唯一泛圈有向图， 即p o ) 2 ”一4 口 5 最小唯一泛圈有向图 具有v 个顶点和最小可能条弧的唯一泛圈有向图称为个顶点的最小唯一泛圈有 向图，用9 ( p ) 表示其最小可能的弧数 定理5 1 对3 ，9 0 ) p + z 卵2 p 一2 ) 证明：由定理3 2 直接推得口 定理5 - 2 对4 ，9 ( p ) 兰+ ；) 一1 证明：当为偶数时，构作有向图d 1 使v ( o a ) = f u l ，q j 2 ， 且a ( d 1 ) = ( ( 让，v , + 1 ) l i = 1 ，2 ，v 1 ) u ( v ，口1 ) ) u “砘，t k ) 忙= 2 ，t 2 ) u “仇， 1 ) ) ，其中 = 字显然对每个 = 2 ，3 ，t 一1 ，d 1 恰有一个长为i + l 的有向圈仇 l u 2 - 仇，且 对每个i = 2 ，3 ，t 一1 ，d l 恰有一个长为i + t l 的有向圈毗”h l ”i u 2让仇因 此d 1 为唯泛圈有向图且i a ( d a ) i = ( p 1 ) + 1 + ( 字一1 ) 十l = p + ；一l = + ( ；) 一1 6 当p 为奇数时，构作有向图0 2 瞳r ( d 2j = u l ，0 2 ，) 且a ( d ! ) = ( t 1 ，2 ： ，p 1 ) u ( ( t _ ，j u “、t - t ) i t = l 2 2 uf ( 讪+ ll ，2 ) ) ，其中t = 然别每个 = 2 、3 ，fl ，d 2 恰有一个长为i + 1 的有向圈l ，一，h l z ，2q ”f 个i = l ，2 ，o l ，d 2 恰有一个长为 + t 的有向圈t - u + 1 fj 。t 7 i ur 唯一泛圈有向图且i a ( d ) = ( p1 ) + l + 字+ 1 = v + 字l = + 等) 一l 9 ( ) + ；) 1 口 定理53 对3 s8 ，9 ( p ) = + ( 1 0 9 2 ( v 一2 ) ) 1 z + 1j i = 掣显 且对每 故d 2 为 所以， 证明：由于有向3 圈恰为一个唯一泛圈有向图，故9 ( 3 ) 兰3 又由定理5 1 得g ( 3 ) 3 ， 所以9 ( 3 ) = 3 根据定理5l 和定理5 2 对= 4 ，5 6 ，7 ，8 ，9 ( p ) = v 十 j o 船( 一2 ) ) = v + 差 一1 口 为了确定9 ( 9 ) 需要引入下述两个引理 引理5 1 对任何有向图d ，若s b 由一对相互偏斜的桥组成，则n ( s ) = 0 证明：仿照命题33 的证明可知d 1 和d 2 均不可能为有向图，因此n ( s ) = 0 口 引理5 2 对任何有向图口设s b ，若l s l = 3 ，s 中存在一对相互偏斜桥且 n ( s ) = l ，则对任意s 1cs 且i s lj = 2 ，有n ( s 1 ) = 0 证明：设s = o ，b ，c 且o ，6 是一对偏斜桥，可以分为三种情况 情形1 s 中恰有一对偏斜桥不妨设n = ( “， ) ，b = ( ，”7 ) 且“，u 7 ， ， 按顺时针方 向出现在有向圈g 上显然此时必有c = ( ，) ( 见图l ( a ) ) 易知此时o ，c 非同向。b ，c 也非同向，而a , b 是相互偏斜的因此由命题3l 和引理51 知，此时引理成立 情形2 s 中恰有两对偏斜桥不妨设。与b ，c 都偏斜容易验证当6 ，c 没有公共端点 时，n ( s ) = 0 因此为使n ( s ) = 1 必有b ，c 有一个公共端点，且n = ( u ， ) ，6 = ( “，u ) ， c = ( ，z ) 使 ，u ，z ，u ，按顺时针方向出现在g 上( 见图l ( b ) ) 易知6 ，c 非同向，且d 与b 偏斜，o 与c 偏斜由命题3 1 和引理5 1 知，此时引理成立 情形2 - s 中任两桥都偏斜根据命题3 3 ，仅有一种情形( 见图1 ( c ) ) 由引理5 1 推出引理成立口 i l ) 【h lf cj 图没有2 桥有向圈的有向图 定理5 4 9 ( 9 ) = 1 3 证明：南定理51 知9 ( 9 ) 1 2 ，由定理52 知口( 9 ) 11 3 因此只要证9 ( 9 ) 1 2 ，即 证不存在9 个顶点1 2 条弧的唯一泛圈有向图用反证法，假设这样的有向图存在，即d 7 为9 个顶点1 2 条弧的唯一泛囤有向囝，则显然甘i 二3 且( d ) = 7 。可分以下阿种情 况讨论 情形1d 中存在一对偏斜桥。 情形ll 凡( b ) = 1 南引理5 2 知，对任意scb 且s l = 2 ，有凡( _ s ) = 0 ，故 n 2 = 0 从而m ( d ) = “o + n l + a 3 = 1 + 3 + l = 5 7 ，矛盾 情形l2n ( b ) = o 由引理5l 知，存在scb ，i s i = 2 使扎( s ) = 0 ，故a 2s2 从 而m ( d ) = 。o + a l + a 2 1 + 3 + 2 = 6 7 ，矛盾 情形2d 中没有偏斜桥 情形2 1 _ b 是相关的 情形2 1 _ 1b 中任两桥同向此时a 2 = 3 ，a 3 = 1 ，战m ( d ) = e 拉3o 。= l 十3 + 3 + 1 = 8 7 ，矛盾 情形2 1 2b 中存在两条桥非同向显然此时b 中至少有两对桥非向向因此 n 2sl ，故m ( d ) 曼1 + 3 + 1 + l 一6 7 ，矛盾 情形2 2b 是独立的显然此时至少有一对桥非同向，故a 2s2 又由命题3 2 知 几( b ) = 0 ，即a 3 = 0 ，故m ( d ) 1 + 3 + 2 = 6 7 ，矛盾口 阱下我们确定当1 0 茎p s2 0 时的9 ( ) 定理5 5 对p l o ，1 1 ，1 2 ，1 4 ，1 9 ，2 0 。9 ( p ) = v + l 0 9 2 ( v 一2 ) ) 证明：由定理51 可知口( p ) p + g 0 9 2 ( 一2 ) ，并且对 1 0 ，1 1 ，1 2 ，1 4 ，1 9 ，2 0 已 经找到了具有y 个顶点和恰好v + l 0 9 2 ( u 一2 ) ) 条弧的唯一疰圈有向图( 见图2 ) ，因此 定理成立口 v = 1 0v = 1 l v = 1 2 v = 】4 1 ，：l9 v = 2 0 图2 六个唯一泛固有向图 定理5 6 对 1 3 ，1 5 ，1 6 、1 7 ，1 8 ) ，9 ( ) = p + f 0 9 2 ( p2 ) + 1 8 证明由定理5i 可知9 ( p ) ”十 f 叼2 ( 一2 ) 。假设对p 1 3 ，1 5 、1 6 ，1 7 ，1 8 ) 1 目f7 ，) = p 十f l 。9 2 ( 一2 ) ) ，即存在v 个顶点+ f o 驰( 一2 ) ) 条弧的唯一埋固有向图，则显然 l 引： z o 观( 一2 ) ) = 4 。根据定理61 ( 下一节) ，当p 1 3 ，1 5 、1 6 ，l i ) 时m ( d j 2 ， 与存在v 个顶点4 条桥的唯一泛固有向图矛盾当j = 1 8 时，虽然存在有向图d 满足 m f j _ ) 1 = = ：2 = 1 6 ，但在这种情形下b 是相关的且b 中任两桥同向此时显然没有有向 3 圈，又与存在1 8 个顶点4 条桥的唯一泛圈有向图矛盾因此当p 1 3 ，1 5 ，1 6 、1 7 ，i s 时9 ( p ) 1 + f o 卯( v 一2 ) ) + 1 由于已经找到当 1 3 ，1 5 ，1 6 ，1 7 ，1 8 ) 时具有个顶点 v + f 2 0 驰( 一2 ) ，+ 1 条弧的唯一泛圈有向图( 见图3 ) ，所以定理成立口 1 1 = 1 3 v = 1 5 v = 1 7 v = 1 8 图，五个唯一泛圈有向匿 6 具有4 条桥的有向图的有向圈数 v = 1 6 引理6 l 令d 是具有4 条桥的有向图若b 中存在一对相互偏斜的桥，则m ( d ) 墨1 0 或m ( d ) = 1 2 证明：可分为两种情形讨论 情形la 4 = l ，即n ( b ) = 1 情形l - 1 a a 0 令s 口，s = b l ，6 2 ，h a 满足n ( s ) = l ，g s 中的囵为c 1 假设 s 中不存在相互偏斜的桥，则显然s 是相关的若s 中存在两条桥不同向，则c l 必为有 向3 圈，故佗( b ) = 0 。矛盾因此s 中的任两条桥同向令b s = f 如 珏，”是扎的 接触顶点若b 4 只与s 中的一条桥相互偏斜，不失一般性令 y ( 岛) ，y ( q ) ，则 显然n ( b ) = 0 ，矛盾若b 4 与s 中的两条桥相互偏斜，则u ，u v ( c i ) ，得到n ( b ) = 0 矛盾因此s 中必存在一对相互偏斜的桥南引理52 可知存在三种可能( 见图1 ) 。由 于n ( 日j = 1 ，断以6 4 的两个接触顶点必须同时包含在g n g l 的某段有向路中，且b 4 与 c 和g l 同向根据引理52 的三种可能得到四种墒足上述要求的有向囝( 见图4 ) 今 b ， b l ，b 2 ，b a ) 且b b7 ，s l = b ，岫) ，则显然或者b 与b 相互偏斜、或者5 1 是独 9 互的h ；t 此推出n ( s 1 ) = o 从而a 3 = 1 i _ j 弓1 理52 。f 得到对任意s7 s 且| s l = 2 礼( s 7 ) = 0 ，故n ：s3 。因此 l ( d ) = e 名on 。1 + 4 + 3 + 1 + 1 = 1 0 。 图4四种图 情形1 2 a 3 = 0 情形l2l b 中至少存在两对相互偏斜的桥由引理5 1 ，a 2 曼4 因此m ( d ) s 1 - t - 4 + 4 + 1 = 1 0 情形12 2 b 中恰好存在一对相互偏斜的桥不失一般性令b l 与b 2 相互偏斜， 则显然存在位于g 上的有向路p 满足p = b lu p ub 2 仍为有向路令u ，口分别为 p 的起点和终点由于n ( b ) = l ，所以b 中其余两条桥必构成一条长为2 的路u u 且 w v ( c ) ( 见图5 ) 由此推出a 2 = 0 ，从而m ( d ) = o o + 0 1 + 瓤= l + 4 + 1 = 6 1 0 图5m ( d ) = 6 情形2 啦= 0 ，即n ( b ) = 0 情形2 10 322 情形21 1 d 中存在至少两个3 桥偏斜有向圈( 包含至少一对偏斜桥的有向圈称 为偏斜有r w 圈) 假设s 1 = b l ，6 2 ，b 3 ，岛= 6 l ，b 2 ，b 4 ) 满足s ( i = l ，2 ) ，至少存在 一对相互偏斜的桥且n ( s 1 ) = n ( s 2 ) = 1 由引理5 2 可得对任意s b ，若f s i = 2 且 s ( b ，虬) 。则n ( s ) = 0 ，因此a 2 1 故m ( d ) = o o + l 十。2 + a 3 l + 4 + 1 + 4 = 1 0 情形2l2 d 中仅存在一个3 桥偏斜有向圈令& = 6 l ，b 2 ，b 3 ) b 满足s l 中存 在一对相互偏斜的桥且礼( s 1 ) = 1 由于a 3 2 ，所以d 中至少还有一个3 桥非偏斜有 向固 ； _ 1 引理52 知s l 中三桥仅有引理5 2 中情形l 、2 两种可能令b s 1 = 虹) ， 则虬必与一，j 中某两桥构成一个非偏斜有向固，故有图6 所示的三种可能据引理52 得 1 0 “2 曼3 ，此时显然a 3 = 2 ，所以r e ( d ) l + 4 + 3 + 2 = l o 图6 恰好包含一个3 桥偏斜有向圈的图 情形213d 中不存在3 桥偏斜有向圈由于a 3 2 ，所以d 至少有两个3 桥非 偏斜有向圈令s 1 = b l ，b 2 ，b 3 且n ( s i ) = 1 ，则显然s l 是相关的令包含品中所有桥 的有向圈为倪，则g 1 与g 同向( 否则，c 1 的长必为3 ，与d 中至少有两个3 桥非偏 斜有向圈矛盾j 令b 一毋= 伯4 ) ，假设b l 与6 4 相互偏斜令岛= 6 4 ，b 2 ，b 3 ，则岛 是相关的且n ( ) = 1 此时d 只有一种可能( 见图7 ) ，显然a 2 = 5 和a 3 = 2 ，因此 m ( d ) = f 之n0 4 = l + 4 + 5 + 2 = 1 2 图7 m ( d ) = 1 2 情形22a 3 = 1 情形2 2 1 d 中存在一个3 桥偏斜有向圈此时a 2 茎3 ，故r e ( d ) = 釜o d = 1 - f4 + 3 + 1 = 9 1 0 情形2 2 2 d 中存在一个3 桥非偏斜有向圈假设岛= 6 1 ，6 2 ，6 4 ) 口满足s l 是相 关的且礼( s 1 ) = 1 令b s l = 伯4 ) ，若6 4 与b 中两条桥相互偏斜，则由引理5 l 得。2 s4 若6 4 仅与b 中一条桥相互偏斜，设此桥为b l ，则因为a 3 = 1 所以存在b b 2 ，6 3 满足b 与b 4 不同向根据命题3 1 和引理5 l 得a 2s4 因此m ( d ) = 圣oo ：1 + 4 + 4 + 1 = 1 0 情形23 a 3 = 0 由于b 中存在一对相互偏斜的桥，敞a 2 5 因此r n ( d ) 薹o 。l + 4 + 5 = 1 0 口 引理62 令d 是具有4 条桥的有向图若b 是平行的，则m ( d ) 茎1 0 或m ( d ) = 1 2 或m ( d ) = 1 6 证明：令b = b 1 6 2 ，b 3 ，虬1 ，可“分三种情况讨论 情形1b 是相关的 情形llb 中任两桥同向，此时m ( d ) 二二2 4 一1 6 情形1 2 b 中至少有一对桥不同向，此时可推出8 中至少有3 对桥不同向，因此 a 2 茎3 又南于a 4 兰1 以及a 3 茎1 ，故m ( d ) = 1 - o a i 茎1 + 4 + 3 + 1 + 1 = l o 。 情形2b 是不相关的，但存在s 日满足l s i = 3 且s 是相关的令s = d 1 ，b 2 ，b 3 ， 口一s = b 4 情形2 ls 中任两桥同向且b 4 分别与s 中的两条桥同向此时0 2 = 5 和a 3 = 2 故m ( d ) = 1 + 4 + 5 + 2 = 1 2 情形22s 中任两桥同向且b 4 仅与s 中的一条桥同向此时a 2 = 4 ，a 3 = 1 ，故 m ( d 1 = 1 + 4 + 4 + 1 = 1 0 情形2 3 s 中存在两条桥不同向此时可推出b 中至少存在两对桥不同向，故 a 2 4 又显然a 3 l ，所以m ( d ) 1 + 4 + 4 + l = 1 0 情形3b 是独立的此时b 中至少存在两对桥不同向，故a 2 4 显然0 3 = a 4 = 0 故r a ( d ) 兰l + 4 + 4 = 9 ： 定理6 1 令d 是具有4 条桥的有向图，则m ( d ) 曼1 0 或m ( d ) = 1 2 或m ( d ) = 1 6 证明。由引理6 1 和引理6 2 可直接推得口 1 2 参考文献 1 1b o n d y ，j aa n dm u r t y ，usr ，g r a p ht h e o r yw i t ha p p l i c a t i o n s m a c m i l l a np r e s s ，1 9 7 6 2 】y o n g b i n gs h i ，t h en u m b e r o fc y c l e si nah a m i l t o ng r a p h ，d i s c r e t em a t h e m a t i c s ，1 9 9 4 1 3 3 ：2 4 9 2 5 7 3 b e r m o n d jc ，h a m i l t o n i a ng r a p h s 、i ns e l e c t e dt o p i c si ng r a p ht h e o r y , e d i t e db e i n e k e l wa n dw i l s o n ，rj ，a c a d e m i cp r e s s ，1 9 7 8 a b s t r a c t ：i n1 9 7 3 rc e n t r i n g e rr a i s e dt h ef o i l o w i n gq u e s t i o n ：d e t e r m i n ew h i c hs i m p l e g r a p h sg h a v ee x a c t l yo n ec y c l eo fe a c hl e n g t hf ，3 lsp ，i nt h i sp a p e r ，e n t r i n g e r sp r o b l e m i se x t e n d e dt od i r e c t e dg r a p h sa n dg e ts e r v e r a lr e s u l t sa b o u tu n i q u e l yp a n e y c h cd i g r a p h s a u n i q u e l yp a n c y c l i ed i g r a p hi sad i g r a p hw h i c hh a se x a c t l yo n ed i r e c t e dc y c l eo fe a c hl e n g t h z ，f o r3 1s ，w h e r epi st h en u m b e ro fv e r t i c e so f t h ed i g r a p h l e tdb ead i g r a p h ，c i st h eh a m i l t o nc y c l eo fd ，t h e nt h ea r c si na ( d ) 一a ( c ) a r ec a l l e dt h ed i r e c t e db r i g d e so f dt h es e to fd i r e c t e db r i d g e so fdi sd e n o t e db yb ( d ) ( o rb ) i fd i