（计算机软件与理论专业论文）关于对集和hamilton圈的一些研究.pdfVIP

中山大学硕士学位论文 关于对集和h a m i l t o n 圈的一些研究 胡若曼 关于对集和h a m i l t o n 圈的一些研究 专业：计算机软件与理论 学位申请人：胡若曼 指导老师：娄定俊教授 摘要 本文证明了任意强正则图g ( v ( g ) ，k ，a ，b ) ，如果b = 0 或6 一 v ( g ) 3 ( v ( g ) 5 ) ， 那么g 是h a m i l t o n 图。 本文还证明了一个n 一可扩图的充分必要条件：图g 是n 可扩图，当且仅当， 对于一个有n 条独立边的集合s ，和任意对集m ，m 包含s ，如果有i m i v ( g ) 3 ( v ( g ) 5 ) ，t h e ngi sah a m i l t o ng r a p h - a n dw co b t a i nas u f f i c i e n ta n dn e c e s s a r yc o n d i t i o na b o u tn - e x t e n d a b l eg r a p h ：a g r a p hg i sn - e x t e n d a b l e ，i fa n do n l yi f , f o ras e tso fni n d e p e n d e n te d g e sa n da n y m a t c hm s ，i fl m i v ( h ) 和巾：e ( g ) 一 e ，使得v g ( e ) = “v 当且仅当h ( 巾( e ) ) = o 中山大学硕士学位论文 关于对集和h a m i l t o n 圈的一些研究胡若昱 ( 0 ( 订；这样的一个映射对( 0 ，中) 称为g 和h 之间的一 个同构。 定义1 - 2 9每一对不同的顶点都有一条边相连的简单图称为完全图。若该完 全图顶点数为r l ，则该完全图记为i 【n 。 定义1 2 1 0所谓偶图( 或二部图) ，是指一个图，它的顶点集可以分解为两 个子集x 和y ，使得任何一条边都有一个端点在x 中，另一个 端点在y 中；这样一种分类( x ，y ) 称为图的一个二分类。完 全偶图是具有二分类( x ，y ) 的简单偶图，其中x 的每个顶点 都与y 的每个顶点相连。若i x l = m ，l y l = n ，则这样的图记为i 【l i l 。 定义1 2 1 1如果v ( h ) c - v ( g ) ，e ( i x ) e ( g ) ，并且v h 是v g 在e ( h ) 上的限 制，那么称图h 是g 的子图，记为h g 。当h c - g ，但h g 时，则记为h c g ，并且h 称为g 的真子图。若h 是g 的子图， 则g 称为h 的母图。g 的生成子图( 或生成母图) 是指满足v ( g ) = v ( h ) 的子图( 或母图) h 。 定义1 2 1 2从图g 中删去所有的环，并使每一对相邻顶点只留下一条连杆 即可得到g 的一个简单生成子图，称为图g 的基础简单图。 定义1 2 1 3假设v 是v 的一个非空子集。以v 为顶点集，以g 中两端点均 在v 中的边的全体为边集所组成的子图，称为g 的由v 导出的 子图。记为g v 】，g v 】称为g 的导出子图。导出子图g v w 】 记为g v ，它是从g 中删除v 中的顶点以及与这些顶点相关联 的边所得到的子图。 定义1 2 1 4假设e 是e 的一个非空子集。以e 为边集，以e 中边的端点全 体为顶点集所组成的子图，称为g 的由e 导出的子图。记为 中山大学硕士学位论文关于对集和h a m i l t o n 圈的一些研究胡若曼 g e 】，g e 】称为g 的边导出子图。边集为e e 的g 的生成子 图简记为g e ，它是从g 中删除e 中的边所得到的子图。 定义1 2 1 5图g 的顶点v 的度( 或次) 是指g 中与v 关联的边的数目，每 个环算作两条边。用d g ( v ) 或简化为d o ) 来表示v 的度，用6 ( g ) 和( g ) 来分别表示图g 中顶点的最小度和最大度。为了说话方 便，把奇数度的顶点简称为奇点，把偶数度的顶点简称为偶点。 定义1 2 1 6称图g 是k _ 正则的，如果对于所有y v ，有d ( 订= k 。 定义卜2 1 7图g 的一条途径( 或通道) 是指一个有限非空序列 w = v o e l v l e 2 v 2 e k v k ，它的项交替地为顶点和边，使得对1 i k ，。i 的端点是h l 和雎，称w 是从v 0 到v k 的一条途径，或一 条( v o ，v k ) 途径。顶点v o 和v k 分别称为w 的起点和终点，而 v l ，v 2 ，v 称为它的内部顶点，整数k 称为w 的长。 定义1 2 1 8若途径w 的边e l ，e 2 ，e k 互不相同，则w 称为迹。又若 途径w 的顶点v 0 ，v 1 ，”k 也互不相同，则w 称为路。 定义1 2 1 9称一条途径是闭的，如果它有正的长且起点和终点相同。若一条 闭迹的起点和内部顶点互不相同，则称它为圈。 定义1 2 2 0经过图g 中每条边的迹称为g 的e u l e r 迹。g 的环游是指经过g 的每条边恰好一次的闭途径。e u l e r 环游是指经过每条边恰好一 次的环游，换言之，e u l e r 环游是闭e u l e r 迹。一个图若包含e u l e r 环游，则这个图称为e u l e r 图。 定义1 2 2 1图g 中，包含g 的每个顶点的路称为g 的h a m i l t o n 路。类似地， 包含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 圈，则称这个图为h a m i l t o n 图。 定义1 2 2 2 图g 的两个顶点“和v 称为连通的，如果在g 中存在( “，v ) 路。连通是顶点集v 上的一个等价关系。于是就存在v 的一个 分类，把v 分成非空子集v 1 ，v 2 ，、k ，使得两个顶点“ 和r 是连通的当且仅当它们属于同一子集v i 。子图g 【v 1 】， g v 2 ，g 【u 】称为g 的分支。若g 只有一个分支，则称 g 是连通的，否则称g 是不连通的。图g 的分支个数一般记为 ( g ) 。 定义1 2 2 3对于连通图g ，若v 的子集v 使得g v 不连通，则v 称为g 的顶点割。k 顶点割是指有k 个元素的顶点割。完全图没有顶点 割。事实上，没有顶点割的图也只能是以完全图作为生成子图的 那些图。 定义1 2 2 4若g 至少有一对相异的不相邻顶点，则g 所具有的k 顶点割中 最小的k ，称为g 的连通度，记为1 ( ( g ) 。否则定义k ( g ) 为v 1 。 于是，当g 是平凡的或不连通时，g ) = 0 。若g ) k ，则称g 为k 连通的。所有非平凡连通图都是1 连通的。 定义1 2 2 5 设s 和s 是v 的子集，我们用【s ，s 】表示一个端点在s 中，另 一个端点在s 中的所有边的集合。所谓g 边割是指形为【s ，s 】 的e 的子集，其中s 和v 是非空子集，v s 表示在v 中但不在s 中的顶点的集合。 k 边割是指有k 个元素的边割。若g 非平凡，则把g 的边连通度 定义为g 的所有k 边割中最小的k ，记为k g ) ；否则，定义九( g ) 为o o 。 定义l 一2 2 6 不包含圈的图称为无圈图，连通的无圈图称为树。在一棵树中 中山大学硕士学位论文关于对集和h a m i l t o n 圈的一些研究胡若曼 任意两个顶点均由唯一的路连接。若g 是树，则e = v 一1 。每棵非 平凡树至少有两个1 度的顶点。 定义1 2 2 7设m 是e 的一个子集，它的元素是g 中的连杆，并且这些连杆 中的任意两个在g 中均不相邻，则称m 为g 的对集( 或匹配) 。 m 中一条边的两个端点称为在m 下是配对的。若对集m 的某条 边与顶点v 关联，则称m 饱和顶点v ，并且称v 是m 饱和的， 否则称v 是m 非饱和的。若g 的每个顶点均是m 饱和的，则称 m 为g 的完美对集。若g 没有另外的对集m ，使得l m | i m | 则m 称为g 的最大对集。显然，图g 的每个完美对集都是最大 对集。 定义1 2 2 8设m 是g 的对集，g 的m 交错路是指其边在e w i 和m 中交错 出现的路。m 可扩路是指其起点和终点都是m 非饱和的m 交错 路。 定义1 - 2 2 9令n 和v 为两个正整数，其中n ( v 一2 ) 2 ，图g 是具有v 个 顶点且存在完美对集的图。若g 中任意边数为n 的对集都可以扩 展成( 或者说都包含在) 一个完美对集( 中) ，则称图g 是n 可 扩的。一个图的可扩度是指能够使得该图是n 一可扩图的最大正整 数n 。当图g 存在完美对集时，我们称g 是0 可扩的；若g 中 的任意一条边都可以扩展成一个完美对集，我们称g 是1 可扩 的；以此类推。 如果n v 一2 ，对图g 中的任意n 个顶点的子集s ，均满足g s 有完美对集，则我们称这个图是n 一临界的。1 临界图也被称为 因子临界图。 定义1 2 3 0图g 的一个k 顶点着色是指k 种颜色1 ，2 ，k 对于g 的 各顶点的一个分配；称着色是正常的，如果任意两个相邻顶点都 中山大学硕士学位论文关于对集和h a m i l t o n 圈的一些研究胡若曼 分配到不同颜色。当g 有一个正常的k 顶点着色时，就称g 是k 顶点可着色的。为了方便起见，我们把它简称为k 可着色。显然， 一个图是k 可着色的当且仅当它的基础简单图是k 可着色的。 定义1 2 3 1设图g 是k 一正则图，a ，b 为两个正整数。如果在g 中，任意两 个相邻点有a 个公共相邻点，任意两个不相邻点有b 个公共相邻 点，那么称图g 是强正则图( v ( g ) ，k a ，b ) 。 对于本文中使用的其他术语和概念，请读者参n q 和【2 】 9 中山大学硕士学位论文关于对集和h a m i l t o n 圈的一些研究 胡若昱 1 3 研究成果及相关背景的简单介绍 本文中所有研究的图均为简单、有限、无向图。 我们用定理的方式给出两个本文的研究成果。 定理a 当b = 0 或b v ( g ) 3 ，强正则图g ( v ( g ) ，l 【 a ，b ) 是h a m i l t o n 图，其中 v ( g ) 5 定理a 相关背景： 图g 中，包含g 的每个顶点的路称为g 的h a m i l t o n 路。类似地，包含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 图。 h a m i l t o n 图的概念是源自1 8 5 6 年哈密尔顿( h a m i l t o n ) 在给他一位朋友的 一封信中所描述的一个小游戏。它在各个领域都有非常重要的应用，尤其是运筹 学。 设图g 是k - 正则图，a ，b 为两个正整数。如果在g 中，任意两个相邻点有 a 个公共相邻点，任意两个不相邻点有b 个公共相邻点，那么称图g 是强正则图 ( v ( g ) ，k ，a ，b ) 。 两相邻点“、v 有a 个公共相邻点两相不邻点“、v 有b 个公共相邻点 图1 - 2 关于强正则图中a 和b 的局部示意图 中山大学硕士学位论文关于对集和h a m i l t o n 圈的一些研究胡若昱 强正则图的概念是在1 9 6 3 年b o s e 最先引入，它在组合设计等方面有广泛的 应用前景。 详细的背景介绍及定理a 的证明请参阅第二章。 定理b 图g 是n 一可扩图，当且仅当，对于一个有n 条独立边的集合s ，和任意 对集m ，m 包含s ，如果有i m i i v ( g ) 3 ，强正则图g ( v ( g ) ，k ，a ，b ) 是h a m i l t o n 图， 其中v ( g ) 5 证明： 1 当b = 0 时，即g 中任意不相邻的两点没有公共相邻点，由于g 是连通图， 显然，g 中不可能存在不相邻的点，即g 为完全图。完全图一定是h a m i l t o n 图。 2 当b = k 时，对定理2 2 的公式进行化简，可以得到2 k = v ( g ) + a ，则2 k v ( g ) 。由于g 是k 一正则图，因此，g 满足定理2 1 ，即g 中任意两点度数 之和大于等于g 的顶点数之和，因此，g 是h a m i l t o n 图。 3 当v ( g ) 3 b k 一1 时，其中v ( g ) 5 ，b 2 我们不妨假设g 不是h a m i l t o n 图，则g 中肯定存在一个最长圈c 和圈外一 些点v l ，v 2 ，v i ( i 1 ) 。 基于此假设，我们有如下推断 推断1 v ( g ) 一v ( c ) 中至少有一点v 1 与c 中至少b 个点相连接。 推断1 证明：由于g 是连通图，则v ( g 卜v ( c ) 中至少有一点v l 与c 上某一点。1 相连接。 1 4 中山大学硕士学位论文 关于对集和h a m i l t o n 圈的一些研究胡若曼 基于c 是最长圈的假设，则v 1 不和c l 在圈c 中的直接相邻点 c 2 相连接，否则c 不是最长圈。 图2 1 那么除去c l 之外，v l 和c 2 有b - 1 个公共相邻点，并且这些点 全部都在圈c 上，否则，c 也不是最长圈。 从而，这b - 1 个点和。1 就够成了c 中与v 1 相连接的b 个点。 口 不妨设c 1 ，c 2 ，c 。( m b ) 为c 上按顺时针顺序与v i 相连的点，1 1 为圈c 上c 。与c ：之间点的个数( 不包括c 。，c 2 ，且取少于半圈的那些点，以下同) ，1 2 为 圈c 上c 2 与c 3 之间点的个数，i m 为圈c 上c 。与c - 之间点的个数。 c l 图2 2 1 s c 3 中山大学硕士学位论文 关于对集和h a m i l t o n 豳的一些研究胡若曼 显然，1 1 ，1 2 ，i 。均不为0 。 推断2 至少有一个i n = 1 n n ) 。 推断2 证明：设x = v ( v ( q v ( c ) ) ，显然x l ：i = 1 1 + 1 2 + + i m 因为 m 8 v ( g ) 3 那么 l + x v ( g ) 一v ( g ) 3 = 2 v ( g ) 3 i i b l + 旧。 若 f l ：x ，由于i 0 ( 1 n m ) ，则必然有i d l x + l 。 若i b i = y ，即圈c 中的顶点比| b i = o 时少y 个顶点，显然，这会 使得： 或者是现在的d ：p , i b i = 0 时的d 多出y 个顶点。 或者是现在的fl z i b i = 0 时的f 少了y 个顶点。 或者是现在的de k l b l = 0 时的d 多出y 1 个顶点，同时fi ：p , i b i = 0 时的f 少了y 2 个顶点，且y l + y 2 = y 综上所述，i d | i b i + 吲) i b l l + l f i 。即l d i l h i 。 口 下面我们将通过两种情况的讨论来推出我们总能找到一个比c 更长的圈，从而 断定我们的假设是错误的。 情况1 ：l h i = 0 图2 7 由之前证得，1 1 , 1 2 ，i m 中总有一个i 。= 1 ( 1 n m ) ，即idl l ，任取一d 1 9 中山大学硕士学位论文关于对集和h a m i l t o n 圈的一些研究胡若曼 中的顶点，不妨设为图2 7 中的v 。因为在集合c 中，有并且只有b 个顶点与 h 相连接，且b k 一1 ，那么v 。必定与b 2 u d u e 中的顶点相连接。 情况1 1 ：v 。与b 2 中的一点相连接，不妨设为图2 - 7 中的h ，那么， v l h v nc a p z c i v z v yc h p 3 c g v v c f p 2c b v l 为一个比圈c 更长的圈。 情况1 2 ：v 。与d 中的一点相连接，不妨设为图2 - 7 中的v 。，那么， v lc a p lc i v z v y c h p 3c g hv nc b p 2c f v l 为一个比圈c 更长的圈。 情况1 3 ：h 与e 中的一点相连接，不妨设为图2 - 7 中的v 。，那么， 1 ) 1c a p lc i v z h hc b p 2c f h c g p 3 c h v l 为一个比圈c 更长的圈。 情况2 ：l h i 1 g 为k 一正则图，我们不妨用d ( d ) 表示d 中每个顶点的度数，用d ( h ) 表示 h 中每个顶点的度数。 h 中的顶点均不与a 中的顶点即v 。相连接，那么h 中的每个顶点都至少连 有b 个与v 1 相邻的顶点，显然，这些点均不在d 中。我们暂时不考虑h 与d 中 顶点相连接的情况，此时，d ( h ) b 。 与情况1 同理，d 中的顶点必定与b 2 u d u e u h 中的顶点相连接。若与 b 2 u d u e 中的顶点相连接，则和情况1 相同。不妨假设d 中的顶点不与b 2 u d u e 中的顶点相连接。 我们暂时不考虑d 中顶点与h 中顶点相连接的情况，此时，d ( d ) = 1 3 。 2 0 中山大学硕士学位论文关于对集和h a m i l t o n 圈的一些研究 胡若曼 可以看出，在我们现在暂时不考虑d 和h 中顶点相互连接的情况下，d ( d ) d ( h ) 。 现在我们来看d 和h 中顶点相互连接的情况。 根据我们的假设即d 中每个顶点只能和h 中的顶点相连接，和推断3 即i d i i n l ，我们不难发现，无论d 和h 中的顶点怎样连接，都不能满足图g 是正则 图的前提条件。d ( d ) 始终会小于d ( h ) 。因此，d 中的顶点必定和b 2 或d 或e 中的顶点相连接。从而，我们可以根据情况1 找到一个比圈c 更长的圈。 综上所述，我们总是可以找到一个比圈c 更长的圈，这与圈c 是最长圈矛 盾，因此，我们的假设必然是错误的。 即当v ( g ) 3 b k 一1 时，其中v ( g ) 5 ，b 2 时，图是g 是h a m i l t o n 图。 综合1 、2 、3 ，定理a 得证。 中山大学硕士学位论文 关于对集和m 衄t o n 圈的一些研究胡若曼 2 3小结 定理a 给出了强正则图是h a m i l t o n 图的一个局部条件。 定理a 的证明是从强正则图的特殊性质出发，充分利用b 的特性，对强正则 图中的最长圈进行研究，从而得到一些强正则图的h a m i l t o n 性质。 并不是所有的强正则图都是h a m i l t o n 图，比如p e t c r s o n 图( 图2 _ 8 ) 。但是一 般来说，一个图连通性越好，那么它是h a m i l t o n 图的可能性也越大。强正则图 正是一类连通性比较好的图。因此我们有如下猜想：是否除去少数几个特例外， 所有的强正则图都是h a m i l t o n 图? 图2 - 8p e t c r s o n 图 中山大学硕士学位论文关于对集和h a m i l t o l l 圈的一些研究 胡若曼 第三章关于对集理论的研究 3 1对集理论的历史及发展现状 对集理论的研究最早始于1 8 9 1 年，彼德森( p e t e r s o n ) 在一篇文章中，把 代数的因子分解问题转换为图的因子分解问题，证明了任意3 正则连通图g ， 若g 没有割边，则g 中存在完美对集。作为图论的一个重要分支，对集理论从 一开始就得到了广泛的关注，经过学者们的大量研究，目前已经形成体系。 下面介绍一下对集理论中的一些较为重要的结果 定理3 1 ( b e r g e ，1 9 5 7 ) g 的对集m 是最大对集，当且仅当g 中不包含有 m 可扩路。 定理3 2 ( h a l l ，1 9 3 5 ) 设g 为具有二分类( x ，y ) 的偶图，则g 包含饱和 x 的每个顶点的对集当且仅当 l n ( s ) i i s i 对所有s c _ x 成立 定理3 3 ( t u t t e ，1 9 4 7 ) g 有完美对集当且仅当 o ( g s ) l s i 对所有s c v 成立 n 一可扩图在对集理论的研究中有着非常重要的地位。n 一可扩图的概念由 p l u m m e r 【5 1 在1 9 8 0 年提出，一些学者对这个课题已经做了不少研究工作。我们简 单介绍一下关于n 可扩图的一些研究结果： 定理3 4 ( p l u m m e r 5 】) 若图g 是n 可扩的，那么g 是( n 一1 ) 一可扩的。 定理3 5 ( p l u m m e r l 6 1 ) 令g 是连通的二部图，它的两个分部是( 聊。假设 n 是满足条件n ( i v ( g ) i 一2 ) 2 的整数，那么以下的条件是彼此等 中山大学硕士学位论文 关于对集和h a m i l t o n 圈的一些研究胡若昱 价的： ( 1 ) g 是n 可扩的； ( 2 ) i u i = l w l ，并且对u 的任何一个非空子集z 满足l 卅i u 卜n ， 有l ( 砷i i 卅+ n ，其中是x 的邻域，即所有与x 中的顶点相 邻的顶点集合： ( 3 ) 对所有的u l ，u 2 ，u n 和w 1 ，w 2 ，w n e 职g = g “l - “2 - u 。一w 1 w 2 w n 有一个完美对集； 定理3 6 ( p l u m m e r 6 1 ) 令g 是一个k 连通图，顶点数为偶数p ，令n 和t 是 整数，0 n p 2 一l ，1 t k 一2 n + 2 ，若对于每一个顶点数为t 的独 立顶点集a ，都有f g ( a ) l p k + 2 n 1 ，则g 是n 一可扩的。 定理3 7 ( p l u m m e r 5 1 ) 设1 k n 一1 ，| v ( g ) i = 2 n 。那么，如果g 是k 一可扩 的，则g 是( k + 1 ) 连通的。 定理3 8 ( p l u m m e r 5 1 ) 设1 k n 一1 ，lv ( g ) i = 2 n 。那么，如果6 ( g ) n + k ， 则g 是n 一可扩的。 定理3 9 ( a n a n c h u e n l 7 1 ) 设1 k n 一1 ，l v ( g ) l = 2 n 。那么，如果g 是k 可 扩的，则要么k + 1 6 ( g ) n ，要么6 ( g ) 2 k + l 。 定理3 1 0 ( p l u m m e t 5 】) 平面图都不是3 可扩的。 定理3 1 1 ( 娄定俊8 1 ) 每个顶点数为偶数的5 连通平面图是2 - 可扩的。 定理3 1 2 ( d i n 舀u nl 0 u 【9 1 ) 令g 是一个具有偶数个顶点的连通图，v v ( g ) ， 定义n k ( v ) = u i u v ( g ) 并且u ，v 之间的距离为k ) 。如果对于每一 个v v ( g ) 和每一个满足条件s en 2 ( v ) 的独立集s ，有i n ( v ) nn ( s ) l s l + 2 n 成立，那么g 是n 一可扩图。 中山大学硕士学位论文 关于对集和h a m i l t o n 圈的一些研究胡若曼 定理3 1 3 ( d i n g j u n l o u 1 0 】) 如果g 是n 一可扩图，并且v ( g ) 4 ，那么g 是 h a m i l t o n 图。 定理3 1 4 ( l i t t l e 、g r a n t 、h o l t o n 1 1 】) 令g 是顶点数为偶数的图，则g 是1 一 可扩当且仅当： ( 1 ) o ( g - s ) q s l ，对于所有的s c _ v ( g ) 成立； ( 2 ) 若o ( c s ) = i s l ，则s 是独立集。其中o ( g - s ) 表示g s 中的奇分支数； 定理3 1 5( l i t t l e 、g r a n t 、h o l t o n 1 1 】) 图g 是1 一可扩的偶图，当且仅当g 有 一个偶图耳朵分解。 定理3 1 6 ( l i t t l e 、g r a n t 、h o l t o n 1 1 ) 设图g 是l 。可扩图且g ，是g 的一个子 图，则g 有一个相对与g 的耳朵分解；当且仅当g 是g 的一个好 的子图。 更多的对集理论资料请参阅p l u m m e r 的综述文章【5 】。 中山大学硕士学位论文关于对集和h a m i l t o n 圈的一些研究 胡若昱 3 2定理b 的提出和详细证明 定理b图g 是n 一可扩图，当且仅当，对于一个有n 条独立边的集合s ，和 任意对集m ，m 包含s ，如果有l m i v ( g ) 2 ，那么就存在一对m 非饱和顶点h 、v ，使得g 有一条 ，v ) m 可扩路p ，并且v ( p ) nv ( s ) ：空集。 证明： 必要性： 设g 是n 可扩图。 令g = g v ( s ) ，m = m s ，则m 是g 中的一个对集。f l = 1 5 = i m i i m 2 卜 重复上述证明我们总可以找到一个m i 包含s 且m i 是g 的一个完美对集。 故g 中任意n 条独立边的集合s 都包含在一个完美对集中，从而，g 是n 一 中山大学硕士学位论文关于对集和h a m i l t o n 圈的一些研究 胡若曼 可扩图。 综上所述，定理b 得证。 3 3小结 本章给出了一个n 一可扩图的充分必要条件。 在该条件必要性的证明中，我们通过对n 一可扩图基本性质的分析，结合b e r g e 定理的逆命题，从而找到一条满足条件的m 可扩路。 在该条件充分性的证明中，我们从对集和m 可扩路的基本性质出发，结合 题设条件，构造出图g 中类似m 且满足题设条件的对集m 2 ，im 2 | i m i 。若m 2 不是完美对集，则将m ：看成m ，再重新构造m 2 ，不断重复此过程，最终得到 一个图g 中包含s 的完美对集，从而证明g 是n 一可扩图。 中山大学硕士学位论文关于对集和h a m i l t o n 圈的一些研究胡若曼 第四章总结和展望 4 1总结和展望 本文的第一章首先简单地介绍了图论的历史及其发展状况，随后详细介绍了 图论中的一些基本术语、基本概念以及相关符号，最后引入关于h a m i l t o n 圈和 对集理论的研究成果定理a 和定理b ，并简单介绍其各自的相关背景。 第二章首先详细介绍了h a m i l t o n 圈的历史及其发展状况和强正则图的相关 概念，而后给出定理a 并对其进行详细的证明，最后对证明的思路及方法进行 小结。 第三章同第二章类似，首先详细介绍了对集理论的历史及对集理论中一些已 有的研究成果，而后给出定理b 并对其进行详细的证明，最后对证明的思路及 方法进行小结。 图的h a m i l t o n 性质是图的一个重要性质，对于一般图h a m i l t o n 性质的研究 也是公认的难题之一。我们通过对强正则图特殊性质的研究给出了强正则图是 h a m i l t o n 图的一个局部条件，在今后的研究中我们希望能够在此基础上继续扩大 这个结果，使得这个局部条件更加一般化，并且由此得到一些强正则图的更为优 秀的性质。 中山大学硕士学位论文关于对集和h a m i l t o n 圈的一些研究胡若昱 参考文献 【1 】j a b o n d ya n du 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 s ，m a c m i l l a n p r e s s ，l o n d o n ，1 9 7 6 【2 】l l o v d s za n dm d p l u m m e r , m a t c h i n gt h e o r y e l s e v i e r , n o r t h h o l l a n d ， a m s t e r d a m ，1 9 8 6 【3 】d i n g i u nl o ua n dy uqlh a m i l t o n i a np a t h si nh a l i ng r a p h s ，c h i n e s e m a t h e m a t i c aa p p l i c a t a , 1 9 9 5 ，8 ( 1 ) ：1 5 8 - 1 6 0 【4 】p j c a m e r o n ，s t r o n g l yr e g u l a rg r a p h s ，s e l e c t e dt o p i c si ng r a p ht h e o r y ( a c a d e m i cp r e s s ，n e wy o r k ，1 9 7 8 ) 3 3 7 - 3 6 0 【5 】m d p l u m m e r , o nn e x t e n d a b l eg r a p h s ，d i s c r e t em a t h 3 1 ( 1 9 8 0 ) ，2 0 1 2 1 0 【6 】m + d p l u m m e r , m a t c h i n ge x t e n s i o ni nb i p a r t i t e g r a p h s p r o c o ft h e s e v e n t e e n t hs o u t h e a s t e r nc o n f e r e n c eo nc o m b i n a t o r i c s ，g r a p ht h e o r ya n d c o m p u t i n g ，c o n g r e s sn u m b e r 5 4 ，u t i l i t a sm a t h ，w i n n i p e g , 1 9 8 6 ，2 4 5 2 5 8 【7 】n a n a n c h u e n ，g r a p h st h a ta r e c r i t i c a lw i t hr e s p e c tt om a t c h i n ge x t e n s i o na n d d i a m e t e r , c u r t i nu n i v , o ft e c h n o l o g y , s c h o o lo fm a t h e m a t i c s ，p h d t h e s i s ， j u n e ，1 9 9 4 【8 】娄定俊，2 - 可扩平面图。中山大学学报( 自然科学版) v 0 1 2 9n o 4 ，1 9 9 0 ， p p 1 2 4 1 2 6 【9 】d i n g i u nl o u ，al o c a ln e i g h b o u r h o o dc o n d i t i o nf o rn e x t e n d a b l eg r a p h s a u s t r a l a s i a nj o u r n a lo fc o m b i n a t o r i c s ，1 4 ( 1 9 9 6 ) ，p p 2 2 9 2 3 3 【1 0 d j 1 0 ua n dq i n g l i ny u ，c o n n e c t i v i t yo fk - e x t e n d a b l eg r a p h sw i t hl a r g ek d i s c r e t ea p p l i e dm a t h m a t i c s ，1 3 6 ( 2 0 0 4 ) ，5 5 - 6 1 1 1 】c h c l i t t l e ，d d g r a n ta n dd a h o l t o n o nd e f e c t dm a t c h i n g si ng r a p h s d i s c r e t em a t h ，1 3 ( 1 9 7 5 ) ，p p 4 1 - 5 4 【1 2 d i n g j u nl o ua n dq i n g w e iz h u ，t h e2 - e x t e n d a b i l i t yo fs t r o n g l yr e g u l a r g r a p h s ，d i s c r e t em a t h m a t i c s1 4 8 ( 1 9 9 6 ) 1 3 3 - 1 4 0 【1 3 1 da h o l t o na n dd i n g j u nl o u ，m a t c h i n ge x t e n s i o n so fs t r o n g l yr e g u l a r g r a p h s ，a u s t r a l a s i a nj o u r n a lo fc