（运筹学与控制论专业论文）连通无爪图的最长圈及其hamilton性.pdf

山东大学硕。l 学化论文 连通无爪图的最长圈及其h a m i l t o n 性 李凌云 l i i 东入学数学学院 运筹学与控制论 山东济南2 5 0 1 0 0 中文摘要 图的h a m i l t o n 性是图的最基本的性质之一。图的h a m i l t o n 性与网络模型 联系密切，使它拥有很强的应用背景，是图论巾重要的研究课题之一。包含有 限简单图g 的每个顶点的圈称为h a m i l t o n 圈( h a m i l t o n i a nc y c l e ) 。若图g 的每 两个顶点都由h a m i l t o n 路连接着，则图g 称为h a m i l t o n 一连通图( h a m i l t o n i a n c o n n e c t e dg r a p h ) 。一个图若自h a m i l t o n 圈，则称这个图足h a m i l t o n 图。无爪 图( c l a w f r e eg r a p h ) 是不含有同构于虬3 的导出j f 矧的图，无爪图是一个重要 的图类。 图的最长幽是探讨图的h a m i l t o n 性的重要工具之一，对它们的研究具有 重要的理论价值和应用价值。本文选择连通无爪图的最长圈作为研究对象， 就是希望能够对进一步了解连通无爪图结构的研究工作有所帮助。本文主要 研究3 连通无爪图的h a m i l t o n 性、4 连通无爪图的最长圈的性质以及h a m i l t o n 性。下面简单介绍一下本文的主要结果。 我们先介绍连通无爪图的周长及幅度的概念。 定义1 图g 的最长圈的长度，我们称为图g 的周长，记为c ( g ) 。 定义2 图g 为阶数为p 的k 连通无爪图，f = c i 圈c 是图g 的最长 圈) ，对任一c f ，定义 ，( c ) ： p ，y ( g ) = y ( c ) im a x d ( v ) l v v ( c ) 一y ( c ) ) ，v ( c ) v ( c ) 山东大学硕l 学f 讧论文 并记0 ( a ) 一i l l a x ，( c ) i c f ) ，称o ( a ) 足图g 的幅度。 我t f j 禾u 用幅度的概念，得出了关丁3 一连通无爪图的h a m i l t o n 性和4 一迕通无 爪图的最长圈及其h a m i l t o n 性的新结论。 结论1图g 是阶数为n 的3 一连通无爪图，o ( c ) 为图g 的幅度，当 o ( c ) j ( n 一6 + 1 ) 时，图g 为h a m i l t o n 图。 结论2 设图g 为4 一连通非l l a m i l t o n 无爪图，罔c 为图g 的最长圈，彤= g v ( c ) 是图g 的导子图，rcr + 是形的一个连通分支。r ，且 t ( u i ) d ，设a t 乞( 乱) ，：( “产1 ) n ( n t ，n t + 1 ) = z ；，z ；，。i ，z ? ，；( n ，1 ) n ( a i + 1 ，a t 2 ) = 鲥，井，群。_ ，u c ( a + 1 ) n ( n ：+ 2 ，a i t3 ) = 霹，管j z ，c ( n 1 ) n ( a i + 3 ，a 件4 ) = r i ，巧2 ，r ，若f 列条件之一成立：( 1 ) z i 蚺3 ：( 2 ) z ； z i l + 2 ；( 3 ，z ；2 r l ；( 4 ) y 髯之2 z 1 1 ；( 5 ) y 等之2 r l ；( 6 ) z ：v 十i ! 1 1 吃1 ， 则i ( a i ，a i + 1 ) l ；：1l c ( o 产1 ) n ( a i ，a i + 1 ) i + l + l ，其中下标取值：当i + j 4 时，值为i + j 一4 ，i ，j = 1 ，2 ，3 ，4 ；f = m i n i p ( u i ，u 抖1 ) i li = l ，2 ，3 ，4 1 。 设c ( 口f 1 ) n ( 锄- 1 a i ) = 毋，等，g ，铲 ，c ( o f l ) n ( a t ，a i + 1 ) = 讲，记，谚 ，c ( o _ 1 ) n ( a i + 1 ，a i + 2 ) = 毋，尊，铲 ，m ：( 口f 1 ) n ( a i + 2 ，a i + 3 ) = p l ，房，硝 ，以上结果对n _ 1 ，其中i = 1 ，2 ，3 ，4 ，亦成立。 结论34 连通非h a m i l t o n 无爪图g 的周长：c ( a ) m i n ( 4 0 ( g ) + 6 ，s a 。 结论4 设图g 是阶数为佗的禾连通无爪图，o ( c ) 为图g 的幅度，圈c 为图g 的最长圈，若o ( a ) ， c ( n 产1 ) n ( 0 4 + 2 ，0 4 + 3 ) = ( z t ，气2 ，彬) ，c ( o 产1 ) n ( 0 4 + 3 ，a t + 4 ) = r j ，q 2 ，r ) ， i fo n eo ft h ef o l l o w i n gc o n d i t i o n ss e t su p ：( 1 ) x i k 靖3 ；( 2 ) z 1 + 2 ；( 3 ) x t 略1 ；( 4 ) 轨i + l 。- 2 i - 2 筏1 + 1 ；( 5 ) y i “+ + 2 2 一；( 6 ) 幺q + q l - 1 一，i ( o i ，0 4 + 1 ) i ；：ll c ( o 于1 ) n ( a i ，0 4 + 1 ) l + z + 1 ，w h e r ei fi + j 4 ，i + j 一4 ，i ，j = l ，2 ，3 ，4 ； z = m i n l p ( u i ，u i + , ) 1 1 i = 1 ，2 ，3 ，4 l e t n 。( a 7 1 ) f 3 ( a i 一1 ，a i ) = 酲，毋，毋，露) ，n 。( a 7 1 ) n ( a t ，a 件1 ) = ( 讲，臂，谚 ，n 。( a 7 1 ) n ( n t + 。，a i + 2 ) = 【口，学，p ，c ( o _ 1 ) f 3 ( 口件。，a 件3 ) 一 p ：，砖，西 ，s oa r e n f l ，w h e r e i = 1 ，2 ，3 ，4 c o n c l u s i o n3l e tgb ea4 - c o n n e c t e dn o n - h a m i l t o nc l a w f r e e g r a p ho np v e r t i c e s t h ec i r c u m f e r e n c eo fg ：c ( g ) r n i n 4 0 ( g ) + 6 ，8 6 i v c o n c l u s i o n4 l e tgb ea4 - c o n n e c t e dc l a w - f r e eg r a p h ，ci st h el o n g e s tc y c l e 山东大学硕j j 学位沦文 o fg ，r + = g 一1 ( g ) i st h es u b g r a p ho fg ，rcr + i sac o n n e c t e ds u bo fr + i f o ( c ) j + a n d 口( g ) ：( 佗一2 j + 5 ) ，gi sh a m i l t o ng r a p h c o n c l u s i o n5l e tgb ea4 - c o n n e c t e dc l a w f r e eg r a p h ，ci st h el o n g e s tc y c l e o fg ，r + = g 一( g ) i st h es u b g r a p ho fg ，兄cr + i sac o n n e c t e ds u bo fr + i f i c ( r ) i = 2 = 4 ，a n do ( c ) ：( n 一2 6 + 4 ) ，gi sh a m i l t o ng r a p h k e y w o r d s ：c o n n e c t e dc l a w f l e eg r a p h ；t h el o n g e s tc y c l e ；h a m i l t o n ；s p o k e n u m b e r 一v 一 山东大学硕+ 上学化沦文 v ( c ) i g i e ( g ) 6 ( g ) d a ( v ) a s 】 e ( g ) g s g 一口 c ( c ) c ( g ) 扩 o ( a ) 符号说明 图g 的顶点集合 图g 的阶数 图g 的边集合 图g 的最小度 u 前：图g 中的度 s 导出的g 的子图 s 导出f 图g 【吲的边集合 矿( g ) s 的导出子图 y ( g ) u 的导出子图 图g 的圈 图g 的周长 图g 的所有路长为3 的两端点度极大值的极小值 图g 的幅度 一v i i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：壅超丞 日 期：地2 ：丛 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：銮盘丞导师签名拯 日 期：礁z 丝 山东大学硕i j 学位论文 第一章引言 在这一章中我们首先介绍在本文中要用到的图论术语及其定义，朱说明的 图论术语会存其他章节巾必要时再给予阐述；之后介绍对连通_ 尤爪图中最长圈 和h a m i l t o n 性研究的历l 史背景和进展状况；最后简曾介绍本义的些主要结 果。 1 1 基本定义与符号 下面我们先列出一些贯穿后面章节的符号和定义，其他未定义的符号和术 语参见【2 i 】。 图g 代表一个有序元组( y ( g ) ，e ( g ) ，妒( g ) ) ，这里v ( g ) 表示非窄顶 点集，e ( c ) 表示与v ( a ) 不相交的边集，妒( g ) 是关联函数，它使图g 的每 条边对应丁图g 的无序顶点对( 7 6 必相异) 。若e 是条边，u 和，是使得 妒g ( e ) = u v 的顶点，则称边e 连接u 和u ，顶点u 和v 是边e 的端点，丑顶点 乱和顶点秒与边e 相关联，顶点钰和顶点 相邻并互为邻点。n a ( u ) 代表由顶 点乱在图g 中所有的邻点所组成的乱的邻域，简记为x ( u ) 。令y v ( a ) ，记 n c ( v ) = u y g ( 耖) y 。 顶点集v ( a ) 中的元素个数称为图g 的阶，记为l g l 或l v ( a ) l 。图g 中与 顶点v 关联的边的数目，称为顶点v 的度，记为d g ( ) 。6 ( g ) 表示图g 中顶点 的最小度。如果图g 中各个顶点的度数都等于k ，则称图g 是k 正则图。端点 重合为一点的边叫做环。一个图称为简单图，如果它既没有环也没有两条边连 接同一对顶点。如果图g 的顶点集和边集都有限，则称图g 为有限图。图中任 意两个顶点都有一条边相连的简单图称为完全图。孔个顶点的完全图记为。 设，v ( a ) 且l i = 1 ，1 i = 3 ，v 2 任意两个顶点均不相邻，k 与之间每 个顶点都相邻的简单图称为爪图，记为尬在本文中，我们仅考虑有限的简单 图。 称图日是图g 的子图( 记为日g ) ，如果v ( h ) 冬y ( g ) ，e ( h ) e ( g ) ，并且妒是妒g 在e ( h ) 上的限制。当日g ，但h g 时，记为 hcg ，并且称子图日为图g 的真子图。若图日是图g 的子图，则称图g 是 图日的母图。图g 的生成子图( 或生成母图) 是指满足v ( a ) = v ( h ) 的子图( 或 者母图) h 。 山东大学硕上学何沦文 设y 7 是顶点集v ( g 1 的一个非窄子集，以y 7 为顶点集，以图g 中的两端 点均在v 7 中的边的全体为边集所组成的子图，称为图g 的山y 7 导出的子图， 记为c r y ，】g f y l 称为图g 的导出+ f 图。导出了图c v y 7 】简记为g y 7 ； 它是从图g 中删去y 7 中的点以及所有与这些点相关联的边所得到的予图。若 v 7 = ) ，则把g 一 口) 简记为g v 。 设g 】和g 2 是图g 的子图，若子图g 1 和g 2 没有公共顶点，则称它们 是4 i 相交的，g 1 和g 2 的并图g lug 2 是指图g 的一个r 图，其顶点集为 v ( c 】) uv ( c 2 ) ，其边集为e ( g a ) ue ( g 2 ) ；如果g l 和g 2 是不相交的，有时记 其并图为g 。十g 2 。类似的可以定义，g 1 和g 2 的交图g lng 2 ，但此时g 1 和 g 2 至少要有一个公共顶点。 图g 的。条途径( 或通道) 是指一个有限非空序列w = v 0 e l v l e 2 v 2 e k t ， 它的项交替地为顶点和边，使得对1 i k ，边e l 的端点是饥和仇一l 。称 w 是从铷到仇的一条途径。顶点哟和魄分别称为彤的起点和终点，而 口l ，v 2 ，吼一1 称为它的内部顶点，整数k 为w 的长。 如果途径w 的边e l ，e 2 ，互不相同，则称为迹，如果 v o ，v 1 ，v 知互不相同，则称彬为路。 称一条途径是闭的，如果它有正的长凡起点和终点相同。若一条闭迹的起 点和内部顶点互不相同，则称它为圈。长为k 的罔称为k 圈，记作瓯；3 圈常 称为三角形。长度足奇数的圈为奇圈，否则为偶圈。图g 的周长是指图g 中最 长圈的长度。用c ( g 1 表示图g 的周长。 如果图g 的任意两个顶点之问都有连接它们的路，则称图g 是连通的。 不连通的图的极大连通子图称为此图的连通分支，图的连通分支的数日用u ( g ) 来表示。 若顶点集v ( c ) 的子集y 7 使得g y 7 不连通，则y 7 称为图g 的顶点割。k 顶点割是指含有k 个元素的顶点割。若图g 至少有一对相异的不相邻的顶点， 则图g 所具有的k 顶点割中最小的k ，称为图g 的连通度，记为k ( g ) ：否则定 义k ( g ) 为i g i 一1 ，若k ( g ) k ，则称图g 是k 连通的。 若图g 中的一条路包含图g 的所有项点则称为图g 的一条h a m i l t o n 路； 图g 的h a m i l t o n 圈是指包含图g 的所有顶点的圈。若一个图包含h a m i l t o n 圈 则称这个图是h a m i l t o n i a n 一2 一 山东大学硕l 学位论文 1 2 研究背景 1 2 1 无爪图的h a m i l t o n 性研究概况 包含有限简单图g 的每个顶点的圈称为h a m i l t o n 幽( h a m i l t o n i a nc y c l e ) 。 对于有限无向简单图g ，包含图g 的每个顶点的路称为图g 的h a m i l t o n 路( h a m i l t o n i a np a t ho 若图g 的每两个顶点都由h a m i l t o n 路连接着，则图g 称为 h a m i l t o n 连通图( h a m i l t o n i a nc o n n e c t e dg r a p h ) 。一个图荇有h a m i l t o n 圈，则 称这个图是h a m i l t o n 图。若图g 是h a m i l t o n 图，则图g 的最艮圈的长度就足 其阶数，即图g 的顶点数。然而，一般来说，判断一个图是否是h a m i l t o n 图相 当刖难，足n p - 完全问题。若图g 不是h a m i l t o n 图，怎样求出它的最长圈的长 度。对。般图，这个i 、u j 题还没有完全解决。这里对一个重要的特殊图类一兀爪 图进行讨论。无爪图( c l a w f r e eg r a p h ) 是不含有同构十k 1 3 的导出子图的图， 无爪图是一个重要的图类，它包含了线图，而线图奉身就是图论中的一个重要 图类。近年来，在研究无爪图方面有很多结果，这类图在许多方而与一般图相 比有较好的性质。 h a m i l t o n 问题一直是图论研究的前沿课题之一。随着应用领域的不断拓 展，对它们的研究已成为近二十年来图论研究的热点之一。最近几年，关于无 爪图连通性的研究已有许多很好的结果，但判定一个图是否是h a m i l t o n 图的充 分必要条件到现在还没有得出。1 9 5 6 年加拿大的t u l l e 给出了一个定理：“4 一连 通的平面图存在h a m i l t o n 回路”。到1 9 7 7 年他又给出了一个新的证明( 利用了桥 的理沦) ，这个证明可以算得上是当今世界上图论方面最好的成果之一。至于 “3 一连通平面图存在h a m i l t o n 回路”也早已被否定。奇怪的是由“禾连通平面 图存在h a m i l t o n 回路”推证不出“四色定理”；相反，若由“3 连通平面图存在 h a m i l t o n 回路”却可以推导出“网色定理”。这实在是令人深思。 图的最长圈是研究图的h a m i l t o n 性的有力工具，例如，m a t t h e w s 和s u m - m e r 【2 2 】已证明了：2 连通无爪图g 有长度至少为2 石( g ) + 4 的圈或图g 是 h a m i l t o n 图，并证明了当6 ( g ) ( n 一2 ) 3 时，图g 是h a m i l t o n 图。、u 和 l i u 【3 2 证明了阶数至多为4 尼+ 1 的2 连通、k 一正则的无爪图是h a m i l t o n 图。 之后，l i u 和l i 【2 8 证明r 阶数至多为5 七一5 的3 连通、k 正则的无爪图是 h a m i l t o n 图。闻良辰【2 0 】引入幅度的概念，使用反证法，通过构造最长罔并得 一3 一 山尔大学硕一l 学化论文 出矛盾的方法，给出了2 一连通无爪图g ，若e ( c ) ( n 一6 2 ) ，这里o ( a ) 是 图g 的幅度，6 是图g 的顶点最小度，图g 是h a m i l t o n 图这一充分条件，为 进一步讨论h a m i l t o n 性提供了，一种新的思路。 目前，连通图的最长幽的忭质及其h a m i l t o n 阡已成为人们十分关注的课题 之一。奉论文以3 连通无爪陶的h a m i l t o n 性，4 连通尤爪图的最长圈的性质及 其h a m i l t o n 性为卜要内容。下丽，我们来分别介绍连通无爪图中的最长罔与 h a m i l t o n 性的研究进展以及部分研究成果。 。 首先介绍一下荚于无爪图的相关定义： 定义1 1 如果一个图g 不含有同构- 丁k 1 3 的导出子图，我们称图g 是无爪 图。 记号l 6 为图g 的最小顶点度，即6 = m i n d ( x ) l x y ( g ) ) ， 扩= m i n m a x ( d ( e ) ，d ( y ) ) l x ，剪y ( g ) ，d ( ：r ，y ) = 3 ) 【2 0 】。 记n - 2 c = x l x 2 x u ：r l ，( x u + l = x 1 ) 为图g 的圈。k ，吻】= c x i ，巧】= x i x ii _ 1 1 ，( 鼢，) = 【x i ，】一 耽， 。( x i ，x j ) 表示圈c 上短段弧的顶点集。 定义1 2 图g 的最长圈的长度，我们称为图g 的周长，记为c ( c ) 。 记号3 尸( 仳，v ) 表示从顶点u 到顶点v 的最长路，以k ，a ，u 分别表示点的连通 数，点的独立数和分支数。z 。 p + 1 ，o + h + l p 一1 ； ( i v ) 若即既e ，z 。z j e ，则下面结论成立： ( a ) 当i + 1 p i tsj 一1 或j + lsp q i l 时i c ( z z ，z 。) j h ； ( b ) 当i + l a p j l 或歹+ l a i 一1 时i c ( z 。，z 口) i h ； ( c ) 当i + 1 p j l ，歹+ l n i 一1 ，z 。z 口+ 1 e ，瓯z 。+ 1 e 时，其中 q s t i 一1 ，则l c ( x 。，z ) i h 或l c ( z 。，x t - - i ) l h ，其中x t - - l x t + 1 e ， 或l c ( z 。+ 1 ，x t ) 2h ，其中z 。一1 z 。+ 1 e 。 车向凯【1 2 也证明了上述结论在3 连通非h a m i l t o n 无爪图中也成立。 引理1 5 2 0 设图g 为2 连通无爪图，z y ( g ) ，则对比，y y ( g ) 名 ， 存在路p ( z ，y ) 使l p ( z ，可) i d ( z ) + 1 一6 一 山东大学硕上学化沦文 引理1 5 【2 0j 设图g 为2 一连通非h a m i l t o n 无爪图，圈c 为图g 的最长 罔，r + = g v ( a 1 是图g 的导出子图，rcr + 是臂的一个连通分支，z y ( r ) ，且 r ( j ( z ) d ，则对r - - 有点z ，y 及路p ( z ，耵) ，使i p ( z ，? ! ) i d r ( z ) + l ，c ( z ) 毋，m ( 耖) 9 ，i 虬( z ) u c ( 可) i22 。 引理1 7 2 0 】 设图g 为2 连通非h a m i l t o n 无爪图，圈c 为图g 的最长 圈，r + = g v ( c ) 是图g 的导山r 图，月cr + 是彤的一个连通分支，名 y ( r ) ，一z 为r 的割点，则对r 中有点z ，y 及路p ( z ，y ) ，使i p ( x ，可) i d r ( z ) + l ，m ( z ) d ，f ：( 可) 毋，l c ( z ) u c ( 可) l 2 。 闻良辰【1 9 】得出上述结论对3 连通非h a m i l t o n 无爪图亦成立。 引理i 8 【1 9 j设矧g 为2 连通非h a m i l t o n 无爪网，罔c 为图g 的最长 圈，r 4 = g v ( a ) 是图g 的导子图，rcr 是形的一个连通子 图，c ( r ) = x i l ，x i 2 ，x i l 】l ，i 1 i 2 i t ( z 赴+ l = x i l ) ，2 2 , m j = m i n a l x 。c ( x i ，+ l ，z ：z 3 + 1 - - 1 ) ，z 。隹y z x i ，) 】，其中j = 1 ，2 ，z ，则有如下结 论： ( 1 ) ( z 。) n ( c x i 。，z 。】u 肮( 冗) u 矿( r ) ) = d ，其巾8 j ，s ，j = l ，2 ，z ； ( 2 ) 若z n c ( z m ，) n cx 。) ，则下列三个结论成立： ( a ) x a - i x 口十1 岳e ； ( b ) z 。，z 卢 l ( z 。，) n i ( z m 。) 时，x a x f l 簪e ； ( c ) i c ( zm ，) n c ( z 。) is2 ，其中s j ，s ，j = 1 ，2 ，z ； ( 3 ) 若r l 是彤一冗的任意连通分支，矗。( z 。；) 晒，则： ( a ) k 。( z m 。) o ，其中8 j ； ( b ) n o ( x r ，) ni ( c x i 。一1 ，z 。】u k ( z 。) uc x i j 一1 ，z m j + 3 】 z 。j ) = 0 ， 其中s 歹，s ，j = 1 ，2 ，l ； ( c ) i c ( z 。，) n cx 。) l 1 ；s 歹； ( 4 ) 若5 + = m i n m a x ( d ( x ) ，d ( y ) ) l x ，y y ( g ) ，d ( z ，y ) = 3 】，z v ( r + ) ， 若d ( z ) 6 + ，贝0d ( z m i ) 5 + ，其中j = 1 ，2 ，z 。 下面我们来看对连通无爪图h a m i l t o n 性的研究，已有如下结果： 一7 一 山尔大学形! i j 学f 讧论文 定理1 7 【8 j 对任一2 一连通无爪图g ，如果存在 0 0 y ( g ) ，l ( 蛳) f = l v ( g ) i l ，则对任意两个顶点n b ( ) 图g 巾存在“，b 为其端点的h a m i l t o n 路。 对于图的h a m i l t o n 性的研究，彳丁过很多好的结果，遗憾的是，至今还没有 找剑一个充要条件，并日存：，找各利，条件的过程巾，很少有名虑肌离为3 的顶点 的，1 9 9 3 年，党恺谦通过对距离为3 a 9 顶点的度数和加以限制，得到了2 一连通无 爪图中存在h a m i l t o n 罔的一个充分条件，从而为研究图的h a m i l t o n 巾l 提供了一个 方法。 定理1 8 【7 】 设图g 为2 一连通无爪图，圈c 为图g 的最长圈，6 + = m i n m a x ( d ( z ) ，d ( 剪) ) l z ，矽y ( g ) ，d ( x ，) = 3 ) ，j i l 0 当6 ；( 他一6 2 ) 时， 图g 为h a m i l t o n 图，且其条什是小可改进的。 2 0 0 5 年，闻良辰应用幅度的概念，使j j 反证法，通过构造最长幽并得出矛 盾的方法，给出了2 一连通无爪图的h a m i l t o n 性的一个充分条件，为进一步讨论 h a m i l t o n 性提供了一种新思路。 定理1 9 1 9 1设图g 为2 连通无爪图，o f f ；) 为图g 的幅度，当o ( c ) 2 ；( 礼一6 2 ) 时，图g 为h a m i l t o n 图。 1 2 2 应用价值 十九世纪中期爱尔兰的皇家人文学家h a m i l t o n ( w i l l i a mr o w a nh a m i l t o n ) 提 出，在一个有多个城市的地图网络巾，寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。 h a m i l t o n 路径问题在h 世纪七十年代初，被证明是“n p 完仝”的。这意味 对于某些顶点数不到1 0 0 的网络，利用现有最好的算法和计算机也需要比较荒唐 的时间( 比如几百年) 才能确定其是否存在一条这样的路径。h a m i l t o n 问题在运 筹学中有着非常实际的意义，例如，求h a m i l t o n 回路中总距离中最短的问题， 就是著名的旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ) 或者叫做传播塞尔斯曼问 题，到目前为止，没有一个有效算法去解决这个问题。 h a m i l t o n 连通性也是互联网络的币要性质之一。h a m i l t o n 连通性表示网 络中任意两点问存在至少一条h a m i l t o n 路，因此，当网络在广播数据时，可以 有效地避免冈某条链路严重阻塞而带来的通信延迟。 一8 一 山东大学硕i j 学f 口沦文 1 3 本文的主要结果 本文主要利用陶的幅度的概念来讨论3 一连通无爪图的h a m i l t o n 件以及4 _ 连 通无爪图的最k 陶及其4 连通无爪幽的h a m i l t o n 性，订以下儿点创新： 1 对3 连通尤爪图的h a m i l t o n 性进行r 研究，给出了3 连通尤爪图的 h a m i l t o n 性的充分条件。 2 讨论了4 连通无爪图的最长圈的相关性质，并给出了最长圈的长度的一 个下界。 3 对4 一连通无爪图的h a m i l t o n 性进行了讨沦，给出了4 一连通无爪图的 h a m i l t o n 性的充分条件。 下面简单介绍一下本文的：# 要结果，以及存内容上的组织安排。 全文共分阴章，第章简单介绍了对连通无爪图的研究的历史背景、进展 状况、已取得的相关结果以及本论文的一止匕研究成果，并对本论文中需要用到 的图论里的基本概念与符号进行j ，解释。这一章是后面其他各章的基础。 第_ 章主要研究3 一连通无爪图的h a m i l t o n 性，我们首先对3 连通无爪图的 性质进行了研究，并有以下结论： 引理2 8 设图g 足阶数为p 的3 连通非h a m i l t o n 无爪图，圈c 为图g 的最长圈，r + = g v ( g ) 是图g 的导出子图，rcr + 是冗的一个连 通分支，n c ( n ) = 翰，z t ：，z 如) ，i l i 2 i t ( z 赴+ ，= 戤，) ，其中 z 3 ，m j = m i n c r l x 口c ( x i j + l ，z 弓+ 1 - 1 ) ，茹a 岳n c ( z j ) ，其中j = 1 ，2 ，z ， 则： ( 1 ) ( z 叻) n ( c x i 。，z 。】um ( r ) uy ( r ) ) = 仍，其中8 j ，s ，j = l ，2 ，z ； ( 2 ) 若霉口c ( 髫。) n c ( z 。) ，则下列三个结论成立： ( a ) z 口一1 3 口+ 1 叠e ； ( b ) z o ，z p 、7 ：( z 。j ) n v ：( z m 。) 时，z 。z p 岳e ； ( c ) i c ( z 。，) n c ( z 。) i 2 ，其中8 j ，s ，j = 1 ，2 ，f ； ( 3 ) 若冗l 是彤一r 的任意连通分支， k 。( z 。；) 0 ，则有下述结论： ( a ) n n ，( z 。，) 谚，其中s 歹； 一9 一 山东大学硕一l 学 眵沦文 ( b ) n 。( x r ，) ni ( c x i 。1 ，z 。；】un c ( z 。) uc x i ，1 ：x n j + 3 】 ) ) = d ， 其中s j ，s ，j = 1 ，2 ，f ： ( 4 ) 若扩= m i n m a x ( d ( x ) ，d ( y ) ) l x ，y v ( g ) ，d ( x ，y ) = 3 ) ，vz v ( n + ) ， 有d ( z ) 筏1 + 2 ；( 3 ) z ； r 1 + 1 ；( 4 ) 统筠2 z h l ；( 5 ) 端2 r ；( 6 ) 气t q + + 1 1 r 1 1 ， 则j ( 哦，a i + 1 ) i ：】j c ( n 于1 ) n ( a i ，a i + 1 ) i + f + 1 ，其中下标取值：当i + j 4 时，值为i + j 一4 ，i ，j = 1 ，2 ，3 ，4 ；2 = m i n l p ( u i ，乱抖1 ) l l i = 1 ，2 ，3 ，4 ) 。 设c ( o _ 1 ) n ( a i 一1 ，a i ) = 毋，聍，g ，擘】，n 。( a 7 1 ) n ( a t ，a i + 1 ) = 琅，臂，醒) ，c ( 口f 1 ) n ( a i + 1 ，a i + 2 ) = 【( ? ，尊，铲 ，c ( n _ 1 ) n ( a i + 2 ，a i + 3 ) = j d ，房，西 ，以上结果对o _ 1 ，其中i = 1 ，2 ，3 ，4 ，亦成立。 其次，我们给出了4 连通无爪图的周长的一个下界： 定理3 5 舡连通非h a m i l t o n 无爪图g 的周长：c ( g ) m i n 4 0 ( g ) + 6 ，8 6 ) 。 一1 0 一 山东大学硕上学位沦文 最后，我们主要讨论了4 一连通无爪幽的h a m i l t o n 性，主要结果如f ： 定理3 6 设图g 是阶数为礼的4 连通兀爪陶，o ( c ) 为俐g 的幅度，圈c 为图 g 的最长圈，若口( g ) 蚺。，或z z 0 。，或暗， 孝， 则i ( ，i + 1 ) l ；：。l m ( 时1 ) n ( n l ，o 州) i + z + 1 ，其中下标取值：当 i4 - 7 3 时，值为i 十j 一3 ，其中i ，j = 1 ：2 ，3 ；：= m i n l p ( u i ，u 件1 ) i i = 1 ，2 ，3 ，。再设c ( _ 1 ) n ( 啦“啦) = 甜，g ，g ，孽 ，n c ( a 7 1 ) n ( a i ，a i + 1 ) = 磺，叩? ，醒t ，c ( n f l ) n ( 吼+ 1 ，o 件2 ) = 0 ，e ，g 。，以上结果对a ：1 ，其中 i ：1 ，2 ，3 亦成立。 对