（应用数学专业论文）连通性、邻域、路和圈.pdf

山东师范大学硕士学位论文 连通性 邻域 路和圈 陆联合 山东师范大学数学科学学院 济南 山东 2 5 0 0 1 4 中文摘要中又摘要 路和圈是图的两种基本结构 是分析和刻画图的有力工具 有大量的实际问 题可以归结为图的路和圈问题 所以这方面 直是图论中的热点研究领域 关于路 和圈的进展 已经取得长足的发展 这方面的研究成果和进展可见参考文献 事实 上 图论中三大著名难题之一的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 9 5 2 年和1 9 6 0 年 d i r a c 和o r e 分别用顶点的度作为条件研究路和圈问题 得到著名的d i r a c 定理和o r e 定理 1 9 8 9 年 朱永津提出图中顶点隐度的概念 1 9 8 7 年 f a u d r e e g o u l d j a c o b s o n s c h e l p 创立了n e i g h b o r h o o du n i o n sc o n d i t i o n s 从邻域的角度给出路和圈问题的充分条件 在本文第三 四章中将继续从邻域和隐 度的角度来探索路和圈问题的充分条件 在第一章中主要介绍本文的研究背景 已有的结果以及文章中所涉及的一些概 念和术语符号 2 0 0 6 年 刘晓妍提出了s 一点连通图的概念 在第二章中 提出更一般性的概 念 s 七 一连通图的概念 进而得到下面结果 定理2 2 1g 是n 阶 8 k 连通图 若s k 孕 则g 是路可扩的 推论2 2 2 g 是礼阶图 若k g 丝笋 则g 是路可扩的 在第三章中讨论邻域条件下图的路 圈 得到下面的结果 定理3 1 1g 是2 一连通图 若vv y g g n 2 是完全图 则g 是 泛圈的 1 山东师范大学硕士学位论文 定理3 1 2g 是2 一连通图 若vu y g g 2 u 是完全图 则g 是 可迹的 定理3 2 1g 是2 一连通图 若g 中导出 1 3 或甄 3 e 中的不相邻两 点让 口均有i n u u u l m m 是正数 则g 有h a m i l t o n 圈或者有长至少为 m 2 的圈 定理3 2 2 g 是2 一连通n 阶图 若g 中导出 1 3 或 1 3 e 中的不相邻 两点让 口均有i n u u 口 i 佗一6 则g 是h a m i l t o n 图 在第四章中 讨论了在隐度条件下h a m i l t o n 圈 推广了顾国华 卫兵 余荣 祖等人的结果 定理4 1 2g 是2 一连通礼阶图 若g 中满足i 牡 n i q g 一1 的不相邻两点牡 口均有d l u d l v 詈 6 g 则g 是h a m i l t o n 图 定理4 1 5g 是2 一连通n 阶半无爪图 a b 是g 中满足c f 2 o c f 2 6 几 不相邻两点 则g 是h a m i l t o n 图当且仅当g 曲是h a m i l t o n 图 定理4 2 2g 是2 一连通图 若对于g 中任意独立集s u u 伽 存在 x y s y 使得d 2 x 4 d 2 c c 是正数 则g 有h a m i l t o n 圈或者有长至 少为c 的圈 2 关键词 哈密尔顿 s k 连通图 邻域 隐度 分类号 0 1 5 7 5 山东师范大学硕士学位论文 c o n n e c t i v i t y u n i o n p a t h sa n dc y c l e s l i a n h el u s c h o o lo fm a t h e m a t i c a ls c i e n c e s s h a n d o n gn o r m a lu n i v e r s i t y j i n a n s h a n d o n g 2 5 0 0 1 4 p r c h i n a a b s t r a c t p a t h sa n dc y c l e sa r et w ob a s i cs t r u c t u r e so fg r 印h s i nf a c t m a n yp r a c t i c a l p r o b l e m sc a nb ea t t r i b u t e dt ot h ep r o b l e m so fp a t h sa n dc y c l e s t h e r e f o r e t h e r e s e a r c ha b o u tt h e mi sv e r ya c t i v e w h a ti sm o r e t h ef a m o u sh a m i l t o np r o b l e m i sa b o u tp 筑t h sa n dc y c l e so fg r a p hi ne s s e n c e a f t e rt h ed e v e l o p m e n tf o rd o z e n s o fy e a r s t h ec o n t e n t si np r o p e r t i e so fg r a p h s p a t h sa n dc y c l e sb e c o m em o r ea n d m o r er i c ha n ds p e c i f i c i n c l u d i n gh a m i l t o np a t h t r a c e a b i l i t y h a m i l t o nc y c l e l o n g e s tp a t h l o n g e s tc y c l e h a m i l t o n c o n n e c t e d p a n c o n n e c t i 访锣 v e r t e x p a n c y c l i c i t y p a t he x t e n d a b i l i t y c y c l ee x t e n d a b i l i t ya n ds oo n i n1 9 5 2a n d1 9 6 0 d i r a ca n d0 r es t u d i e dt h ep r o b l e m so fp a t h sa n dc y c l e s o nt h ec o n d i t i o no fv e r t e xd e g r e e o b t a i n e dr e s p e c t i v e l yt h ef a m o u st h e o r e m so f d i r a ca n do r e i n1 9 8 9 y o n g j i nz h up u tf o r w a r dt h ec o n c e p to fi m p l i c i td e g r e eo f g r a p h i n1 9 8 7 f a u d r e e g o u l d j a c o b s o n s c h e l pf o u n d e dn e i g h b o r h o o du n i o n s c o n d i t i o n s g a v et h es u 伍c i e n tc o n d i t i o n so ft h ep r o b l e m so fp a t h sa n dc y c l e sf r o m t h en e i g h b o r h o o d w ec o n t i n u et os t u d yt h es u 伍c i e n tc o n d i t i o n so ft h ep r o b l e m s o fp a t h sa n dc y c l e sf r o mt h en e i g h b o r h o o da n di m p f i c i td e g r e ei nt h et h i r da n d f o u r t hc h a p t e ri nt h i sp a p e r i nt h e 缸8 tc h a p t e r w eg i v eab r i e fi n t r o d u c t i o na b o u tt h eb a s i cc o n c e p t s t e r m i n o l o g i e sa n ds y m b o l sw h i c hw i l lb eu s e di nt h i sp a p e r i nt h em e a n t i m e w e a l s oo b t a i ns o m er e l a t e dr e s e a r c hb a c k g r o u n d sa n ds o m ek n o w nr e s u l t s i n2 0 0 6 x i a o y a nl i up u tf o r w a r dt h ec o n c e p to fs v e r t i c e sc o n n e c t e dg r a p h i nt h es e c o n dc h a p t e r w eg i v eag e n e r a lc o n c e p t s k c o n n e c t e dg r a p h a n d o b t a i nt h ef o l l o w i n gr e s u l t s 3 山东师范大学硕士学位论文 t h e o r e m2 2 1l e tgb ea s 忌 一c o n n e c t e dg r a p ho fo r d e rn i f8 一 s 孚 t h e ng i sp a t he x t e n d a b l e c o r o l l a r y2 2 2 l e tgb eag r a p ho fo r d e rn i fk g t n l t h e ngi s p a t he x t e n d a b l e i nt h et h i r dc h a p t e r w ed i s c u s st h ep a t h sa n dc y c l e so fg r a p ho nt h ec o n d i t i o n o fn e i g h b o r h o o d w em a i n l yo b t a i nt h er e s u l t sa sf o l l o w s t h e o r e m3 1 1l e tgb ea2 c o n n e c t e dg r a p ht h a tg n 2 u i sc o m p l e t e g r a p hf o re v e r yv e r t e xv i ng t h e ngi sp a n c y c l i c t h e o r e m3 1 2l e tcb ea2 c o n n e c t e dg r a p ht h a tg n 2 i sc o m p l e t e g r a p hf o re v e r yv e r t e xv i ng t h e ngi st r a c e a b l e t h e o r e m3 2 1l e tgb ea2 c o n n e c t e dg r a p hs u c ht h a tl n u u i m mi sap o s i t i v en u m b e r f o re a c hp a i ro fn o n a d j a c e n tv e r t i c e sua n dv t h a ta r e v e r t i c e so fa ni n d u c e dc l a wo ra ni n d u c e dm o d i f i e dc l a wo fg t h e ngc o n t a i n s e i t h e rah a m i l t o nc y c l eo rac y c l eo fl e n g t ha tl e a s tm 2 t h e o r e m3 2 2l e tgb ea2 c o n n e c t e dg r a p ho fo r d e rns u c ht h a t i 乱 u 口 l 礼一6f o re a c hp a i ro fn o n a d j a c e n tv e r t i c e sua n dvt h a ta r e v e r t i c e so fa ni n d u c e dc l a wo ra ni n d u c e dm o d i f i e dc l a wo fg t h e ngi sh a m i l t o n i a n i nt h ef o u r t hc h a p t e r w ed i s c u s sh a m i l t o nc y c l eo nt h ec o n d i t i o no fi m p l i c i t d e g r e e i m p r o v es o m ec o r r e s p o n d i n gr e s u l t so fg u o h u ag u b i n gw e i r o n g z uy u e t c t h e o r e m4 1 2 l e tgb ea2 一c o n n e c t e dg r a p ho fo r d e rns u c ht h a t d l u d l v 之詈 艿 g f o re a c hp a i ro fn o n a d j a c e n tv e r t i c e s ua n dvw i t h l u n u j 口 g 一1 t h e ng i sh a m i l t o n i a n t h e o r e m4 1 5l e tgb ea2 c o n n e c t e dq u a s i c l a w f r e eg r a p ho fo r d e rn s u c ht h a td 2 a d 2 6 礼f o re a c hp a i ro fn o n a d j a c e n tv e r t i c e saa n dbi nc t h e n gi sh a m i l t o n i a ni fa n do n l yi fg a bi sh a m i l t o n i a n 4 t h e o r e m4 2 2l e tgb ea2 c o n n e c t e dg r a p h i ft h e r ee x i s tx y s x 山东师范大学硕士学位论文 y s u c ht h a td 2 z d 2 y c ci sap o s i t i v en u m b e r f o re v e r yi n d e p e n d e n ts e t s 札 口 伽 i ng t h e ng c o n t a i n se i t h e rah a m i l t o nc y c l eo rac y c l eo fl e n g t ha t l e a s tc k e y w o r d s h a m i l t o n s 七 一c o n n e c t e dg r a p h n e i g h b o r h o o d i m p l i c i t d e g r e e c l a s s i f i c a t i o n 0 1 5 7 5 5 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果 据我所知 除了文中特别加以标注和致谢的地方外 论文 中不包含其他人已经发表或撰写的研究成果 也不包含为获得 注 如没有其他需要特别声明的 本栏可空 或其他教育机构的学位或 证书使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意 黝姗貅降黔一字 鹕 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留 使用学位论文的规定 有 权保留并向国家有关部门或机构送交论文的复印件和磁盘 允许论文被查 阅和借阅 本人授权学校可以将学位论文的全部或部分内容编入有关数 据库进行检索 可以采用影印 缩印或扫描等复制手段保存 汇编学位论文 保密的学位论文在解密后适用本授权书 靴敝一名 酗黔 签字日期 2 0 0 9 年舻月厂日厂 月 焉锋 名9 加 事 期 签 唱 芹 r 耀 字 斟 签 山东师范大学硕士学位论文 第一章预备知识 1 1符号概念介绍 本文仅考虑有限无向简单图 所使用的记号和术语约定如下 其中未加说明 的部分请参照文献 1 设g 是 个图 v g e c 分别表示g 的顶点集和边集 对s tcy g a v g 以及g 的子图日 令 n 8 口 s a v e g n h 口 a v 日 口 n h s u s n h u 巧 g m i n n c u i 钞 y g e st s t e g s 墨t t n c v 也筒记为n v 图g 中与点移关联的边的数目叫做顶点移的度 记为 如 口 即d g v 口 在不引起混淆的情况下简记为d 秒 用如和 g 分 别表示g 中顶点的最小度和最大度 也常常简记为瓦 即石 m i n d v y g m a x d v u y g i g i i y g i 称为图g 的阶 g 的由s 导 出的子图记为g 翻 如果g s 不连通 则称s 为g 的一个顶点割 g 中含顶 点最少的顶点割叫g 的最小顶点割 最小顶点割中顶点的数目称为g 的连通度 记为k g 完全图j 厶的连通度定义为k k n 一1 如果心 g k 则称g 是k 一连通的 1 一连通图也叫连通图 显然 若g 是肛连通的 则v v c g 一 口 是 k 一1 一连通的 设s k 是满足s k 1 的整数 如果对任意满足i s i s 的子集scv g g 旧是珏连通的 则图g 叫做 s 连通图 s k 连通图有如下性质 性质设图g 是 s k 连通图 则 1 g 是 8 1 k 1 一连通图 2 g 是 s 1 七 一连通图 经过图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 图 经过图g 每个顶点恰好一次的路叫g 的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 路 则称g 是h a m i l t o n 连通的 设c 是g 的一个非h a m i l t o n 圈 如果g 中存在圈c 使y c cy c 6 山东师范大学硕士学位论文 且l v o i l y g i 1 则称圈c 是可扩的 同时称 为c 的一个扩圈 如果 图g 中每一个非h a m i l t o n 圈都是可扩的 则称图g 是圈可扩的 如果图g 的每 个顶点都在长度为3 的圈上 并且g 是圈可扩的 则称图g 是完全圈可扩的 以 顶点t 口为端点的路称为 仳 u 一路 设p 是图g 中一条 缸 u 一路 如果g 中存 在 牡 u 路尸 使v p cv p 且i y p i l v p i i 则称路p 是可扩的 同 时称p 为p 的一条扩路 如果图g 中每一条非h a m i l t o n 路都是可扩的 则称图g 是路可扩的 设p 1 忱 为g 的一条路 q y p 1 i 设d l 如 d k d k 1 d k 2 是g v t o 飓 u 中顶点的度序 列 则定义u 的两种隐度d l v 和如 如下 如 m a x m 2 七 1 如果d k 1 否则 如果d k k 1 的整数 如果对任意满足l s i 8 的子集sc y g g 翻是七一连通的 则图g 叫做 s 七 一连通图 性质2 1 1 图g 是 s 七 一连通图 则 1 g 是 8 1 k 一1 连通图 2 g 是 s 1 七 一连通图 证明 1 对vtcy g i t i s 一1 取v v a 一t 则g tu 是k 一连通的 于是g 闭 g tup 一 u 是 k 一1 连通的 所以g 是 s 一1 k 一1 连通图 2 否则 存在ucy g i u i 8 1 使k g 明 k 于是有 配l w i k 一1 使c u 一 不连通 在g 明一w 的不同分支中取 8 一 k 一1 8 一k 1 2 个顶点构成集合s 易知形也是c wu 翻的顶点 割 但是i us i i w i i s l s 这与g 是 s 七 一连通图矛盾 性质2 1 1 证毕 由性质2 1 1 2 知 s k 连通图是后一连通的 性质2 1 2 图g 是 s k 连通图 则k g 几一s k 证明 由性质2 1 1 1 知 g 是 s 一 七一1 1 一连通图 即g 中任意s k 1 个顶点的导出子图是连通的 换言之 对vscy g l s l 佗一 8 一k 1 n s k 一1 g s 是连通的 所以k g 佗一s k 1 2 山东师范大学硕士学位论文 性质2 1 2 证毕 引理2 1 3 1 6 g k g 1 3 山东师范大学硕士学位论文 2 2 8 七 一连通图的路可扩性 本节在 2 1 节的基础上 给出如下定理 定理2 2 1g 是佗阶 s 忌 一连通图 若s k 孚 则g 是路可扩的 证明 首先g 是连通的 由8 一k 孚得佗 2 s k 1 由性质2 1 2 有 6 g k g 佗一s k 1 一s k s k 1 车 由性质2 1 1 1 知 g 是 8 一 k 一1 1 一连通的 即g 中任意s k 1 个 点的导出子图是连通的 结合 木 有 论断1 1 vtcy g 若i t i s k 1 则g 吲是连通的 2 v 口 y g g i n v 是连通的 设p v l v 2 是g 中任意一条路 且i 尸i d h v 时 此时n h v i 乃 令嵋 讨 u 一 u p 讨 l 啊c 寸川 麓藩 1 量 茎麓嚣j 总之 l 昨 时 l i n p v l 一1 又雌 讨 nn h v 1 j 2 f 所以 i 雌 订 u 日 忱 i i 昨 谚 i4 i n i l v i d p 谚 一1 4 d 日 优 d p 讨 一1 d u 时 d 时 一1 兰6 g 一1 即i 雌 时 t jn h v i i 6 g s k4 1 由论断1 知 g 雌 矿 u 蜥 忱 连通 故刍t r n h v i y 雌 时 使 x y e g 与论断3 矛盾 情形2 当d h v i d v 优 一1 妇 仇 d 饥 一1 6 g 一1 即l 畦 忱 u 日 时 i 6 g 8 一k 1 由论断1 g 睇 优 u 讨 是连通的 故3z 日 讨 y 苫 忱 使x y e g 与论断3 矛盾 综上述 v v p 一 仇 吻 有如 一 妇 u 妇 再结合论断2 即得d n v 一 d h 妇 矿 0 论断4 证毕 论断5 仇吻 e g 歹 2 3 p 证明 否则 路尸上有点 1 s k 1 由论断1 知 g n v j u n h v f 是连通的 故3z 蜥 丐 y 啊 使x y e g 此与论断3 矛盾 论断5 证毕 考虑点 0 2 因为g 忱 连通 而且由论断4 知 忱 刀 所以 n h v 2 y n p v 2 使x y e g 由论断3 1 知 y y v p v p 由论断5 知 钞1 一 e g 于是 1 6 山东师范大学硕士学位论文 是p 的扩路 矛盾 定理2 2 1 证毕 v l y p 忱x y p v p 注 下面构造图g 1 g 2 说明定理2 2 1 中的条件s k 旦 是最好可能的 设g l 艺是两个顶点不交的图 且g l 謦j 厶一k 竺g 2 它们的顶点集合分别为 y g 1 v l 忱 一七 v g 2 u l 坳 u 一七 用g 1 g 2 表示其顶点集和边集分别为v v 1fj i g 2 y g 1 uv g 2 和 e g l i i i g 2 e g 1 u e g 2 u 乱i 忱 i 1 2 s k 的图 此图是n 2 s k 阶 8 k 连通图 且s k 署 但它不是路可扩的 推论2 2 2 g 是n 阶图 若k g 学 则g 是路可扩的 证明 由仡 g 的定义可知 对g 中任意一个含k g 一1 个顶点的集合 scy g g s 一定是连通的 换言之 g 中任意礼一 k g 一1 死一k g 1 个 顶点的导出子图是连通的 即g 是 8 七 一连通图 这里的s 几一k g 1 k 1 又因为 s k 扎一k g 1 一1 n k g n 一业2 1 n r 1 由定理2 2 1 知 g 是路可扩的 推论2 2 2 证毕 1 7 山东师范大学硕士学位论文 第三章邻域条件下图的路 圈 度和邻域一直是研究路 圈问题的重要条件 本章将从邻域的角度研究图的 路 圈问题 3 1 2 u 条件下图的路 圈 对于图g 中的顶点u 我们用 乞 u 表示图g 中与 的距离为2 的顶点组成 的集合 即 2 口 u i u y g d u 2 定理3 1 1g 是2 一连通图 若v y g g n 2 是完全图 则g 是 泛圈的 证明 设图g 满足定理的条件 圈c v l 忱 协是图g 中长为r 的圈 假 设图g 不存在长为r 1 的圈 日是g v c 的一个分支 论断1vx v e h y c h y c 1 z t z u 一隹e g 2 口一u e g 证明 1 否则易得到长为r 1 的圈 2 由 1 知d x 町 2 d z 讨 又g 2 是完全图 有 u v e g 论断1 证毕 情形1 日中存在一点z 使l n o z i 之2 设仇 v l y c i 歹 使她 z e g 可知i 讨c 叮i 1 否则有长为 r 1 的圈 当i v j c v i i 0 时 圈x v i c v 了x 是长为7 1 的圈 矛盾 当1 c 仇i 1 时 论断2 订 访2 f 町 证明 因为d z 町 d 时 2 故町讨 e g 又z 时2 隹e g 否则 有长为r 1 的圈 故d z 付2 2 d z 叮 因而有町时2 e g 同理可证 町时3 町 f e g 论断2 证毕 1 8 山东师范大学硕士学位论文 根据论断2 知 可得到长为r 1 的圈 x v i c v f v c v j x 矛盾 情形2 日中任意一点z 均有i 心 z i 1 因为g 是2 一连通的 所以jz y z y h jv i i j y c 使 z 仇 秒 e g 子情形1x y e c 1 当i 时c 口f l 1 且l v c v l 0 时 若j c i 3 此时可得到长为4 的圈 x v l v 3 y x 矛盾 若旧 4 因为v i v e g 有v i v 2 e g 否则d v i 讨2 2 d v i y 2 则可时2 e g 矛盾 此时得到长为r 1 的圈 z 仇讨2 c v j y x 矛盾 2 当i 寸c f i 0 且i u 产g 町i 1 时 类似以上讨论同样可得到长为r 1 的圈 矛盾 3 当l 时c f i 1 且i u 产c 町i 1 时 首先由论断2 知 讨 访2 f 町 此时得到长为r 1 的圈 v i c v 7 2 v c v 了y x 矛盾 子情形2x y 簪e g 此时d x y 2 记 z 一路为 z 让1 u 2 箩 则d z 坳 2 又d x 谚 2 d x 町 故u 2 v e g 坳町 e g 此时i u 2 i 2 矛盾 定理3 1 1 证毕 定理3 1 2g 是2 一连通图 若v 口 y g g 飓 u 是完全图 则g 是 可迹的 证明 设g 满足定理条件 假设g 不是可迹的 则设p v l v 2 吻是g 中 最长的路 日是g v p 的一个分支 又g 是2 一连通的 故i p 日 l 2 因 而jz y h x y 可能相同 协 吻 y p t 歹 使x v i y v l e g 由p 是最 长路知 仇 吻 在日中以z y 为端点的路记为x p y 论断1vx v i e g y 尸 h 协 y p 贝0 1 z 可 z 时譬e g 2 町讨 刀 g 证明 1 很显然易得 2 由 1 得 d z 町 2 d z 时 由g 2 是完全图知 町时 e g 论断1 证毕 1 9 论断2 证明 讨p 丐l 3 当l 讨p 口7 i 0 时 此时可得到长于p 的路 v l p v i x p 7 y v j p v p 矛盾 当i 讨p u i 1 时 此时可得到长于p 的路 v l p v v v i x p 7 y v j p v p 矛 当 v p v 7 2 时 此时可得到长于p 的路 u 1 p 町讨忱z p y v j v 于v p v p 矛盾 一 论断2 证毕 情形1 z e c 此时d x 町 2 d x 时 由g 2 是完全图知 v i 一丐 e g 则得到长于p 的路 v l p v v j p v i x t 7 y v i p v p 矛盾 情形2 x v j 聋e g 此时z y 假设d z y 2 以z y 为端点的路 d z u 2 2 又d z 讨 一2 由g 2 是完全图知 p 7 z y z u l 也 y v u 2 e g 则 此时可得到长于p 的路 1 钞1 p v i x u l u 2 v p 吻 矛盾 因而y 让1 又d z 吻 2 d z 讨 由g 2 u 是完全图知 寸 e g 此时可得到长于p 的路 口l p 仇z 可 讨尸哼哼p 矛盾 定理3 1 2 证毕 山东师范大学硕士学位论文 3 2 虬 3 或硷 3 e 条件下图的路 圈 对定理1 2 1 3 和1 2 1 4 中两点 进一步限制 它们是g 中导出甄 3 或 风 3 e 中的不相邻的两点 这样得到下面定理3 2 1 定理3 2 1g 是2 一连通图 若g 中导出k 1 3 或k t 3 e 中的不相邻两 点乱 均有i n u u j m m 是正数 则g 有h a m i l t o n 圈或者有长至少为 m 2 的圈 证明 假设g 不是h a m i l t o n 图 下证g 的最长圈的长度不小于m 2 取g 中最长路p v l v 2 有n v 1 un v p y p 因为g 是2 一连 通的 故在p 上除了v 2 点外至少还有一点与u 1 相邻 设眈与 1 相邻 在所有以吻为端点的等长度的最长路中取i 尽可能的大 即i p m 觚俐 1 优 e g 假设g 的最长圈长度小于m 2 这时i m 2 论断li p 证明 假若i p 当p 佗时 g 有h a m i l t o n 图 矛盾 当p 佗时 g 为2 一连通的 此时g 含有长于p 的路 矛盾 论断1 证毕 论断2n v 1 忱 忱 忱 证明 假设n v 1 v 2 s 仇 因为p 是最长路 所以n v 1 冬 y p 0 2 3 t 一1 因为g 是2 一连通的 故g 一 饥 连通 故存在 s 亡 s i i p 矛盾 论断2 证毕 取协聋 u 1 且使r 尽可能大 这时 1 协隹e g 论断3 如果r 2 i 有协协 2 e c 证明 假设协珥 2 譬e g 而v l v r 2 e g 这时 笺蜀 3 e 由定理条件知 又n v 1 u t j r t j 2 优 这时 u 1 珥 1 v l v i e g n v 1 u 坼 i m 2 1 山东师范大学硕士学位论文 矛盾 论断3 证毕 n v 1 u 坼 l i 一2 m 2 2 m 如果r 3 i 时 类似于论断3 可证 珥 3 e g 依次讨论下去进而可有珥忱 e g 又协仇 1 譬e g 有 笺甄 3 由定理条件知 i n v 1 u 协 i m 又n v 1 u t j 2 忱 这时 矛盾 定理3 2 1 证毕 n v t u 坼 l t 一2 m 2 2 m 对定理1 2 1 5 和1 2 1 6 中两点让 进一步限制 它们是g 中导出虬 3 或 k x 3 e 中的不相邻两点 这样得到下面定理3 2 2 定理3 2 2g 是2 一连通n 阶图 若g 中导出尬 3 或跹 3 e 中的不相邻 两点乱 均有l n u u u i 佗一6 则g 是h a m i l t o n 图 证明 设g 满足定理条件 c v l 2 是g 中最长的圈 日是g c 的一个分支 因g 是2 一连通的 故 忱 v 1 y c i 歹 刍z y h x y 可能 相同 使得x v i y v l e c 且仇 1 v i 2 一1 和z y 都不相邻 论断1 1 z 饥一1 x v i 1 隹e g 2 v i 1 u 1 芒e g 3 v g c 仇 1 nn c c 1 历 4 n v i 1 un v j 1 n 舫 z g 5 n v i 1 un v j 1 n n h z g 证明 否则 容易得到长于c 的圈 矛盾 论断1 证毕 因为t j 件1 1 萑e g 故d v i l 1 2 情形1 当d 讧 1 1 2 时 论断2i 饥 1 u 吻 1 i n 一6 证明 因为n a g 仇 1 c l n c c v j 1 j 2 f 所以 v k y c 使得仇仇 1 v k v l f j a 1 当k 歹 2 歹 3 i 一1 时 又仇 1 十1 隹e g 故 v k 优 1 吻 1 o k l k 1 3 e 因而j 仇 1 un v j 1 i 礼一万 2 当k 0 2 i 3 歹一1 时 又 v k l o i 1 e g 故 竺t 1 3 或 兰 竺k 1 3 或 垒 此时砚一1 v 1 隹刀 g 故 型k 1 3 或 笺k 1 3 e 因而l 吣1 uu v j 1 l n 一6 4 当k 歹时 此时饥一1 1 隹e g 故 垒t 1 3 或 笺k 1 34 e 因而i 坼1 un v j a l 礼一万 论断2 证毕 因为 i n v i 1 un v j i 扎一 i u 苫 x u k z 1 一i z 扎一d z 一1 n 一6 1 n 一6 这与论断2 矛盾 情形2 当d 饥 1 吻 1 3 时 由论断1 1 知 笺k 1 3 或 竺 1 3 e 故l u z u 忱 1 i n 一6 取z 1 1 当z n a o v j 1 时 由论断1 可知z 和z 0 i 1 均不相邻 2 当名 n o u 件1 时 若z 忱 2 c 吻一1 则点名与z t 3 i 1 均不相邻 因为d v i x 1 3 和z 剪 山东师范大学硕士学位论文 的选择 2 4 若z y 2 c v d 则点z 一与x v i 1 不相邻 否则有长于c 的圈 根据上面 1 和 2 的讨论知 n v i 1 u i 几一l n o v j 1 ug c g 1 一 v a i i z q 1 佗一 d v j 1 一1 一2 n d 1 一1 几一6 1 礼一6 矛盾 定理3 2 2 证毕 山东师范大学硕士学位论文 第四章隐度条件下图的路 圈 度一直是研究路 圈问题重要条件之一 本章将从隐度的角度来研究图的路 圈问题 4 1隐度条件下图的h a m i l t o n 圈 1 9 9 6 年顾国华 赵俊得到 定理4 1 1 1 2 1g 是2 一连通礼阶图 若g 中满足i n u n u l 口 g 一1 的不相邻两点心 均有d u d v 詈 6 g 则g 是h a m i l t o n 图 将定理4 1 1 推广到隐度条件下得到 定理4 1 2g 是2 一连通礼阶图 若g 中满足i n u n 口 l 口 g 1 的不相邻两点t 均有d l u d l v 量 6 g 则g 是h a m i l t o n 图 引理4 1 3 n 设g 是2 一连通图 并且p v l v 2 坳是g 中一条最长路 如果d v 1 d l v 1 且 1 吻萑e g 则j 协 n v 1 使得d v i d l v 1 下面是定理4 1 2 的证明 证明 反证法 假设g 是极大的非h a m i l t o n 图 论断1g 中任意不相邻两点u 均有i n u nn v i 口 g 一1 证明 因为g 是极大的非h a m i l t o n 图 则g 让u 是h a m i l t o n 图 则g 中 存在一条以仳 u 为端点的h a m i l t o n 路 记为p u 仇忱 v p v l 牡 吻 u 设n u nn v 忱 仇 仇 2 i l i 2 i 仇 佗一1 假若i n u n u i a g 则m q g 令s 咭 呓 吃 1 由 口 g 定义知 s 不是独立集 故jz y s 使x y e g 当z 口l y 畦 1 k m 此时g 有h a m i l t o n 圈 v l 吃p v p v i i p v l 矛盾 当z 咭 y 呓 1 t d v 1 时 由引理4 1 3 知 jv i n v 1 使d v i d l 研 1 当d v p d l v p 时 则g 有h a m i l t o n 路 p 7 池 v i p v l v i 1 p 吻 此时d v i d v p d l v 1 d l v p 鸶 6 g 又他 碧e g 由论断1 知 i n v i f l 吻 i 及 g 一1 再由定理4 1 1 知 g 是h a m i l t o n 图 矛盾 2 当d v p d l 吻 时 讨论h a m i l t o n v i 路 由引理4 1 3 知 jv j 吻 使d 吩 d l v p 贝0g 有h a m i l t o n 路 p 7 v i p 铷 1 p v i 此时d d v i d l v p d l 1 詈 6 g 又v j v i 隹e g 由论断1 知 l 叼 n n v i l q g 二1 再由定理4 1 1 知 g 是h a m i l t o n 图 矛盾 情形2 当d l v 1 d v 1 时 此时d l v 1 d 饥 6 g 又d l v 1 d l v p 芝量 6 g 故d l v p 号 又g 是2 一连通的 所以在p 上除忱点外至少还有一点与 l 相邻 设 m m a x i l v t v i e g 论断3v l v i e g 2 i m 证明 假若存在某个k 3 七 仇一1 使得k 是v l v k 隹e g 最大下标 则 仇魄 1 e g 此时g 有h a m i l t o n 路 p 7 讥 坳 k p 1 v k 1 p 坳 又由论断1 知 i n v 1 n n v 七 i q g 一1 再由条件知 d l v k 詈 从而d l v k d l v p n 又仇 隹e g 故g v k v p 是h a m i l t o n 图 由定理1 2 2 3 知 g 是h a m i l t o n 图 矛盾 论断3 证毕 同时对vj 1 j 仇一1 有吩吻 e g 否则g 有h a m i l t o n 圈 又 d v l v p 2 所以v m v p e g 令h 1 v m 2 又v l i 譬e g m 1 i p 由论断1 及定 理的条件知 日中每个点仇的均有d l v i 等 由论断2 知 c h 是完全图 又 g 是2 一连通的 g 一 讥 仍连通 故 s 和t 2 s m 一1 m 1 t p 一1 使 仇 e g 此时g 有h a m i l t o n 圈 u 1 p 饥p t k 1 仇 1 p t h p 1 u 1 矛盾 山东师范大学硕士学位论文 定理4 1 2 证毕 当只关注无爪图时 余荣祖 陈冰把定理1 2 2 3 作如下推广 定理4 1 4 1 4 g 是2 一连通n 阶无爪图 a b 是g 中满足d 2 a d 2 6 n 不相邻两点 则g 是h a m i l t o n 图当且仅当g 曲是h a m i l t o n 图 将定理4 1 4 推广到半无爪图时 得到 定理4 1 5g 是2 一连通礼阶半无爪图 a 6 是g 中满足d 2 a d 2 b n 不相邻两点 则g 是h a m i l t o n 图当且仅当g 口6 是h a m i l t o n 图 引理4 1 6 n 设g 是2 一连通图 并且p v l v 2 吻是g 中一条最长路 如果d v 1 d a 4 d b 不妨设如 o d n 由引理4 1 6 考 虑下面两种情况 在每种情况下 均能得到g 的一条h a m i l t o n 吻一路 使得这条 路的另一端点移满足d v d 2 o 情形ljv i n 一 口 使得d 忱 d 2 口 在这种情形下 p 7 仇 b 仇仇一1 仇地十l v i 2 t 6 p 是g 的一条使得d v i d 2 a 的h a m i l t o n 一路 情形2 对v 仇 n 一 口 均有d 忱 d 2 o 由引理4 1 6 知 有g a 忱 v 3 且对每一个顶点仳 2 口 都有 d 乱 如 口 g 是2 一连通的 故g 一 连通 则一定存在一条满足r m 8 的边协 e g 按以下两个条件选择边 2 7 山东师范大学硕士学位论文 1 s 尽可能的大 2 在满足 1 的条件下 7 尽可能的大 由珥 的取法 显然 d v s d 2 a 假若s p 则g 有h a m i l t o n 圈 v l p 协吻7 l v l 矛盾 故s p 一1 子情形1 s m 4 若嘶 一1 e g 则 一1 ja 且d 一1 d 2 a 此时 尸7 一1 b 一l v s 一2 1 v l v 2 协 1 咋是g 的一条使得d 一1 如 口 的h a m i l t o n 一路 若蜥 一1 萑e g 根据协和 的选择 有体 1 萑e g 故d t j r v s i 2 又g 是半无爪图 j 忱 j 珥 v s 1 且 h 协 u 1 1 当仇 时 仇一1 u 1 又协 一1 隹曰 g 故 一l v 卧1 e g 此时p 吻 v s v r v r 一1 v l v r l v r 2 v