（应用数学专业论文）几乎自补图的直径和色数.pdf

ab s t r a c t a g r a p h g i s c a l l e d s e l f - c o m p l e m e n t a ry g r a p h , i f it i s i s o m o r p h i c t o i t s c o m - p l e m e n t s . s i mi l a r l y , a g r a p h g w i t h e v e n n u m b e r o f v e rt i c e s i s c a l l e d a lmo s t s e l f - c o m p l e m e n t a ry , i f i t i s i s o mo 印h i c t o o n e o f i t s a l m o s t c o m p l e m e n t s g 一m: g= g 0 一m, w h e re m d e n o t e s a p e r f e c t m a t c h i n g i n i t s c o m p l e m e n t g .i n t h i s p a p e r , w e p a y a t t e n t i o n t o t h e p ro p e rt i e s a n d d i ff e r e n c e b e t w e e n t h e s e l f - c o m p l e m e n t a ry g r a p h s a n d t h e a l m o s t s e l f - c o m p l e m e n t a ry g r a p h s . i n c h a p t e r 3 , w e m a i n l y c o n s i d e r t h e d i - a m e t e r a n d c h r o m a t i c n u m b e r o f t h e s e l f - c o m p l e m e n t a ry g r a p h s . i n c h a p t e r 4 , b a s e d o n t h a t , w e p r e s e n t s o m e p r o p e rt i e s o f a lm o s t s e l f - c o m p l e m e n t a ry g r a p h s a n d p r o v e s o m e r e s u l t s a b o u t t h e d i a m e t e r a n d c h r o m a t i c n u m b e r o f a l m o s t s e l f -c o m p l e m e n t a ry g r a p h s . w e s h o w t h a t t h e d i a m e t e r o f c o n n e c t e d a l m o s t s e l f - c o m p l e m e n t a ry g r a p h s mu s t b e 2 , 3 o r 4 , a n d c o n s t r u c t c o n n e c t e d a l m o s t s e l f -c o m p l e m e n t a ry g r a p h s w i t h 2 n v e r t i c e s h a v i n g d i a m e t e r 3 , 4 f o r e a c h n 3 a n d d i a m e t e r 2 f o r e a c h n _ 4 re s p e c t i v e l y . i n a d d it i o n , w e a l s o o b t a i n t h a t f o r a n y a l m o s t s e l f - c o m p l e m e n t a ry g r a p h氏 w i t h 2 n v e rt ic e s , 而 1 x (g n ) :5 。 . b y c o n s t ru c t io n , w e v e r ify th a t th e u p p e r b o u n d is a v a i l a b l e f o r e a c h p o s i t i v e i n t e g e r ， a s w e l l a s t h e l o w e r b o u n d i s a v a i l a b l e i f 而 is p o s i t i v e i n t e g e r . k e y w o r d s : s e l f - c o m p l e m e n t a ry g r a p h , a l m o s t s e lf - c o m p le m e n t a ry g r a p h , d i a m - e t e r , c h r o ma t i c n u mb e r . mr s . c .( 2 0 0 0 ) : 0 5 c 1 2 , 0 5 c 1 5 , 0 5 c 6 0 南开大学学位论文版权使用授权书 本人完全 了 解南开大学关于收集、保存、使用学位论文的 规定， 同 意如下各项内容:按照学校要求提交学位论文的印刷本和电子版 本;学校有权保存学位论文的印刷本和电 子版，并采用影印、缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供目 录检索以及提供 本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国 家有 关部门 或者机构送交论 文的复印件和电子版; 在不以 赢利为目的的前 提下， 学校可以 适当复制论文的部分或全部内 容用于学术活动。 学 位 论 文 作 者 签 名 :i 奔 -o v 了 年 月 砰日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名: 净子 ， s il a t, / - - / 一 学位论文作者签名: 安 萍 解密时间:年月日 各密级的最长保密年限及书写格式规定如下: 内部 5 年 最长5 年， 可少子5 年) 秘密*1 0 年 ( 最长1 0 年， 可少于1 0 年) 机密2 0 年 ( 最长2 0 年，可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学位论文， 是本人在导师指导下， 进行 研究工作所取得的成果。 除文中已 经注明引 用的内 容外， 本学位论 文 的研究成果不包含任何他人创作的、 已公开发表或者没有公开发表的 作品的内 容。对本论文所涉及的 研究工作做出贡献的其他个人和集 体， 均己 在文中以明确方式标明。 本学位论文原创性声明的法律责 任 由本人承担。 学 位 论 文 储签 “ : 4 洋 问年s 月1 4 日 第一章 绪论 第一章绪论 1 . 1 图 论的 发展史 图论是一门应用十分广泛其内容非常丰富的数学分支， 是近年来较为活跃的 数学分支之一。它的起源很早， 瑞士数学家 e u l e r 在 1 7 3 6 年解决了当时颇为有 名的一个数学难题， 即哥尼斯城堡七桥问题， 从而使他成了图论和拓扑学的创始 人。 k i r c h h o ff 在1 8 4 7 年 运用图 论 解决了电 路理 论中 求 解联 立方程的 问题， 他引进 了“ 树 ” 的 概 念 ， 可 惜 的 是 他 的 发 展 超 越 了 时 代 而 长 期 未 被 重 视 。 1 8 5 7 年c a y le y 非常自然地在有机化学的领域里发现了一族重要的图， 称为树， 他应用树来解决 计 算饱和氢化 合物氏月 兹 十 : 的同 分异构 体的 数目 。 1 8 9 5 年， h a m i l t o n 发明了 一 个所谓环球旅行的游戏， 他用一个正十二面体的二十个顶点表示世界上的二十座 大城市， 提出的问题是要求游戏者找一条沿十二面体的棱通过每个顶点恰好一次 的闭路。 正是由于早期的图论与似乎没有很大意义数学游戏发生密切联系， 对图论知 识要求甚寡， 使得这一学科的发展颇为迟缓， 甚至一度处于停止状态。 直到1 9 3 6 年， 匈牙 利著名 图论 学家k o n i g 出 版图 论的 首部 专著 有限图 与 无限 图理 论 ， 总 结了图论二百年来的主要成果。 有限图与无限图理论一书的出版是图论史上 的一 个重要里 程碑。 此 后， 图 论进 入发展与 突破的 快车 道， 又经过半 个多世纪的 发展， 现己成长为数学科学的一个独立的重要学科， 它的分支很多， 例如图论， 算 法图论， 极值图论， 网络图论， 代数图论， 随机图论， 模糊图论， 超图论等等。 由于 现代科技尤其是大型计算机的迅猛发展， 使图论大有用武之地， 无论是数学， 物 理， 化学， 天文， 地理， 生物等基础科学， 还是信息， 交通， 战争， 经济乃至社会 科学的众多问题， 都可以应用图论方法予以解决。 图论又是计算机科学最重要的 基础之一。 2 0 世 纪科学史 上的 主要 事件之 一就是借 助于计 算机解决了 近代数学中 一个 最著名的 数学 难题一“ 四 色猜想” 。 这个问题 是1 8 5 2 由 一个叫g u t h r i e 的 伦敦学 生提出的: 在地图， 或地球仪上， 最多用四种颜色就可以把各国之版图染色好， 使 得任 一国 界线 两侧没 有 相同 颜 色。 1 8 7 9 年伦敦数 学会 会员k e m p l e 声称证明 了此 第一章 绪论 猜 想成立， 且 发表了 论文， 1 0 年后， h e a w o o d 指出了k e m p l e 证明中 存在 不可克 服的 漏洞， h e a w o o d 沿用k e m p l e 方法证明 了 五色定理。 k e m p l 。 的论证 方法极为 精 巧， 用a p p e l 的话 来说， 是“ 包含着 一个 世纪后 终于引出 正确证明 的绝 大部分 基 本思想” 。 1 9 7 6 年美国 伊利诺 大学的 两位教 授a p p e l 和h a k e n 在k o c h 的 协助 下， 依靠计算机的帮助， 证明了“ 四色猜想” 是正确的， 但是数学家们对于借助于 计算机进行证明并不满意， 仍希望最终给出数学证明。 图论最吸引人的特点是它蕴含着大量强有力的思想， 漂亮的图形和巧妙的论 证方法， 即使是非常困难的尚未解决的问题有时也易于表达， 现实生活中处处蕴 藏着图论的难题， 这也是图论的魅力所在。 芍 1 .2 自 补图和几 乎自 补图的研究状况 自补图的研究始于本世纪 6 0年代初，它几乎同时由三位著名的图论专家 r in g e l,s a c h a 和r e a d 1, 21 各自 独 立 的 进 行 了 研 究 ， 随 后 有 许 多 著 名 的 图 论 专 家 展 开 对自 补 图 的 研 究 ， 如r a o ,c la p h a m ,m a th o n ;l 等 . 自 补 图 是 有 趣 而 重 要 的 一 类 图 ， 业已 发现， 自 补图 在对角 线型的r a m s e y 数 方面的 研究4 , 5 1 ， 图 与它的 补图的 色 多 项 式 相 互 之 间 的 关 系 方 面 的 研 究6 1, s tr o n g p e rf e c t g ra p h 猜 想 以 及图 的 同 构 测试问题等的研究方面有其重要的应用。 到目前为止， 关于自 补图理论及其应用 的研 究已 经 取得了 丰富 的结 果， 并且 有很多 优美的结 果与独 特的方 法。 r i n g e l 和 s a c h s l , 11 分 别得出了自 补图 直 径的上 下界， r i c h a r d 和g ib b s lq 以 同构 映射 为基础 得 出 了 自 补 图 的 一 种 构 造 方 法 和 其 矩 阵 特 点 ， c la p h a m 和k le itm a n 91 证 明 了 自 补 图 的度 序列的充要 条件， c h a o 和wh i t e h e a d 10 l 研究了自 补图的 色数和色多 项式 等问题， r c .r e a d 2, 1 1 , 12 等研究了自 补图的 计数问 题， rm a t h o n 1a 和s . b . r a o l l l 讨论了强正则几乎自 补图的特点等等。 b .a ls p a c h 14 1 和d .f ro b e k l l 等 人 在 研 究 循 环自 补图 时 首 先 提 出 了 几 乎自 补 图 的概 念， 并提出 循环几乎自 补图的 阶数所 满足的必 要条件， 之后e . d o b s o n 和 m .g aj n a 1s1 于2 0 0 4 年 对 于 循 环 几 乎自 补 图 的 一 个 子 类 成 功 的 解 决了 这 一问 题 。 p o to d n ik 和g a j n a n 在 此 基 础 上 ， 对 几 乎自 补 图 进 一 步 研 究 ， 从 几 乎自 补 图 的 自 同构群角度分析， 得到了正则几乎自 补图的阶数所满足的充要条件， 构造了无限 第一章 绪论 几乎自 补图， 顶点可迁几乎自补图及几种特殊的几乎自补图。 1 .3 本文的结 构安排 本文共分5 章， 第一章介绍了图论的发展史，自补图和几乎自 补图的发展现 状及本文的创新点。 第二章给出了本文涉及到的基本概念， 包括图和同构的一些 相关理论以及自补图， 几乎自补图的基本定义。 第三、 四章是本文的重点. 第三章第一节详细论述了自 补图的一些性质， 包括自补图的顶点个数n必须 满足n 二0 , 1 ( m o d 4 ) . o 是g的自 补置换， 则。 2 t - 1 仍是g的自 补置换， 并且 最多有一个长度为1 的轮换， 而o的其他轮换的长度均可被4 整除; 第二节研究 了自 补图的 直径， 证明了自 补图必 是连通图， 且其 直径 满足2 d ia m ( g ) 3 ， 其 中 正 则自 补图的 直径是2 : 第三 节引用n o r d h a u s i m 的结 论: 对于 任意n 阶 简单图 g , 2 v ln x ( g ) + x (g ) n + 1 ， 得 出 自 补 图 色 数 满 足而 x ( g ) 呼 ， 另 一 方面， 若已 知自 补图 色数x ( g ) = k ， 则阶 数i v ( g ) l 2 ， 均存在这 样的自补图。 几乎自 补图是在自 补图的理论基础上产生的， 但研究和构造几乎自 补图要比 自 补图复杂. 在第三章证明思想的启迪下， 我们在第四章对应地研究了几乎自 补 图的性质、 直径和色数。 第一节得到了几乎自 补图的一些性质; 第二节证明了几 乎自 补 图 的 直 径 满 足2 d ia m ( 仍 4 ， 通 过 巧 妙 的 构 造 方 法 ， 验 证了 结 论 的 正 确性， 得出了对于每一个正整数n全3 ， 均存在直径为3 和 4的2 。阶几乎自 补 图， 对于每一个正整 数n 24 ， 均 存在直径为2 的2 。 阶 几乎自 补图， 同时 证明 了正 则几乎自 补图g直 径满足d i a m ( 叨 3 : 第三节 证明了加 阶 几乎自 补图 的 色 数x ( g ) 满 足 而 i x ( g ) n ， 同 时 ， 创 造了 两 类 几 乎自 补 图 分 别 满 足 x ( g ) = n , iv ( g ) l = 2 n 和x ( g ) = n , i v ( g ) l = 2 n 2 ， 进而 说明t 几乎自 补图 的色 数 上界是最 好的， 下界当而 为 整数 时也是 最好的 。 且当双仍=。 ， i v ( 叨 二2 n 2 时， g包含” 个顶点不 相交的 子图k 2 ” 一 ” k 2 - 第五章是对本文工作的一个总结， 并指出了今后的研究方向。 9 1 .4 本文 创新点 证 明了 n 阶自 补 图g 的 色 数x ( g)满 足而 x ( g ) 粤 : 第一章 绪论 证 明了 连 通 的 几 乎自 补 图g 的 直 径d ia m (叨满 足2 d ia m ( g ) 4 ; 证明了正 则几乎自 补图g必连通， 且直 径d i a m ( g ) 满足d i a m ( 切 3 : 对每一个正整数。全4 ， 构造出了直径为2的2 。 阶几乎自 补图: 对每一个正整数。之3 ， 构造出了直径为3 的2 。 阶几乎自 补图: 对每一个 正整数n 七 3 ， 构造出了 直径 为4 的2 。 阶几乎自 补图; 证明了 若 几乎自 补图的 色数x ( 叨 = k ， 则顶点 个数 v ( 叨1 2 k 2 ; 证明了2 。 阶 几乎自 补图的 色数x ( g ) 满足 j n- 1 _ x ( g ) n ; 对每一个 正整数n 全 2 ， 构造出了 色数 为n 的2 n 阶 几乎自 补图: 对每一个正整数n21 ， 构造出了色数为。的2 矿阶几乎自补图: 证明了x ( 匀 =。 且 v ( 叨i = 2 n 2 的 几 乎自 补 图必 是。 个顶点 不相交的 子图 k 2 ” 一。 k 2 的并。 第二章 基本概念 第二章 基本概念 5 2 .1 图 的基本概念 本节图的定 义均来自 于 1 9 . 定 义2 .1 图g 是 指 一 个 有 序 三 元 组( v (g ) , e ( g ) , o g ) ， 其中 v ( g ) = ( v i , v 2 , ， 是非空的 顶点集 ， v i ( 1 i n ) 称为g的 顶点， n = i v ( g ) 为g的 顶点个数， 也 叫g 的 阶 数 ; e ( g ) = l e i , e 2 , . . . ， 是 不 与v (g ) 相 交 的 边 集 ， e ; ( 1 i 6 ) 称 为g 的 边 ， = ie ( g ) ! 为g的 边 数 ; 如是 关 联 函 数 ， 它 使g 的 每 条 边 时 应 于 g的 无 序 顶 点 对( 不 必 相 异天 若。 是 一 条 边 ， 而。 和” 是 使 得+p o ( e ) = ，的 顶 点， 则称e 是连接移和”的，同时把边 e 和点“( 或形 ) 称为互相关联的， 顶点“ 和。 称 为。 的 两 个 端 点 ， 称 点二 和 。 是 相 邻 的 ， 记e = (u , v ) . 具 有 同 一 端 点 的 边 称为环， 端点不同的边则称为连杆。 无环 且不存 在两 个顶 点连 接两 条 杆的图 称为 简单 图. 一个顶点集 和 边集都 有 限的图 称为 有限图. 只 有一个 顶点的图 称为 平凡图 ， 其 他所有的图 都称 为非 平凡 图。 本文 研究的图 仅限于 有限简 单图 . 定 义2 .2 设g 是简 单 图 ， 若v ( g ) 卜。 ， 且图 中 任意 两 顶 点 均 相 部 ， 则 称g 为n 阶 完 全 图 ， 记 做k n ; 若v ( g ) = x u y , e ( g ) = (二 ， v ) 二 x , y e y 其中 ix i = m , iy i = n ， 则 称g 为 完 全 二 部 图 ， 记 做k . ,n . 定义2 3设 g 是一个简 单图 ， g的 补图 记 做g ， 满 足 v ( g )= v ( 叨 e ( g )= ( 二 ， 。 ) 。 ， 。 e v ( g ) 且( 二 ， 。 ) 样 e ( g ) 定 义2 a称 图h是g的 子 图 ， 如 果v ( h ) 9 v ( g ) , e (h ) c e ( g ) ， 并 且o r 是 如在e ( h ) 上 的 限 制 . 假 设v 是v 的 一 个 非 空 子 集 ， 以v 为 顶 点 集 ， 以 两 端 点均 在v 中 的边的 全体为 边集所 组成 的子图称为g的由v 导出 的 子图 ， 记做 g v j . g 叫 称 为g 的 导 出 子 图 . h为 边 集e 的 非 空 子 集 ， g - e 表 示 从g中 删除e 中的边所得到的子图. 第二章 基本概念 定义2 . 5图g 1 和汤 的 并， 记做g=g l u 场， 其中 v ( g )= 。 i 、 v (g j ) 或。 e v ( g 2 ) ) e ( 叨 = ( 。 ， 。 ) ( 。 ， 。 ) e e ( g 1 ) 或恤 ， 。 ) e e ( 仇) 定 义2 .6 g 的 顶 点。 的 度心(哟是 指g 中 与。 关 联 的 边 的 数目 ， 每 个 环 算 作 两 条 边， 用8 和 分别表示g的顶点的最小度和最大度。 定 理 2 .1e 心 (。 ) = 2 1e (g ) i. v e v ( g ) 证明 . 每条边有两 个端点 ， 所有顶 点度数 相加时 每条边 计算了 两次， 所以有 艺 d g ( v ) = 2 1e ( g ) i ( 2 . 1 ) v e v ( g ) 口 定义2 . 7设 g是简单图， 如果图所有顶点的度数相同为k ( k 为正整数i则称g 为 k 一 正则图。 推 论2 .2 。 阶; 一 正 则 图g 的 边 数 为侧必 =盖 k n . 证明.由定理 2 . 1 : 2 1e (g ) i 一艺 d g (v ) =e “ = “ 。 v e v ( g) v e v ( 仍 所 以ie ( g ) i =蠢 k n .口 定义2 . 8 g的一条途 径( 或通道) 指一个 有限非 空 序列w = v o e l v l e 2 v 2 . - e k v k , 它的项交替地为 顶点和 边， 使得对1 i k . 的 端点 是v i - : 和v i ， 称二是从 v u 到v a : 的 一条途径 ， to和v k 分别 称为叨的 起点和终 点， 而v i , v 2 , * , v k - 1 称为 它的内 部顶点， 整数k 称为二的长. 若 途径 w得边e 1 , e 2 , . . , 8 k 互不 相同 ，则w称为 迹， 这时w的长 恰好为 c ( 叻， 又 若途径w的顶 点v o , v i , . . . , v k 也互不 相同 ， 则。 称为路. 对于g中 的两个 顶点移 和公 ， 当 存在 连接二 和” 的 路时， 这些路中 最 短的 路 的 长度称为。 和。 之间 的距离 ， 记做d g ( u , v ) 若 g中任意两个顶点间都有路，则称 g是连通的，否则称 g是不连通的. 不 连通图的 每个连通 子图称为 连通分 支. g的直径是指 g的两个顶点之间的最大距离， 记做d i e m( 引， d i a m ( g ) =m a x d ( 二 ， 。 ) 。 ， 。 v ( 仍 第二章 基本概念 如果g是不连通的 ， 定义a i am( 伪= 0 0 . 定 义2 .， 设m是侧闭的 一 个 子 集 ， 它 的 元 素 是g的 连 杆 ， 并 且 这 些 连 杆中 的 任意两 个在g中 均不 相邻 ， 则 称m为g的匹配 ， m中 一 条边的两 个 顶点称为 在 m 下是配对的， 若时集m 的某条边与顶点 。 关联， 则称m 饱和顶点。 ， 并且称 v 是 m 饱和的，否则称。 是 m非饱和的， 若g的每个顶点均为 m饱和的，则 称m为g的完 美匹配 ， 若g没 有另 外的匹 配m ， 使 得 m 卜 i mi l 则称m 为 g的最大匹配。 定 义2 . 1 0 设s 是 顶 点 集v ( g ) 的 一 个 子 集 ， 若s 中 任意 两 个 顶 点 在g中 均 不 相 邻 ， 则 称s 为g 的 一 个 独 立 集 . 设s 是 顶 点 集v (g ) 的 一 个 子 集 ， 若s 中 任 意 两 个顶点在 g中均相部， 则称s为g的一个团. 定 义2 . 1 1 g的 一个k 顶 点着色 是 指k 种颜色1 , 2 , . , , , k 对于g的各个 顶点的一 个 分配 ; 如果 任意两 个 相部的 顶点都 分 配到不同 的颜色 ， 称着色 是正常的 ; 当g 有 一个 正常k 顶点着色 时， 称g是 k 顶 点可着色 的. g 的 色 数 x ( 叨是 指 使g 为k 可 着 色 的 数k 的 最 小 值 ; 若x (伪 = k ， 则 称g 是k色的. 定 义2 .1 2 字 典 排 序 12 是 指 : x 是 一 个 偏 序集 ， x 直 积 上 的 两 个 元 素。 = ( a , , a 2 , ，) ， 口 =(bi , b2 , . .,小 其中 a ; 击e x , i = 1 , 2 , ， 7 = 1 , 2 , . . . , 则。 月 ， 是 指对某个 k a k 6 k ， 且时 所 有 1 而 保留1 , 2 , . . . , n 中的 其余元 素不 动， 此时 可以 把a 记 做a = ( 2 1 , 匀 ， ， 幼， 且 称a是一个 : 阶循环. 两 个 循环a = ( i t , i 2 , . . . , 4 ) , 0 =伍j 2 , . . . ， 头 ) 叫 做不 相交的 ， 是指 对任何 k , 1 均 有k o j t (1 k r , 1 1 s ) . 任 一 里 换。 都 能 表 示 成 两 两 不 相 交 的 循 环的积， 此时每个循环也称作轮换 ( 或圈) . 定 义2 .1 4 四图0 1 , 0 2 被 称为 是 同 构的 ， 记 做g l = g 2 ， 如 果 存 在 一 个 从v (g i ) 到v (g 2 ) 之 间 保 持 相 邻 性 的1 一 1 映 射v ， 即 在v ( g 1 ) 到v ( g 2 ) 之 间 存 在 一 个 1 一 1 映 射o ， 使得 对于v u , v v ( g l ) , ( u , v ) e e ( g i )当 且仅当( 。 ( 二 ) ， o ( v ) ) e e ( 仇) ( 2 . 2 ) 我 们 把从v ( g 1) 到v (g 2 ) 之间 保 持 相 邻 性 的1 一 1 映 射o 称 作图g : 和g 2 之间 的同构映射. 定义2 . 1 5 1 6 1 如果图g和它的补田g 0 同 构， 则称g为自 补图 . o 是从g到g 0 之间 的一个同 构映 射， a i, 称。 为图g的 一个自 补置 换. 若o 可分 解成k 个轮换之积，即a=0 1 0 2 . . . o k , m对于 每个o i ( 1 三 哟 ， g o i 】 表 示 由 o 所 包 含 的g的 顶 点 导出 的 子 图 . 定义2 . 1 6 fi n g是简 单图， 如果在g的补图g 0 中 存在一 个完美匹 配m ，满 足 g=g 0 一m ， 则 称g为几乎自 补图. g 一m称 为g的几 乎补图 ， 其中 v ( g - 一 m)= v ( g - ) =v ( g ) e ( g - 一 m)= ( 二 ， 。 ) 、 ， 。 v ( 仍， ( 。 ， 。 ) 0 e ( 仍， ( 。 ， 。 ) v m) 图g 的 基 于 完 美 匹 配m的 几 乎 补 图g 0 一 m常 被 记 做嗡 . 。 是 从g 到g i 之 间的一个同构映封， 则称。为图g的一个基于m 的几乎自补兰换. 第三章 自补图 第三章 自补图 笋 . 1 自 补图的 基本性质 定 理3 . 1 问设图g是。 阶自 补图 ， 则。 二0 , 1 ( m o d 4 ) . 证明 . 因 为g 是自 补 图 ， g =g 0 ， 且v ( g ) i = n , . 显 然 有e (g ) i = ie (g ) i, 又由e ( 仍u e ( g ) 二e ( 瓜) ， e ( g ) n e ( g 0 ) =功 可 得: ie (g )一 2 ( 2) 一 14n (一 ) ( 3 . 1 ) 而e ( g ) i 必 为整数 ， 因 此。 二0 , 1 ( m o d 4 ) .口 定 理3 .216 1 设g 是一个自 补图， 。 是g的 一个自 补 1换， 则 有 : ( 1 ) o 2l - 仍是g的自 补!换， t 为 正整 数; (:) 。 可 分 解 成k 个 轮 换 之 积 ， 即 。 = o 1o 2 . . . o k ， 则 对于 每 个o ; (1 i v iz , . . . , v irrm 上的 一 个1 一 1 映 第三章 自补图 射; 另一方面 ， 对于。 , v e v i v i . , . . . ， % ， ( 。 ， ， ) e e ( g o i ) q ( 二 ， 。 ) e ( g ) a ( o ( 二 ) , - ( v ) ) v e ( g ) q (q i (u ) , q i( v ) ) e ( g ) f ( q i ( u ) , 0 i ( v ) ) o e ( g o i ) q o i (u , v ) e ( g 0 : ) 故g a i = g o i 0 , g q i 是自 补图 且o ; 是它的 一 个自 补置 换. (3 ) 假 设。 有 两 个 长 度 为1 的 轮 换 ， q 1 = (u ) 和a 2 = (v ) , ( 。 ， 。 ) e e ( 伪4 * 。 ( 。 ， 。 ) =位 ( 。 ) ， 。 ( 。 ) ) e e ( g ) 而， ( 二 ， 。 ) 二( o l ( u ) , 0 2 ( v ) ) 二( 二 ， 。 ) ， 矛 质。 这 便证明7。 至多 有一 个长 度为 1的轮换。 设。 =0 1 01 2 ol k ， 下面 证明 若叫 笋 1 ， 则叫( 1 _ 3 , a ll 至 少 存 在 两 顶 点。 ， 。 ， 满 足d g (u , 讨=3 ， 则 在g 0 中 ， ( 。 ， 。 ) e e (g 0 ) ， 且 对于v w e v ( g ) 。 ， 。 ， 均 有( u , w ) e e ( g 0 ) 或 (v , w ) e e ( g ) ， 因 为 如 果 存 在 一 顶 点w o e v (g ) 二 ， 。 ， 满 足( u , w o ) 必 e ( g 0) 且(。 ， 二 ) 磷 e ( g $ 则(u , w o ) e e ( g ) 且扣 ， 二 。 ) e e (g ) 与心(。 ， 。 ) = 3 矛 质 . 因 此 d i a m ( g ) _ 4 时 ， 若 d ia m ( g ) _ 3 ， 由 上述 结 论， 可 得d i a m ( g ) 3 ， 矛 盾. 故d i a m ( g ) = 2 . 0 引理3 a 自 补图必是连通图. 证明 .设自 补图g不连 通， 不失 一 般性， 设g=g , u 仇， 认( i = 1 , 2 ) 为g的 两 个 连通分支 ， a ll v u e v ( g , ) , v e v ( g 2 ) ， 均 有恤 ， 。 ) e ( g 0 ) ， 即g 连 通， 与 第三章 自 补图 g =g 0 矛 质. 故自 补图 必 是连通图 . 定 理3 . 5 , 1 若g 是自 补图， 则2 d i a m ( 动 3 . 证 明 . 设。 是自 补 图g 的自 补 里 换 ， 对 任 意 点。 e v ( g ) ， 我 们 有d (二 ， a (u ) ) 2 . 因 为 若( 。 ， 。 ( 。 ) ) e e ( g ) , a 1 证毕 ; 否则( 二 ， a ( u ) ) 样 e ( 匀， (。 一 (。 ) ， 。 ) e e (匀 且 ( 。 (。 ) ， 尹 ( 。 ) ) e (叨 若( 二 ， a 2 ( u ) ) e e ( 仍， 则由( u , a 2 ( u ) ) e e ( g ) , ( a 2 ( u ) , a ( u ) ) e e ( g ) 得d ( u , a ( u ) ) = 2 , 否 则(u , a 2 ( - ) ) 磷 e (g ) ， 则 有(。 一 (、 ) ， 。 ( 。 ) ) e ( 必， 即( 二 ，v 1 ( u ) ) e e ( 匀 和(a - ( u ) , a (u ) ) e e ( g ) 得d ( u ,a ( u ) ) = 2 . 总之， d ( 二 ， a ( u ) ) 2 对自 补 图g中 任蠢顶点 均成立 . 对d u , v v ( g ) ， 若( 、 ， 。 ( 。 ) ) e e ( 切， 则 d ( u , v ) d ( 二 ， 。 ( 。 ) ) +d ( a ( v ) , v ) 3 否则( 。 ， ， ( 。 ) ) 举 e ( 仍， a 1 ( o 1 ( u ) , v ) e e ( 切， 则 d ( u , v ) d ( 二 ， 。 一 ( 二 ) ) + d ( 。 一 ， ( 。 ) ， 。 ) 3 综 上 ， d ( u , 帅 3 . 由 顶 点、 ， 的 选 取 任 意 性 得 d ia m ( 必_ 2 . 综上2 d i a m ( 仍 3 .口 定 理3 . 6 同若g是一个 正则自 补图 ， 则d i a m ( 仍 = 2 . 证明 .g是k 一正 则自 补 图 ， v (g ) = n ， 则 任 意 顶 点。 在g中 的 度 与 在g e 中 度 相 同 ， 且心(动+ 心 (动=。 一 1 ， 即。 一 1 二2 k ， 因 此。 为 奇 数， 又 因 。二0 , 1 ( m o d 4 ) ， 故。=4 k +1 ( k 为 正整 数)，且g为2 k 正则图 . 对于任 意 顶 点。 ， 。 e v ( 匀， 设(。 ， 。 ) 样 e ( g ) ， 因。 ， 。 分 别 与v ( g ) u , v 中2 k 个 点 相 邻 ， 而】v ( g ) u , 好 =4 k 一 1 ， 所 以 必 存 在 一 点、e v (g ) u , 好满 足 ( 。 ， 。 ) e ( 0， ( 。 ， 、 ) e ( g ) ， 即d ( 二 ， 。 ) 2 . 由、 ， 。 的选 取任意性 得d i a m ( g ) 2 ， 又 根据定 理3 . 5 得 d ia m ( g ) = 2 .口 互 3 . 3 定 理3 . 7 u e l 图g是。 阶简单图 ， x ( g ) + x ( g ) 。 +1 . 自 补图的色数 则g的g 0 的 补图的色 数满 足不等式 : 2 而 兰 第三章 自 补图 证明 . 设x ( g ) =k 1 , x ( g o ) =k 2 ， 对g的 任愈k i -顶 点正常 着色 ， 设有、个 顶 点 着 第 种 颜色( 1 _ i k l ) ， 这、个 顶 点 在g中 是 独 立 集 ， 故 在宁中 为 团 ， 所 以n , k 2 ( 1 _ 4 k j k 2 仇 因 此 k 1 +肠2 f 另一 方面， 对。 作归 纳 证明x ( 仍 + x ( g) _ 1 ) 阶 简 单 图 结 论 成 立 ， 那么 当 v (仍! = n + l 时 ， 任 取 一 顶 点v o e v ( g ) ， 记g o = g v o ， 设x ( g o ) = k , x (g o ) = k 2 , a 1 i v ( g o ) 卜 。 ， k 1 + k 2 。 +1 . 设v u 与g o 中t 个 点 相 邻 ， 则 与g o 中。 一 t 个 点 相邻(0 t n ) , 人:v ( g o ) - + 1 , 2 ， 一 ， k 1 为g o 的 一 种k , 一 顶 点 正 常 着 色 ， 儿: v ( g o ) - + 1 ， 2 ， . . - , k 2 为喘的 一 种棍 一 顶 点 正 常 着 色 . 若 f i ( u 川二 ，、 ) e e ( g ) ) i k 1 , 则 在g中 可 用 1 ,2 , . . . ， 姗中 一 种 颜色 对v o 着色 形成g的 一 个k 1 一顶 点正常着色 ， 在宁 中 ， 令八 ( v o ) = 肠+1 可形成 g 的 一 个( k 2 十 1 ) 一 顶 点 正 常 着色 ， 因 此 x ( g ) + x ( g ) k 1 + k 2 +1 ( 。 +1 ) + 1 若 f 2 ( u ) ( u , v o ) e e ( g ) i k 2 ， 可类 似地 证明结 论成 立; 否 则 ; vi m i ( 二 ， 、 ) 。 e ( g ) i “， k 2 i f 2 (u ) i (， ， 、 ) 。 e ( g 0 ) n 一 亡 ， 则k l +k 2 n , x ( g ) +x ( g 0 ) ( k i +1 ) +( k 2 +1 ) 二k 1 + k 1 +2 ( ” + 1 ) + 1 定理成立。口 推 论3 .8自 补 田g 的色 数x ( g ) 满 足而 x (g ) k + 1 与g=g 矛 盾. 因 此v ( g ) i k 2 .口 第三章 自 补图 定 理3 .1 0 (i 61 如 果 存 在 一 个自 补 图 g 满 足x (g ) = k 且v (g ) 卜k 2 ， 则g包 含k 个顶点不文的完全子图k k . 证 明 . 记v (g ) = x l l , x 12 , , x lk , x 2 1 , x 22 , ， x 2 k ， 一， x k l ， 二 。 ， , x k k f ， 对 于 g的 任愈k 一顶点 正常着色 ， 由 定 理3 .9 最多 有k 个 顶点着 相同色 ， 又 v ( g ) l = 护 ， 所 以 恰 好 每k 个 顶 点 着 一 种 色 ， 不 仿 设民= x li ， 二 ， ， 一 ， 二 时 中 顶 点 着 颜色 i ( 1 三i _2 ， 均 存 在一 个自 补图g ， 其色 数x ( g ) 二k 且 v ( g ) i = k 2 . 证 明 . 通 过 构 造g 及g 0 证 明 结 论 成 立 . 记v ( g ) = x ii 1 i , j 封 ， k k ， 表 示由 顶 点 集v (g ) 生 成 的 完 全 图 ， 把e ( k , . ) 平 均 分 配 给g 及g ， 即 e ( k k s ) =e ( g ) u e ( g )且 e ( g ) n e ( g 0 ) = 0 e ( k k , ) 的 分拆 按以 下两 种情况 分别 定义 情况 1 . 如果k 是偶数， 定义映 封b : v( 自 ，v ( 自 如下: b 一n (、二 + 1 ， 二 。+ 1 ,t+ 1 : 。，+ ， ) x 止 o d d 1 1( 、2 j 二 + 1j x j ,i+ 1 ) o d d ( 3 .3 ) 1 二 5k - 1 设 形 如( x tt x t + l t x t + l ,t+ : 二 。,t+ l ) ( ( 1 t k 一 1 且t 为 奇 数) 的 四 阶 轮 换为 a 类 型 轮 换 ， 形 如(x ij x j i x + l j x i ,i+ l ) ( 1 k 一 3 , i + 2 j k 早 是 奇 数) 的 四 阶 轮 换 为 b 类 型 轮 换 . 因 为 k 是 偶 数 ， 所 以 从1 到。 一 ; 共 有套 个 奇 数 ， z _ 。 k ，j ，_ _. _ ._ 。 _._ ， 二. ._ 、。 _ 。. ， . 即 有答 个a 类 型 的 四 阶 轮 换 ， 对 于 每 个 奇 数 ( 1 i k - 3 ) ， 在 十 2 到k 之间 ”2 一 - 一” 一一”一、 一一 有k 一( i + 2 ) +