（运筹学与控制论专业论文）立方图的可圈性.pdf

摘要 图的可圈性是哈密尔顿性的一个推广设g 是有向阿，如果对g 的 每一个定向d ，都存在s ( d ) 互y ( g ) 使在d 中改变所有恰与s ( d ) 中 一令凌赢糯关联酶辍静方蠢鑫所褥戮静匿为鸯舞啥密零簌匿，燹称s 为 可圈图本文将证明至少含五个顶点的连通图g 的立方网是可圈的当且 仅当g 不同构予任何一条偶路该结果改进了k l o s t e r m e y e r 的三个定 疆+ 关键调：可圈性，晗密容顿鼹，啥密尔鞭述通，啥密尔颧匿，立方慝 硕士学住论文 m a s t e r st h e s i s a b s t r a c t t h ec y c l a b i l i t yo fg r 印h si sag e n e r a l i z a t i o no fh 锄i l t o n i a n a g r a p hg i ss a i dt ob ec y c l a b l ei ff o re a c ho r i e n t a t i o ndo fg ，t h e r e e x i s t sas e ts ( d ) y ( g ) s u c ht h a tr e v i s i n ga l lt h ea r c sw i t ho i l ee n d i nsr e s u l t si nah a m i l t o n i a nd i g r a p h i nt h i sp a p e r ，w es h o wt h a tt h e c u b i co fac o n n e c 七e dg r a p hw i t ha tl e a s t 丘v ev e r t i c e si sc y c l a b l ei fa n d o n l yi ft h i sg r a p hi 8n o ti s o m o r p h i ct oa n ye v e np a t h t h i si m p r o i v e s t h r e er e s u l t so fk l o s t e r m e v e re ta 1 k e yw o r d s ：c y c l a b l e ，h a m i l t o n i a np a t h ，h a m i l t o n i a n c o n n e c t e d ，h a m i l t o n i a nd i g r a p h ，c u b i c 1 l 矮士学垃瓷史 m a s t e r s 1 i h e s l s 华中婵范大学学往论文原刽性声嬲和使鼹授权说璎 原创性声明 本人郑鬟声明：所量交豹学建论文，是本人在捋炳指导下，独立进行研究工季# 所取得的磷究藏采。除文中已经标磅孳l 麓静内容步 ，本论文不雹禽任何其谴个人或 集体已经发袋或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均融在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名日期：年月 日 擎谊论文版权使箴嫒敏誊 本学位论文作者完全了解学校有关保留、使用学位论文的靓宓，即：学校有权 保留并向冒豢有关部门戏极聿鼋送交论文的复印件和魄子版，允谗论文被查阅鞠借 阕。本久授粳华中师范大学可戬耨本学彼论文熬全帮凌部分肉容编入有关数攥瘁送 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 作者签名： 日期：年月日 导弹签名：棚狁 日期：d 年g 月o 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章獠”，同意将本人的 学位论文提交“c a l i s 商校学位论文全文数据库”中全文发布，并可按“章程”中的 援定享受翊关投益。回蕊途塞逯銮蜃澎羞! 婆兰望置謦二望；璺三笙筮壹! 榷者签名： 霉纛：年露 簿 导师签名硼锐 瓣期：o 每胄l o 蓦 第一节引言 一符号说明 本文讨论简单有向图，未加说明的符号和术语，参见文献 1 常用符号说明： y ( g )图g 的顶点集合 e ( g )图g 的边集合 g 【s 】g 中由点集s 导出的子图 墨丛：基墨和是的对称差 爿( d )有向图d 的弧集 ( g )图g 所含顶点的最大度 二历史和研究现状 哈密尔顿性是图论中一个非常重要的性质1 9 9 7 年，k 1 0 s t e r m e y e r 和s 0 1 t e s 引入了一个新的类似哈密尔顿性质的图，即可圈图，开拓了 图论中有关类似哈密尔顿性质研究的新领域在 7 中，他们给出了许 多关于哈密尔顿性，哈密尔顿连通性和可圈性之间联系和区别的定理 ( 定理见第二节简介) ，本文改进了其中的一些结论 第二节简介 设g 是一个简单图，s 为矿( g ) 的子集，g 【s 】表示由s 导出的子图 一个图中的路是由一系列不同的顶点所构成，其中相继的顶点是相邻的 比如一条路p 一“。“。吩，我们一般假定p 的方向为从顶点到顶点q 如果雌和“为p 中的点，并且f sj ，那么”， 表示p 中从q 到“，中的连 续点，同时“，元；表示p 中从，到中的连续点这里我们认为 ，和 “i 而i 既是子路又是顶点集 我们研究有向图的下述运算一推点运算在有向图中，“推”一个 顶点意味着将这个被推的顶点所关联的弧全部反向我们称有向图d 能被推成有向图日当且仅当对d 中的顶点作一系列的推点运算之后得 到的图与日同构 k 1 0 s t e r m e y e r 和s 0 1 t e s 用推点运算定义了一种全新的类似哈密尔 顿性质的图即可圈图 设g 为有向图，如果g 的每个定向都可以推成哈密尔顿有向图， 则称g 为可圈图显然，每个可圈图都是哈密尔顿图关于可圈性的 研究最早是由k l o s t e 瑚e y e r 6 作出的，在该文中他证明了所有的奇圈 都是可圈的，所有偶圈都不是可圈的因此一个阶数为奇数的图是可 圈的当且仅当它是哈密尔顿的因此，我们仅需研究偶阶图的可圈性 既然不是所有的阶数为偶数的哈密尔顿图都是可圈的，那么可以 硕士学位论文 m a s t e r st h e s l s 比较可圈性和其它类似于哈密尔顿性的性质图g 被称为是哈密尔顿 连通的当对它的任意两个顶点“和v ，存在g 中的一条“一v 哈密尔顿路 k 1 0 s t e r m e y e r 和s o l t e s 7 中证明了偶圈的平方图是哈密尔顿连通的 但不是可圈的，而完全二部图墨。，( rz 2 ) 是可圈的但不是哈密尔顿连 通的因此可圈性和哈密尔顿连通性这两个性质不存在一个比另一个 更强 设g 是一个图( 有向图) ，我们用e ( g ) ( 爿( g ) ) 表示它的边集( 弧集) 现在我们介绍一些不标准但是非常重要的定义图g 的定向d 的一个 “基”指的是通过给边集s ( g ) 中的边定向所得到的有向弧集i 如 果一条弧e j 是彳( d ) 中的弧，那么我们称弧e 与有向图d 一致，否则， 我们称弧e 与有向图d 不一致基j 中与有向图d 不一致的弧的条数称 为是基i 的权如果基i 的权为偶数，我们称基i 是好的否则，我们 称基i 是坏的显然将基j 中的两条弧同时反向不会影响j 的权，比如， 将一个好的基中的任意两条弧反向，我们得到另外一个好的基如果 i 中的弧形成一个有向圈，也就是说用某种方式给顶点标号后如果 j 一 u 屹，v ：屿，以一1 v 卅，v 1 ) ( 研为正整数且小z 3 ) ，我们称j 为d 的一个弱 圈如果这个弱圈j 是好的，那么我们称它是d 的一个好弱圈，否则称 它是d 的一个坏弱圈，简单的记为j v l v ：u 对于g 的一个定向d ，令x = u 如u 是g 中的一个圈或者一条路 我们定义，伍) 一厶“u + 。) ，其中 肫，= 船羹裟主忽 如果，似) 的值为偶数，称集合x 是好的，否则称j 是坏的 图g 的女次幂图g 是一个顶点集为y ( g ) ，边集合为 e ( g ) ； 刁， z ，y y ( g ) ，z y ，d 括乞o ，y ) s 女) 的图 下面是已经由k 1 0 s t e r m e y e r 作出的关于可圈性的一些定理 定理1 ( k 1 0 s t e m e y e r 6 ) 设g 为厅阶图如果一为奇数，那么g 为可圈图当且仅当g 为哈密尔顿图如果g 为偶数，那么g 的定向d 能被推成一个包含有向哈密尔顿圈的图当且仅当d 包含一个好的哈密 尔顿圈 显然，所有的可圈图都是哈密尔顿图，但反之不成立定理1 告诉 我们所有奇圈都是可圈的，而偶圈不是可圈的，因此一个具有奇数个 顶点的图是可圈的当且仅当它是哈密尔顿的 定理2 ( k a r a g a n i s 5 ，s e k a n i n a 1 2 ) 至少含三个顶点的连通 图的立方图是哈密尔顿连通的 下面这个定理说明连通图的立方图不一定是可圈图 矮士擎佳论史 m a s t e r s 下 羞鞋s l s 定理3 ( x l o s t e r m e y e ra n ds 0 1 t e s 7 ) 含虢个顶点的路的波方 图不可圈 由定理3 ，卜连通和3 次幂都不能保证可圈性若增加1 次幂和增 加1 个连遥庋，k l 。s t e r 推e y e r 帮s o l t e s 得到了下面嚣个关于霹圈瞧的 充分条件 定理_ 嚷( k 1 0 s t e r 黼y e ra n ds o l t e s 7 ) 至少含五个顶点的连通图 的篷次幂建譬酲图。 定理5 曝1 0 s t e r 黼y e ra n ds o l t e s 7 ) 至少含五个璜点的二连遥 豳的立方圈是可圈的。 本文对立方图的可凿性进行亥l 凿，得到下述定理： 定理6 设g 为至少含五个顶点的连遥圈那么g 的立方图是可圈 静当虽仅警g 不露祷予任意一条镁路 显然，定理6 是定理3 ，定理4 和定理5 的一个公效推广 第三节有关引理 为了证明定理6 ，我们需要如下引理 引理l ( k 1 0 s t e r m e y e r 8 ) 一个有向图可以推成哈密尔顿有向图 当且仅当它有一个好的弱哈密尔顿圈 在此引入对称差的定义：基s 和s 的对称差 s s ：= ( s 最) u ( 墨) ( s ) + ：) 4 荟( e ) + 荟。o ) 2 镰雌) + 磊：吨) + 盖嘶) 因为2 了0 ) 为偶数，所以由上式，s 峨的权与s ，足两者和的具 娟 有同样的奇偶性 关于对称差有如下结论：设有向图d 不能被推成哈密尔顿有向图 那么d 中任意两个弱哈密尔顿圈的对称差s 是好的 引理2 如果图g 包含由 畸，也) 和 y ，y ：，y 3 】两部分构成的完全二部图 作为子图，使得五和屯在g 中相邻，并且使得对于每个1 s f s ，s 3 存在 g 一 而，屯) 中的只到y ，的哈密尔顿路，那么g 可圈 证明：我们将证明图g 的任一个定向d 能被推成一个哈密尔顿有 向图首先我们证明定向d 的子定向图d l ( 由顶点毛，x ：，n ，_ ) ，：，儿导出) 有 一个基，即同时包含在d 和d 1 中的一个好的弱四圈 用反证法，假设d 中不存在这样一个好的弱四圈作为基那么弱四 圈t h 工：y ：_ ，h 鼍_ ) ， 是坏的 那么它们的对称差s = 而_ y ：，y 而，y ，- ，工：y 。) 是好的将s 中的最后两 条弧反向，我们得到一个好的四圈) ，：五) ，也，矛盾 因此我们可以假设d l 有一个好的弱四圈，不妨设为c = 鹏y ：墨， 由该引理的假设，存在g 一 而，工：1 中的一条由y ，到y ：哈密尔顿路p 若 有向图d 不能被推成一个哈密尔顿有向图那么由引理1 ，弱的哈密尔 顿圈c l = y ，砂：t t 和c 2 = _ ) ，。毋：z 一：h 都是坏的因此这两个圈的对称差 c 1 c 2 = y ：，埔，葺_ ) 。，y ：，屯y 。) 是好的由于埔和v ：这两条弧都在 这个对称差里面，那么( c 1 c 2 ) 一 确，矾) = 讪，y 戎，y 如，艺m ) 是坏的这 时将y 如和屯y 。这两条弧反向，我们得到一个坏的弱四圈毛咒屯m ，与 假设矛盾因此图g 的任一个定向d 能被推成一个哈密尔顿有向图， 那么g 可圈 引理3 ( k l o s t e m e y e ra n ds 0 1 t e s 7 ) 设g 是一个阶数为偶数 的简单图，d 为g 的一个定向如果d 中包含一个好的四圈n 。n ：n 。n 。n 。， 存在弦n 。码e ( g ) ，使得g k 焉 中存在连接n ：一n 。的哈密尔顿路则 d 可被推成哈密尔顿有向图 证明：用反证法，假设d 不能被推成哈密尔顿有向图设p 为 g 一 n 。，毛) 中的连接口：一口。的哈密尔顿路 硕士学位论文 m a s t e r st h e s i s c i = l 口2 p 口4 口3 口1 ，c 2 重n 3 n 2 砌4 口1 口3 则c 1 ，c 2 都是d 中的弱哈密尔顿圈，由引理1 ，c l c ：是好的 c 1 c ：= n ，口2 n ，口1 n 。吒) u n ，n ：，n l 口，n 。口，) 由m ( 叩炳) ) ；1 ，去掉这两条边，得到 叩：，口4 叩：一q 是坏的，将 弧口n ，4 ，：反向，即推顶点n ，得到圈c - n 。n ：n 妒。n 。仍然是坏的与已知 中c 是d 中的好的四圈矛盾引理得证 要证明引理4 和5 ，需要用到定理2 的结论，由于定理2 的证明比较 简短，不妨在这里给出： 定理2 的证明：设g 是至少含三个顶点的连通图，那么g 中包含 一个支撑树r 我们对川n 进行归纳当n ；2 ，3 ，4 时，结论显然成立 当n 乏5 ，假设结论对n 一1 阶树成立对n 阶树f ，顶点x 和y 是任意 r 中的顶点并且z * ) ，要证明丁3 中存在连接顶点x 和) ，的哈密尔顿路 我们考虑顶点z ，) ，在r 中之间的距离d = 如o ，y ) ( 1 ) 当z 和y 相邻时，去掉边叫，得到两棵树分别包含顶点x 和y 设 包含顶点x 的树为墨，包含顶点y 的树为正设互中与z 相邻的顶点为x ， 互中与_ ) ，相邻的顶点为) ，由假设，口中存在从x 到x 的哈密尔顿路号 霉中存在从y 到y 的哈密顿路只此时由x y r 3 ，那么埠_ ) ，豆y 为r 中连接马y 的哈密尔顿路 ( 2 ) 当x 和y 之间的距离为2 时，我们设顶点v 为顶点x 和) ，的公共邻点， 同( 1 ) ，我们去掉边w ，得到两棵树薯和瓦分别包含顶点x 和v ，y 设z 在 互中的一个邻点为“那么砰中存在从z 到“的哈密尔顿路号，譬中存 在从y 到v 的哈密尔顿路只，那么坤幔y 为r 中连接x ，y 的哈密尔顿路 ( 3 ) 当x 和y 之间的距离大于2 时，不妨设w 为x 一) ) 路上的一条边，其 中x 一，y v ，同上，我们去掉边“v ，得到分别包含瘌) ，的两棵树王和 疋，砰中存在从x 到“的哈密尔顿路墨，才中存在从y 到v 的哈密尔顿 路昱，那么卿厘y 为r 中连接t _ ) ，的哈密尔顿路定理得证 引理4 ( k 1 0 s t e 加e y e ra n ds o l t e s 7 ) 至少含五个顶点的一棵 树t 的两个悬挂点若有一个公共的邻点，那么r 3 是可圈的 证明：设畸和屯为r 的两个悬挂点，它们的公共邻点为h 由r 至 少含有五个顶点，h 有另一个邻点记为y ：，同样的y 。和y ：中其中一点 一定又有另外一个邻点) ，y ，为不同于薯，而，y 。，) ，：的另一顶点我们将 证明r 是可圈的，通过证明由这五个顶点导出的子图满足引理2 显然， r 包含，( 由 葺，而) 和 y ，y ：，) ，) 两部分构成，其中和x ：相邻) 这个子 图我们需要证明对于y 1 ，y ：，y ，中的任意两个顶点，比如) ，。和y ：，存在 r 3 一k ，而) 中的一条哈密尔顿路) ，。一y ：由丁一k ，z ：) 是连通的，因此由 定理2 ，丁3 一k ，屯) 是哈密尔顿连通的，再由引理2 ，r 3 是可圈的 硕士学位论文 m a s t e r s t h e s l s 引理5 丁为一棵树，慨是r 的一条边那么存在r v 中的一个顶 点y 满足挑p ，) ，) s2 使得r 3 一v 中包含一条哈密尔顿路连接x 和y 证明：令m o ) ： _ ( = 工) ，耳) 定义五为r v 中包含顶点t 的连通 分支，f ：1 ，七由丁是一棵树，对每对( f ，) ，其中1 s i cjs 七，都满足 y ( z ) n 矿吒) = 中存在点y ( 以“) n y ( z ) ) u k ) 使得) u ) ，。) l 达到最大值 那么对每个f ，我们有要么| 矿( 王) 一1 要么y ；一t 由定理2 ，我们可以得 到存在p 的一条哈密尔顿路p 连接和咒对每个f ，如o ，) = 1 并且 d 坼p ，y ) s2 ，- 只y l 以最y 。是r 3 一v 中连接x 和y ( = y 。) 的一条哈密尔顿路 引理得证 引理6 偶路的立方图不可圈 证明：对每个非负整数七，定义+ ：表示无向路啦。我们递 推的构建昱。的立方图的定向d 2 。并证明这个定向不能被推成一个包 含有向哈密尔顿圈的图从最简单的例子开始，这里令d 4 是如图1 的 只3 的定向 v 2屹 图1 玩 1 0 有向图d 2 。的顶点集h ，v ：，+ ：) 是由有向图通过增加两个顶 点v ：。和+ ：得到 这样由 v ：。，v ：。，v ：。，+ ：) 这四个点导出的子图和d 4 是同构的( 同构 映射伊：妒( v ：。) ：v 1 ，妒( ) = v 2 ，妒：。) = 码和妒( v 。+ ：) = v 。) 最后，将边 v ：。叱。定向为+ 。v ：。，如图2 所示： 屹i 一3 也 一2”2 i 一1 也i屹i + 1 如 + 2 图2 d 2 。的子图 我们需要f 回这个结论： 断言：设c 为壤+ ：的哈密尔顿圈，女z 2 那么存在壤中的一个哈 密尔顿圈c + 使得，( c + ) 和，( c ) 有同样的奇偶性 证明：因为当圈c 的长度是偶数时，( c ) 和，( 西具有同样的奇偶性，那 么我们证明c 或者百满足断言的条件即可因此我们可以假设 c ：距一：h ：。“。是壤+ ：中的一个哈密尔顿圈其中心，) - “。，+ 。) 满 足“：o ，is l “，o ：下面分两种情况来讨论： 1 1 硕士学位论文 m a s t e r st h e s i s 情形1 ：f 一3 这时h ，：。，“。+ 。e ( 砬+ ：) 子路“一一，“。有如下四种 可能情况：v 2 i v 2 v 一l ：+ 2 + 1 一2 ：一1 v 2 + 1 ：一l v 2 “2 v 2 t + 1 v 2 m 易得，0 一：“，“。) 与，0 。n 。) 具有同样的奇偶性因此，( c ) 与， 一。“，“：。“，) 也具有同样的奇偶性情形1 得证 情形2 ：f ，3 由+ ：在壤+ ：中有三个邻点，“。和叱其中一个是v 。， 另外一个是v ：。显然q 一。v ：。，“。v ：。e ( 哎+ ：) 那么嵋一。或者雌。必有一 个在 v ：。，v ：。】里面因此 “，】n h f 。“。) 一中由情形l ，我们有f = 4 那么子路“。“一。“，只有以下两种可能情况：v ：。v ：。如。v ：。v ：。： v n v 2 “2 如t l 屹“，2 t 一2 不难验证， 一：“。“，) 与，0 一一，) 有同样的奇偶性因此，( c ) 与 ，0 一一；“：。“。) 具有同样的奇偶性断言得证 反复应用断言，我们可以得到对最+ ：中的每个哈密尔顿圈c ，存在 日中的一个哈密尔顿圈c 使得，( c ) 与，( c ) 有同样的奇偶性由每个 d 4 中的哈密尔顿圈都是坏的，那么每个d 2 。中的哈密尔顿圈也是坏的 由定理l ，+ ：不能被推成一个包含有向哈密尔顿圈的有向图这样就 证明了引理6 引理7 至少含六个顶点的偶圈的立方图是可圈的 证明：由每个圈都是二连通图，这个结论可以直接由定理5 得到 下面我们不利用定理5 的结论而是单独来证明这个引理令 c ：吒屹u v l 是一个顶点数n = 6 的任意偶圈用反证法，假设c 的立方 图是不可圈的，那么，存在一个c 3 的定向d ，d 不能被推成一个哈密 尔顿有向图但是d 可以被推成一个有向图d 使得h 比k 为d + 中的有 向哈密尔顿路如果k u 爿( d ) ，那么u v ：k u 为d + 中的有向哈密尔顿 圈这种情况与假设矛盾因此v u 隹彳( d ) ，即h k 4 ( d ) 令f 为整数，满足1 s f s n 一3 那么c f = q q + 。k + ：吒以是c 3 中的一个四 圈并且对角边u q + ：存在，使得c 3 一亿，u + ：) 中存在一条哈密尔顿路 q + 。q 一。醌+ ，连接q + ，和q ，由引理3 ，e 不是一个好的四圈因此 h u + ，一( d ) 特别的，我仃 有u v 4 ，如屹，b 4 ( d + ) 那么v i v 。b v 2 v 3 v 。c v l 是 d 中的一个好的哈密尔顿圈由定理1 ，d ( 或者d ) 可以被推成一个 哈密尔顿有向图，与假设矛盾从而引理得证 矮士擎娃论戈 麓a s t e r s t 毛嚣s i s 第四节定理6 的诞骥 在证明定理6 之前，首先证明如下定理： 定理? 令r 是一襟瓣，顶窳羧一5 翔果矗霉) z 3 ，那么f 酶盛方 图是可圈的 证鹗：令v 是矿) 孛豹一个顶点，辑= 仁心， ，其中露黧3 。 对每个f ；l 2 ，七，令薯是r v 中包含毛的连通分支重新给的下标f 标号，使得| y 列s | y 暇) l p s 眇媛) | 。由弓 理生我搬可以俊定p 馁 | 鼍2 。 如果矿何) 一k ，令m 净鼍：否则，我们令h 为鼍在墨中的一个邻点，对 每个f 一2 ，七，令弘照薯在霉中的个邻点由引理5 ，对每个满足 旷何) i z 2 的f ，都存在一个顶点薯矿圆) 一亿 ，d 晦，蜀) 2 ，使得妒一t 中包含一条连接m 和的哈密尔顿路霉当一。h 时令一- ，那么 事实l 对l s f # ，嚣露，毛墨，薯y j e p 3 ) 。 事实2 对f = 1 ，2 ，七，t e 仃3 ) 分下面两种情形讨论： 情形l 露4 。 不失一般性，假定p 伍) l 1 令q = y ：b z 。霉y 1 ( 如果y 皤) 一“) ，令 q = 岁：置掣) 。注意至l 捌。? 一罗蔹) u 陋：) u y 恁是一搡树并显妫舌掣 。 由引理5 ，存在一个顶点y + p 僻) v j 满足搬。( v ，y + ) 2 使得h 3 一v 中包 含一条连接t 和y 的哈密尔顿路q 。壶事实l 帮事实2 ，我们可以褥到 儿勿 弓霉y 池圆+ ，y 。鳢执z 。缈、z 点地和y + 西。y ：翱呶为岛亏以是一k ，茗： 中的 壤士学锰论史 艇a s f e r s t ￥鞋s l s 三条哈密尔顿路因此地，y 毫0 也) n ，瓴) 并且碣联嚣口3 ) 。由弓i 理 2 ，r 是可圈的 情形2t ：3 蓄宠髅定l 矿瓴l 1 那么y 。鹞：佻芝2 焉，_ ) ，点：妫z ；萎y ，秘y 2 只理，嚣托 是丁3 一h ，屯) 中的三条哈密尔顿路类似于情形l 的讨论，我们可以得 菇尹是霹瀚懿。因戴，我嚣j 缓定矿伐l 芑2 。阉游，由定理l 稻2 ，我翻 假定l y ( t ) l 楚偶数， 注意捌扩绽) | + y 暇籽眇愿) | 。旷够籽4 。l 矿( 嘲，| y 殴) | 粒矿缓) | 孛至少 有一个是偶数，比如f 矿( 只) i 如采7 3 不可圈，那么存在的定向d ，j d 不能被报成个哈密尔顿有向图。令g = 碱托墨强鼓毋办， c 2 一电毪妇啦钞：西而，其中p h 墨葺坦：丘y ：( 如图3 ) 五y 1露互 强3 既然d 不能被推成哈密尔顿有向图，那么圈c 1 和c 2 都是坏的， 蔟士学佼瓷史 a s t e 建s t 差器s l s 这意味着c l g - 撕，y ：，砖娩，y 而) u 僻( p ) u 五伊”是好的 由 甜汪( p ) u 嚣e 勘= r ( p ) 卜l l 矿g ) h y 弼) | _ 4 是偶数，所戳e m 鳓咒y ：而 楚好 的四圈，包含对角边蝻注意到y 。墨诵y ，只2 ，怯，豆y ：是r 一k ，恐) 中涟接 苁帮y ：静晗密尔顿路。由弓| 瑾3 ，蚤霹戳被攘成一个哈密尔顿毒囱鬻， 与假设矛盾这样就证明了定理7 定理6 的证明：令g 是一个至少包含五个顶点的连通图由引理6 ， 只翥证明翔皋g 不网构子一条馁路那么g 3 楚可圈的。我键分两秸愤形 讨论： 情形l 够) 3 + 这种情形下，g 包含一棵支撑树r 使( g ) 凛3 由定理7 ，r 是可圈的，因此g 3 也是可圈的 情形2a ( g ) 一2 这种情形下，g 是一个圈或者照条路。融定 理2 ，g 3 怒哈密尔顿黧。如果罔是奇数，那么由定瑾l ，g 3 是可圈的。 如果f g i 是偶数，那么由g 不同构于一条偶路知，g 是一个偶圈幽引 理7 ，怒可霾薛这样就证翻了定理6 。 参考文献 1 j a b o n d y ，u s r m u r t y ，g r a p ht h e o r yw i t ha p p l i c a t i o n m a c m i l l a n ， l o n d o na n de 1 s e v i e r ，n e wy o r k ，1 9 7 6 2 g c h a r t r a n d ，a m h o b b s ，h a j u n g ，s f k a p o o r ， a n d c s t j a n a s h w i l l i a n i 锄s ， t h es q u a r eo fab l o c k i s h a i i l i l t o n i a nc o n n e c t e d ，j c o m b i n t h e o r ys e r b1 6 ( 1 9 7 4 ) 2 9 0 2 9 2 3 y c h e n ， y z h a n g ， a n dk z h a n g ，a no r e t y p ec o n d i t i o nf o r c y c l a b i l i t y ，e u r o p e a nj c o b i n 2 2( 2 0 0 1 ) 9 5 3 9 6 0 4 r d i e s t e l ，g r a p ht h e o r y ，s p r i n g v e r l a gn e wy o r k ， 2 0 0 0 5 j j k a r a g a n i s ， o nt h ec u b eo fag r a p h ，c a n a d m a t h b u l l 1 1 ( 1 9 6 8 ) ，2 9 5 2 9 5 6 w k 1 0 s t e r m e y e r ，p u s h i n gv e r t i c e sa n do r i e n t i n ge d g e s ， a r s c o m b i n 5 1( 1 9 9 9 )6 5 7 5 7 w k l o s t e r m e y e ra n dl s o l t e s ，h a m i l t o n i c i t ya n dr e v e r s i n g a r c si nd i g r a p h s