（基础数学专业论文）图的可迹性和直积图着色性质的讨论.pdf

中文摘要 本文第一部分根据三点独立集的度和( 记作o ，( g ) ) 讨论了玎一可扩图的可迹性 关于刀一可扩图，1 9 5 7 年b e r g e 在文献 2 中首次提出咒一可扩路的问题，而自从 p 1 u m e r 于1 9 8 0 年在文献 3 中首次引入，l 一可扩图的概念以来，一些学者对可扩图 的度和，可迹性，h 锄i l t o n i a n 性等方面进行研究，得到了一系列成果【3 5 】2 0 0 1 年k e n i c h ik a w a r a b a y a s h i ，k a t s u h i r o o t aa n da k i r as a i t o 在文献 4 中给出 连通的，l 一可扩图的度和与哈密尔顿性及该图与完全图之间的一些关系1 9 9 6 年阿勇 嘎教授在文献 5 中根据顶点数不小于3 的连通图的度和得到图g 的子图在g 中可迹 的一个充分条件 在以上的研究基础上，本文根据图中三点独立集的度和得到了连通的咒一可扩图 可迹的一个充分条件 第二部分主要证明了对几类特殊图h e d e t n i e m i 猜想的等价命题成立图论中， 图的着色问题是人们关注的一个焦点，着色问题起源于最著名的猜想四色猜想 6 自从英国人g u t h r e f 佛朗西斯古特里 于1 8 5 2 年提出四色问题之后，人们用 不同的方法去攻克这一猜想，但至今还未有严格的解析证明h e d e t n i e m i 在文献 7 中揭示了一个图的色数与直积图色数之间关系的猜想，用代数思想研究图的着色问题 对色数大于5 的图还未证明h e d e t n i e m j 猜想成立b e n o i tl a r o s e ，c 1 a u d et a r d i f 在 文献 1 1 中用收缩的观点研究h e d e t n i e m i 猜想，并证明了对两个连通图和顶点传递 的射影的核，h e d e t n i e m i 猜想的等价命题成立 本文根据以上研究结果及一个图是柱心的充分条，件证明了对几类特殊的图 h e d e t n i e m i 猜想等价命题成立 关键词：胛一可扩图，可迹性，直积图，柱心，收缩 a b s t r a c t i nt h ef i r s tp a r to ft h i sp a p e r ，b a s e do nt h ed e g r e es u mo fi n d e p e n d e n t s e tw i t ht h r e ev e r t e x ，d i s c u s s e dt h et r a c e a b i l i t yo f ，z e x t e n d a b l eg r a p h a b o u t以一e x t e n d a b l eg r a p h ，i n1 9 5 7 ，b e r g ep u tf o r w a r dt h e 刀一e x t e n d a b l ep a t b f i r s ti nr e f e r e n c e 2 h o w e v e rs o m es c h o l a rs t u d i e dt h ed e g r e es u m， t r a c e a b ili t ya n dh a m i 1 t o np r o p e r t yo f玎一e x t e n d a b l eg r a p h ，s i n c ep l u m e rd r a w i n t ot h ec o n c e p t i o no f 刀一e x t e n d a b l eg r a p hi n1 9 8 0 ，i nr e f e r e n c e 3 a n dg o t s e r i e so fr e s u l t1 3 一引i n2 0 0 l ， k e n i c h ik a w a r a b a y a s h i ， k a t s u h i r oo t aa n d a k i r as a i t or e v e a l e dt h er e l a t i o nb e t w e e nd e g r e es u ma n dh a m i l t o np r o p e r t yo f 嚣一e x t e n d a b l eg r a p hi nr e f e r e n c e 4 a n dr e l a t i o nb e t l j i f e e n 刀一e x t e n d a b l eg r a p h a n dc o m p l e t eg r a p h sf u r t h e r m o r e i n1 9 9 6p r o f e s s o ray o n g g ab a s e do nd e g r e es u m o fg r a p ht h a td e g r e em o r et h a n3 ，g o tas u f f i c i e n tc o n d i t i o no ft r a c e a b l ei n r e f e r e n c e 5 i nt h isp a p e r ，b a s e do ns t u d ie so fa b o v ew ed is c u s st h et r a c e 曲l ep r o p e r t y o f刀一e x t e n d a b leg r a p hb yd e g r e es u m i ns e c o n dp a r t ， m a i n l yd i s c u s s e dt h ea b u n d a n tc o n d i t i o no ft h ee q u i v a l e n tp r o p o s i t i o no fh e d e t e n i e m i sc o n j e c t u r ec 0 1 0 r i n gp r o b l e mi saf o c u so f t h ep u b li c i ng r a p ht h e o r y c 0 1 0 r i n gp r o b l e mo r i g i n a t e df r o mav e r yf a m o u s c o n j e c t u r e f o u rc 0 1 0 rc o n j e c t u r e 6 p e o p l ec a p t u r et h i sc o n j e c t u r ei n d i f f e r e n tw a y ss i n c ei t i sp u tf o r w a r db y g u t h r e fi n 1 8 5 2 ， b u tt h e r eh a v e n ts t r i c ta n a 】y t i cp r o d fo fi t h e d e t e n i e m i s r e v e a l e d r e l a t i o nb e t w e e ne o l o ro ft j 】l f og r a p h sa n dt h e i rp r o d u c tb yac o n j e c t u r ei nr e f e r e n c e 7 ，c a l l e dh e d e t e n i e m i sc o n j e c t u r e h e d e t e n i e m i sc o n j e e t u r s t u d i e se 0 1 0 r i n gp r o b l e mi na l g e b r a i c 搬a y ， t h e r eh a v en op r o o fo f h e d e t e n ie m i sc o n j e c t u r ef o rg r a p h st h a td e g r e em o r et h a n5 b e n o itl a r o s e ， c 1 a u d et a r d i fs t u d i e dt h eh e d e t n i e m i sc o n j e c t u r ei nv i e wo fr e t r a c ta n d p r o v e dt h a tt h ec o n j e c t u r ei sh o l df o rv e r t e xt r a n s i t i v ec o r eg r a p h ，i fi t i sp r o j e c t i v e i nt h i sp a p e r ，w ep r o v e de q u i v a l e n c ep r o p o s i t i o no fh e d e t n i e m i sc o n j e c t u r ei st r u ef o rs o m es p e c i a lg r a p h sb a s e do nt h ea b o v er e s u l t so fs t u d ya n da b u n d a n tc o n d i t i o no fag r a p ht ob ec o r e k e y w o r d ：玎一e x t e n d a b l eg r a p h ，t r a c e a b i l 时 ，p r o d u c t ， c o r e ，r e s t r a c t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研 究工作及取得的研究成果，尽我所知，除了文中特别加以标注和 致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含本人为获得内蒙古师范大学或其它教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示感谢。 签名：重目托 日期： 枷扩年厂月7 日 关于论文使用授权的说明 本学位论文作者完全了解内蒙古师范大学有关保留、使用学 位论文的规定：内蒙古师范大学有权保留并向国家有关部门或机 构送交论文的复印件和磁盘，允许论文被查阅和借阅，可以将学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子 文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：童闩行导师签名：子盯秀嘿 日期：砌孑年厂月何日 内蒙古师范大学硕士学位论文 引言 本文中讨论的图均为简单图有关记号和术语请参考文献 卜2 1 9 5 7 年b e r g e 在文献 2 中首次提出n 一可扩路的问题，而自从p l u m e r 于1 9 8 0 年 在文献 3 中首次引入，l 一可扩图的概念以来，一些学者对可扩图的度和，可迹性， h 硼i l t o n 性等方面进行研究，并得到一系列成果p 5 1 2 0 0 1 年k e n i c h i k a w a r a b a y a s h i ，k a t s u h ir oo t aa n da k i r as a it o 关于，l 一可扩图的度和与哈密尔 顿性在文献 4 中证明了g 是p 阶连通的聆一可扩图且当仃2 ( g ) p 一以一1 时g 是 h 锄i l t o n 图或月= 1 且2 k l + 3 k 2c g ck 2 + 3 k 2 ，并将此结论推广到 ， 盯，( g ) 昙( p 一以一1 ) 时结论仍成立与此同时提出连通的，l 一可扩图中将条件降至 二 ， 盯，( g ) 詈( p 一2 以) 一2 时疗一可扩图的度和与h 锄i l t o n i a n 性之间关系的一个猜 二 想1 9 9 6 年阿勇嘎教授在文献 5 中将度和概念推广到图的子集上，证明了顶点数 玎3 的连通图g 有ssy ( g ) ，如果以( s ，g ) ，l ，则s 在g 中可迹或 c ( s ，g ) p ( s ，g ) 一1 本文在前人研究基础上，得到了一个推论和连通的，z 一可扩图可 迹的一个充分条件推论l 实际上是文中引理2 的推广，而定理l 强化对嚣一可扩图的度 和的限制条件，讨论了”一可扩图的可迹性 图论中图的着色问题是人们关注的一个焦点，着色问题起源于一个最著名的猜 想一四色猜想 6 英国人g u t h r e f 佛朗西斯古特里 于1 8 5 2 年提出四色问题( f o u rc o l o r p r o b l e m ，亦称四色猜想) ，对平面或球面上任意一个地图着色，至多用四种颜色， 就可以使两个相邻( 即有一段公共边界) 的图相或区域的颜色不相同1 9 7 6 年美国数 学家h a h n 哈肯 和a b e l 阿贝尔 花了1 2 0 0 多小时的电子讨算器工作时间，找到一个 由1 9 3 6 个可约构形所组成的不可免完备集，因而在美国数学会通报上宣称证明了四 色猜想后来他们又将组成不可免完备集的可约构形减至1 8 3 4 个但至今仍没有严格 的解析证明四色问题的研究对平面图理论、代数拓扑论、有限射影几何和计算器编 引言 码程序设计等理论的发展起了推动作用设g ，日是图，如果存在图矿( g ) 到图日的 映射厂：g 专日，对z ，j ，矿( g ) ，当x y 时厂( 工) 厂( y ) ，则称映射厂是图g 到日的 同态映射由此图的r 一正常着色用映射的语言叙述如下：如果g 是，一正常着色的， 则存在图g 到x ，的同态映射厂：g 专x ，即z ( g ) 厂我们可以证明，对任意两 个图g ，h ，如果存在图g 到日的同态映射，则z ( g ) z ( h ) 设是正常着色的， 则存在同态映射g ：日一k ，又因为存在图g 到日的同态映射，设为厂：g 专日， 则g 。厂是g 到x ，的同态映射因为x ，少y ( g ) ，当x 罗时由同态映射的定义有 厂( 石) 厂( y ) ，而厂( x ) ，( 少) 矿( h ) ，所以有科( x ) 卜烈厂( y ) 】即g 。厂是g 到k ，的 同态映射所以z ( g ) ，故z ( g ) z ( h ) 又因为直积g 日到g ，日都存在同 态映射，所以z ( g x 日) m i n 娩( g ) ，z ( ) ) h e d e t n i e m i1 9 6 6 年在文献 7 中根据不 等式z ( g h ) m i n 娩( g ) ，z ( h ) ) ，提出两个图与它们直积图色数之间关系的一个猜 想，即z ( g ) = m i n 娩( g ) ，z ( h ) ) ，用代数思想研究图的着色问题。根据以上分析 可知，证明h e d e t n i e m i 猜想关键是证明不等式z ( g h ) m i n z ( g ) ，z ( 日) ) h a j n a l 在1 9 8 5 年给出两个色数无限的无限图的直积图的色数却有限的例子，于 是h e d e t n i e m i 猜想对无限图不成立因此关于猜想人们只关注有限图到目前为止， 了对色数不大于4 的两个图已经证明了h e d e t n i e m i 猜想成立人们尝试用不同的方法 证明h e d e t n i e m i 猜想( 详见文献 8 1 0 ) ，得到了与猜想等价的一系列命题 1 8 郴】b e n o i tl a r o s e ，c 1 a u d et a r d if 1 1 1 1 从收缩的观点研究h e d e t n i e m i 猜想，提出 猜想的等价命题：完全图k 。是两个图直积的收缩当且仅当是其一个因子的收缩，同 时证明了对两个连通图猜想成立所以只需考虑不连通图的情形，但是猜想至今还未 被攻克本文证明了对几类特殊的图h e d e t n i e m i 猜想的等价命题成立 2 内蒙古师范大学硕士学位论文 第一章刀一可扩图的可迹性 本章，在文献 4 5 的研究基础上，根据图的三点独立集的度和证明了连通的咒一 可扩图可迹的一个充分条件 1 1 基本概念和引理 定义1 1 ”一个图g 是指一个有序三元组( y ( g ) ，e ( g ) ，妒g ) ，其中y ( g ) 是 非空的顶点集，e ( g ) 是不与y ( g ) 相交的边集，而是关联函数，它使g 的每条边 对应于y ( g ) 的无序顶点对( 不必相异) 定义1 2 【3 1 设g 是顶点数至少2 以+ 2 的图，如果每个含有刀条独立的边的匹 配都可以扩成g 的一个完美匹配，则称g 为以一可扩图。 定义1 3 设g 是图，v y ( g ) ，与，相连的边的条数称为v 的度，记为d ( d 定义1 4 2 1 设g 是图，g 中点度的最小值称为g 的最小度，记为万( g ) 定义1 5 5 1 设g 是p 阶的n 一可扩图，scy ( g ) 是独立集，定义 仃，( s ，g ) = m i n d ( t ) ：“，屯，z 3 ) cs 是g 的独立集) ， p ( s ，g ) = m a x f 矿( 一ns l ：p 是g 的一条路) ， c ( s ，g ) = m a x i y ( c ) n s l ：c 是g 的圈) 定义1 6 5 1 设g 是图，s 是g 的一个子集，如果p ( s ，g ) = l s i ，则称s 在g 中可迹 定义1 7 l5 1 设g 是图，s 是g 的一个子图，c 是g 的一个圈，如果 y ( c ) n s i = c ( s ，g ) ，则称c 为s 一最长圈 定义1 8 5 1 设g 是图，s 是g 的一个子图，c 是g 的一个圈，日是g y ( c ) 的 任一分支，如果旷( 日) ns f l ，则称c 是弱s 一控制圈如果旷( ) ns i o ，则 第一章玎一可扩图的可迹性 l y ( 日) | - 1 ，那么c 称c 为强s 一控制圈 定义1 9 【4 1 设肘是g 的一个匹配，彳，曰c 矿( g ) 定义 口m ( 彳，b ) = i ( 口，6 ) ：口彳，6 曰，口6 m ) i 定义1 1 01 5 】设g 是一个图，日是g 的一个子图，对z y ( g ) ，定义 珂( x ) = “y ( 日) ：l e ( g ) ) 且d ( 工) = p v ( x ) i 定义1 1 l 【5 】设g 是一个图，c 是g 的一个圈，用e 表示圈c 的某个方向，则e 表示与其相反的方向设“，矿( c ) ，则“芒、，表示“到v 的路，甜西表示v 到“的路 设1 ，是c 上的一个点，v + 和v 一分别表示v 的后继点和前继点如果彳cy ( c ) ，则定义 彳+ = ( 1 ，+ ：1 ，椰，彳一= p 一：y 么) 尸= h 女表示以u 为起点以k 为终点的一条路 引理1 m 】设，l 是正整数，g 是p 阶连通的刀一可扩图，如果盯，( g ) 三( p 一咒一1 ) 则 ( 1 ) g 是哈密尔顿图，或 ( 2 ) 玎= l 且2 k l + 3 足2c g ck 2 + 3 k 2 猜想1 【4 1 设，z 是正整数，g 是p 阶连通的，l 一可扩图，如果 仃，( g ) 三( p 一2 刀) 一2 ，则下列述语之一成立： ( 1 ) g 是哈密尔顿图， ( 2 ) ( 2 刀+ 2 ) k l + ( 2 k lu ( 2 刀+ 1 ) k 2 ) cg ck 2 。+ 2 + ( 2 k lu ( 2 刀+ 1 ) k 2 ) ， ( 3 ) g 是k 2 川+ ( 世ju ( 2 刀+ 1 ) k 2 ) 的一个导出子图， ( 4 ) g 是k 2 。+ ( 2 甩+ 1 ) k 2 的一个导出子图， ( 5 ) 咒= 1 且g 是k ：+ ( 2 k 2u k 。) 的一个导出子图， ( 6 ) 疗= 1 且2 k l 十( 2 k 2uk 6 ) cgc 足2 + ( 2 足2uk 6 ) ， 引理2 5 1 设g 是阶数玎3 的连通图，且s y ( g ) 如果仃，( s ，g ) ，l ，则s 在 g 中可迹或c ( s ，g ) p ( s ，g ) 一1 4 内蒙古师范大学硕士学位论文 引理3 4 1 设g 是力一可扩图， 对正整数小，如果聊，z ，则g 也是聊一可扩 的 1 2 主要结果和证明 根据引理2 得到下面推论： 推论1 设g 是p 阶连通的，l 一可扩图，且s y ( g ) ，如果仃3 ( s ，g ) 咒，则s 在 g 中可迹或c ( s ，g ) p ( s ，g ) 一1 证：根据以一可扩图的定义p 2 咒+ 2 4 ，因此g 是阶数p 3 的连通图，由 引理2 推论成立 为下面定理叙述方便，首先规定几个记号和术语 g 是连通图，s 矿( g ) ，尸= 而石。是g 的条路，j ，趴矿( 尸) ， 令么= ；( ) ，b = ；( 工。) 且d = p ( y ) 在以上几个引理研究基础上，本文主要证明了下面定理： 定理1 设g 是p 阶连通的盯一可扩图，p 6 ( 以+ i ) 对任意s 矿( g ) 和g 的一条 路尸= 而靠，如果吧( s ，g ) 妄( p 一2 刀) 一4 且集合彳= ；( ) ，矗：孵( ) 和 d = p ( y ) 满足下列条件 1 1 彳u 曰l l d i ， 2 矿( p ) d 的短节构成的集合恰好是彳u 曰， 则s 在g 中可迹或c ( s ，g ) p ( s ，g ) 一1 证：用反证法 设路尸= 而_ 是图g 的一条路，满足下列两个条件： ( 1 ) f 矿( p ) n s l 尽可能大； ( 2 ) l 矿( 用l 在条件( 1 ) 的前提下尽可能小。 假设s 在g 中不可迹且c ( s ，g ) p ( s ，g ) 一1 因为s 不可迹，所以根据可迹的定 义，s y ( p ) 非空令y s y ( 尸) ，由条件( 1 ) ，路尸的两个端点定属于s ，即 第一苹刀一可扩图的可迹性 ，x 。s ，不然与眇( p ) n s l 尽可能大矛盾而且由假设c ( s ，g ) p ( s ，g ) 一1 ，我们可 以断言： g 不含满足条件i y ( 尸) 矿( c ) i 1 的圈c ( 不然与 c ( s ，g ) 矿( c ) n s j _ p ( s ，g ) 一1 ，与假设矛盾) 又由断言知仨e ( g ) ，不然假 设x 。e ( g ) ，则g 中存在圈c 7 = 晟m 而，如图1 - 1 所示，使得旷( 一y ( c 7 ) l _ o 2 ，设鼻的起点是p ，终点是鸟，( 0 sf d 一口一6 ) 又因为l 鼻l 2 ，p ，g ，( o f j 一口一6 ) 令日= y ( p ) 一( 彳u 曰ud ) 以下对日和h = 分别进行讨论 a 当日矽时， 令f = m i n d 一口一6 + l ，村) ，令f = g o g ；，g l g ，g f i g 二i ) ，其中g ，胃， 9 7 d ( o f 一1 ) ，则f 是含有个独立的边的匹配，而g 是栉一可扩图，又由 f 的定义知f 咒所以根据引理3 ，g 也是f 一可扩的因此一定存在g 的一个完美匹配 m 包含f 因为9 f 日，酊d ( o f sf 1 ) 且f = m i n d 一口一6 + 1 ，刀) ，所以 ( h ，d ) f ，而hcy ( p ) 一彳ub ，再根据定理条件2 ，因为矿( p ) d 的短节构成的 集合恰好是彳u 曰，因此( h ，d ) = ( 矿( p ) 一彳u b ，j d ) = d 一口一6 o 这表明 ，d 一口一6 d 一口一6 + 1 因此由，的定义，我们得f = 刀和d 一口一6 刀因此 hu 彳u 引jd c y ( 尸) 且h ，彳，曰和d 俩俩不交，因此i y ( 尸) l 口+ 6 + d + f h i 由 r 内蒙古师范大学硕士学位论文 二二一 日：y ( 一一( 么u b u d ) 知尸一d 的长节都是日的分支，而p ，和g ，分别是那些长节 ( o f d 一口一6 ) 的起点和终点，所以鼽，吼y ( h ) 且p f g i ( 0 f d 一口一6 ) ， 因此 p 。，p l ，p 细一6 ，g i ，9 2 ，g 佃一6 ) = 日，所以旧i = 2 ( d 一口一6 + 1 ) ， 因此 i y ( d l 口+ 6 + d + 2 ( d 一口一6 + 1 ) 口+ 6 + d + 2 ，l + 2 或 d p ( x 。) + d p ( x 。) + d p ( y ) = l 彳l + l b l + l d i = 口+ 6 + d i y ( 尸) l 一2 ，l 一2 再令4 = 芦( ) ，目= 乒( ) 和d l = 乒( y ) ，其中芦= g y ( p ) 则根据断言， 4n 蜀：痧，不然假设z 4nb 。，则又可以找到g 的一个圈c = 晟。砜，如图 1 6 所示，使得l 矿( 尸) y ( c ) i = 1 ，这与断言矛盾 z 图1 6 且又根据( 1 ) 得4n q = 蜀nd l = 矿，不然假设z 4nq ，则g 中存在比路p 长 的一条路尸7 = 弘魏，如图1 7 所示这又与l y ( 尸) ns i 尽可能大的条件矛盾 冈此可以得到下面式子： y 图1 7 9 - _ j 工一2x 一lx 第一章刀一可扩图的可迹性 d 芦( ) + d 芦( ) + d 乒( y ) = l 彳l l + l b l l + l d 。l = 4u 骂ud l l l 矿( 芦) y ) i = p y ( p ) 一1 相加和两式得 仃3 ，g ) d ( ) + d ( x 。) + 矗( ) ，) p 一2 以一3 6 ( 咒+ 1 ) ，相加和式得 盯，p ，g ) d ( ) + d ( ) + d ( y ) sp 一1 吾( p 一2 ，z ) 一4 这又与盯，( s ，g ) 三( p 一2 咒)