（运筹学与控制论专业论文）局部连通图中的同胚不可约支撑树.pdf

一 j d i s s e r t a t i o nf o r m a s t e rd e g r e e 2 0 1 1 u n i v c o d e 1 0 2 6 9 s t u d e n ti d 5 1 0 8 0 6 0 1 0 7 7 h o m e o m o r p h i c a l l yi r r e d u c i b l esp a n n i n g 皿 e e si n l o c a u yc o n n e c t e dg r a p h s d e p 盯t m e n t d e p a 砒m e n to fm a t h e m a t i c s m a j o r o p e r a t i o n a lr e s e a r c ha n dc y b e r n e t i c s d i r e c t i o n t o p 0 1 0 9 i c a lg r a p ht h e o 巧 s u p e i s o r c a n d i d a t e r e nh a n s h a ns o n 9 1 i n g 华东师范大学学位论文原创性声明 叶 鸽 帮重声明 本人所呈交的学位论文 厨泖巫叠阁悯同删粤鳝僻东师范大学攻 读硒生 博士 请勾选 学位期间 在导师的指导下进行的研究工作及取得的研究成果 除 文中已经注明引用的内容外 本论文不包含其他个人已经发表或撰写过的研究成果 对本文 的研究做出重要贡献的个人和集体 均已在文中作了明确说明并表示谢意 作者签名 监丝日期 孙1 年5 月们日 华东师范大学学位论文著作权使用声明 范大学根据相关规定保留和使用此学位论文 并向主管部门和相关机构如国家图书馆 中 信所和 知网 送交学位论文的印刷版和电子版 允许学位论文进入华东师范大学图书馆 及数据库被查阅 借阅 同意学校将学位论文加入全国博士 硕士学位论文共建单位数据 库进行检索 将学位论文的标题摘要汇编出版 采用影印 缩印或其他方式合理复制学位论 文 本学位论文属于 请勾选 1 经过华东师范大学相关部门审查核定的 内部 或 涉密 学位论文 于年 月日解密 解密后适用上述授权 u2 不保密 适用上述授权 学位论文作者签名 够绎放妊导师签名 嗍幽盘豳堕吼丝 汐f f 涉密 学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位论文 需附获批的 华 东师范大学研究生申请学位论文 涉密 审批表 方为有效 未经上述部门审定的学位论文均为公开学位论文 此声明 栏不填写的 默认为公开学位论文 均适用上述授权 镡松龄硕士学位论文答辩委员会成员名单 姓名职称单位备注 吕长虹教授华东师范大学主席 杜若霞副教授华东师范大学 郭军伟副教授华东师范大学 摘要 如果一个连通图的支撑树不含有2 度点 则这棵树被称为是同胚不可约支撑 树 h o m e o m o r p h i c a l l yi r r e d u c i b l es p a n n i n gt r e e 简记为h i s t a h i u 猜想除蚝外的 任何一个平面三角剖分都含有一h i s t j m 删t c h 将此猜想推广到平面近三角剖分的 情形 a 1 b e r t s o n b e r m a n h u t c h i n s o n 和t h o m 嬲s e n 证明了推广后的猜想 并且猜测任何 一个曲面三角剖分也含有一h i s t 本文证明任何一个顶点数至少是4 的局部连通图都含有 h i s t 作为一个推论 便得到任何一个曲面三角剖分也含有一h i s t 的论断 关键词 局部连通图 边收缩 2 树 边不交支撑树 三角剖分 同胚不可约支撑树 a b s t r a c t as p a n n i n gt r e ew i t h o u tv e r t i c 鹤o fd e g r e e2i 8c a u e dah o m e o m o r p h i c a u yi r r e d u c i b l e s p a i l i l i n gt r e e h i s t a h i l lc o n j e c t u r e dt h a te v e 盯t r i 趿g u l a t i o no ft h ep l a n e0 t h e rt h 眦娲 c o n t a i l 培ah i s t j m a l k e v i t c he x t e n d e dt h i 8c o n j e c t u r et oan e a 卜t r i a n g u l a t i o no ft h ep l a i l e a2 c o n n e c t e dp l a n eg r a p hw i t ha ub u ta tm 0 8 to n e f 砬e sa r et r i a n g l e 8 a l b e r t s o n b e r m a n h u t c h i n s o n a n dt h o m a 豁e nc o n 丑m e dt h ec o n j e c t u r e m o r e o v e r t h e y 蹈k e dw h e t h e re t e 阿 拥口哪 地坑d n 可口5 t 正哟c ec d n t 口i 船口脚s zi nt h i 8p 印e r w es h o wt h a te v e 巧c o n n e c t e d 趿dl o c a u yc o n n e c t e dg r a p hw i t hm o r et h a j l3v e r t i c e sc o n t a l i 璐ah i s t c o 璐e q u e n t l y e v e 可 t r i a n g u l a t i o n0 fas u r ec o n t a i 璐ah i s t k e yw o r d s 1 0 c a u yc o n n e c t e dg r 印h e d g ec o n t r a u c t i o n 2 t r e e e d g ed 蠲o i n t8 p a n n i n g t r e 鹄 t r i a l i 州a t i o n h o m e o m o r p h i c a l l yi r r e d u c i b l es p a r l n i n gt r e 鹤 中文摘要 英文摘要 目录 第一章 引言及预备知识 1 1 1 引言 1 1 2 网的基本概念 2 1 3 树 5 1 3 三角剖分图 5 第二章 局部连通图简介 6 2 1 局部连通图的定义 6 2 2 局部连通图的一些性质 7 2 3 关于局部连通图的两个猜想 8 2 4 缸树和弦图 8 第三章边不交的支撑树 1 0 3 1 定义及应用 1 0 3 2 局部连通图中的边不交支撑树 1 1 第四章 局部连通图中的同胚不可约支撑树 1 4 4 1 同胚不可约支撑树 1 2 4 2 弱2 树 1 5 4 3 局部连通图中的m s t 1 7 参考文献 1 8 硕士期问完成的论文 2 0 后记 2 1 华东师范大学 局部连通图中的同胚不可约支撑树 第一章引言及预备知识 1 1 引言 如果一个连通图的支撑树不含有2 度点 则这棵树被称为是同胚不可约支撑 树 h o m e o m o r p h i c a u yi r r e d u c i b l e8 p a i l i l i n gt r e e 简记为h i s t 任意给定南 0 总可 以构造出一个图 使其最小度6 如 但是不含有h i s t 比如 在 a b h t 9 0 中 取r 个j 0 拷贝 对每 个坼拷贝中的r 个点 每一个都与一个一度点连接 然后 添加另外的r 个独 立点 每一个都与已构造图中的r 2 个悬挂点连接 这个图的最小度是r 但是不含有h i s t 然而 a l b e r t s o n b e r m a n h u t c h i 璐o n 和t h o m a u s s e n 证明含有n 个点的连通图g 如果最 小度6 g 4 钜元 则g 含有h i s t 应用相同的技巧 可以证明 对每一个正整数d l 和 任给的常数c o 如果g 的最小度至少为c 何 则g 含有一支撑树不含有2 3 d 度 点 他们同样证明说如果g 不是蚝并且g 的任意两个点之间都有一条长为2 的路 则g 含有h i s t a l b e r t s o n b e r m a n h u t c h i 璐o n 和t h o m a s s e n 同样指出 任给一个图g 决定 g 是否含有h i s t 是n p 困难的 紧接着 他们问 决定一个最大度为3 的图是否含有h i s t 是不是n p 网难的 这个问题已经被人解决 答案是肯定的 但是截止目前 结论尚未公开 发表 将一个图是否含有h i s t 的问题限制在平面图上来考虑 a h i n h i l 7 4 猜想说除飓 外的任何一个平面三角剖分都含有一h i s t j m a l k e v i t c h m a l 7 9 将此猜想推广到平面 近三角剖分 除至多一个面外的所有面都是三角形的平面图 的情形 a l b e i r t s o n b e r m 龃 h u t c h i n s o n 和t h o m a s s e n a b h t 9 0 1 证明了推广后的猜想 并且猜测任何一个曲面三角剖 分也含有一h i s t d a v i d o w h u t c h i n s o n 和h u n e k e d h h 9 5 1 证明每一个环面上的三角剖 分图都含有h i s t 本文证明任何一个顶点数至少是4 的局部连通图都含有h i s t 作为一 个推论 便得到任何一个曲面三角剖分也含有一h i s t 的论断 华东师范大学局部连通图中的同胚不可约支撑树 1 2 1 图的定义 1 2 图的基本概念 一个图g 实际上就是一有序对 v g e g 这个有序对含有三个因素 其一 顶点集 y g 其二 与顶点集不交的边集e g 其三 关联函数妒g 它将g 的每一条边与g 的顶 点集的二元无序对 有可能无序对中的两个元素相同 相对应 如果e 是g 的 条边 u 是g 的两个顶点 并且有惦 e u 我们则说 e 和 t 分别关联 同时 u t 也和e 关 联 u 与 相互邻接 这时 t l 移被称为e 的端点 设 也是g 的一条边 如果让也与 关联 我们则说e 和 邻接 图g 所含顶点的个数 也就是y g 所含元素的个数 通常用l y g i 来表示 图g 所含边的条数 也就是e g 所含元素的个数 通常用i e g i 来表示 在如上所定义的图中 如果我们要求g 的每一条边与g 的顶点集的不同顶点构成的二 元无序对相对应 则相应的图称为简单图 在后文中 如无特别指出 所有的图都是简单图 假设g 是一个简单图 并且假设 是g 的一个顶点 我们将g 中所有与u 相邻接的顶 点集合称为u 的邻域 记为 g u 如果不会引起混淆 则简记为 u 的闭邻域 记为 m u u 与顶点u 相邻接的点的个数 也即是与点u 相关联的边的条数 也即是 所含元素的个数 被称为 的度数 记为站 u 或者d u 图g 中所有顶点的度数中 最小的被称为g 的最小度 记为j g 相应地 最大度记为 g 假设g 是一个简单图 并且假设咖e l u l e 2 u 2 e 3 u 3 饥一l e t 毗是g 中一个点边序列 则这 个序列称为g 的一条长为t 的链 咖和u t 称为链的始点和端点 如果这个链的所有点和边 都互不相同 则相应的链称为g 的一条路 路上的除端点之外的点称为是路的内点 我们 用r 来表示含有n 个点的路 或者长为礼一1 的路 一般地 设p 是一条路 z 可是路上的两个点 则z p 表示以z 秒为端点 以p 上位于 z 可之间的点为内点的一条路 如果一条路的始点和端点相同 则这条路是一个圈 我们用g 来表示长为钆的圈 设g 是一个含有n 个顶点的简单图 如果g 的任何两个点之间都有一条边 则g 是一 个完全图 记为 1 2 2 子图 设g 是一个图 顶点集是y g 边集是e g 我们说图h 是图g 的一个子图 如果 y 日 y g 并且e 日 e g 2 华东师范大学 局部连通图中的同胚不可约支撑树 给定g 的子图h 如果我们有y 日 y g 我们则说日是g 的支撑子图 设g 是一个恰好含有礼个顶点的图 如果g 含有一个支撑圈 或者说长为n 的圈作为 子图 我们则说这个圈是g 的哈密尔顿圈 此时 也说g 是哈密尔顿的 1 2 3 导出子图 设g 是一个图 顶点集是y g 边集是e g 假设s y g 现在定义g 的一个子 图日如下 iy h s le 日 u u i u s 并且u u e g 此时 我们称日是g 的点导出子图 或者是由s 导出的子图 记为g 翻 如果g 鄙是一个 完全图 我们则说s 是一个团 1 2 4 图同构 设g 和日是两个图 如果有y g y 日 e g e 日 并且妒g 妒日 则说g 与 日相等 记为g 日 通常而言 我们说两个图g 和日同构 记为g 望日 如果存在双射口 y g 一 y 日 和 e g e 日 满足惦 e t i u 当且仅当妒日 e 口 u p u 此时 这一对双射 口 咖被称为g 和h 间的同构映射 1 2 5 图的几个运算 给定图g 设s 是y g 的一个子集 那么g s 则表示g 的一个子图 通过删除s 中的顶点和所有与s 中的顶点关联的边而得到 特别地 如果s z 则g s 简记为 g z 给定图g 设t 是e g 的一个子集 那么g t 则表示g 的一个子图 与g 具有相同 的顶点集 而边集则通过从e g 中删除丁中的边而得到 特别地 如果t e 则g t 简记为g e 给定图g 及g 的一条边e z 我们等同顶点z 和可 将这个新点记为叫 然后构造一 个新图g 7 如下 jy g 7 y g z 暑 u 叫 le g 7 t u l t u e g t u 隹 z 暑 u z 叫i z z e g 或者矽名 e g 3 华东师范大学局部连通图中的同胚不可约支撑树 值得注意的是 即使在g 中我们有z 名和妒都是边 在新图中我们只有叫z 这一条边 因此 g 是一个简单图 我们称如上所描述的图运算为边收缩运算 一般地 我们用g e 来表示 g 7 给定一个图g 如果我们将g 的某些边用路来代替 则所得的图称为是原图的一个细 分 比如说 长为8 的圈是长为4 的圈的 个细分 给定一个图g 如果图 可以通过收缩g 中的一些边和删除g 中的一些边而得到 则 日称为是g 的一个子式 给定图g 和日 则gn 日 y g ny 日 e g ne 类似地 gu 日 y g u y 日 e g ue 日 1 2 6 图的连通性 假设g 是一个非平凡图 也即是说g 含有至少两个顶点 我们说g 是连通的 如果g 的任何两个顶点之间都有一条路相连接 设p 和q 是g 的两条路 我们说p 和q 内部不交 如果p 和q 具有不同的内点 如果g 的任何两个顶点间都有至少两条内部不交的路 则g 被称为是2 连通的 相应 地 任意给定正整数后 可以定义 连通 设g 是一个图 任给g 的两个顶点 根据这两个点之间是否有路连接可以将g 的顶点 分类 也就是说 如果z 之间有路连接 则将z y 放在同一个类中 每一个顶点类的导出 子图称为g 的一个连通分支 设g 是一个图 o 是g 的一个顶点 e 是g 的一条边 如果g z 的连通分支的个数比 g 的多 则称z 为g 的一个割点 相应地 如果g e 的连通分支的个数比g 的多 则称e 为g 的一条割边 定理1 设g 是一个图 e 是g 的一条边 如果e 在一个圈上 则e 不是g 的割边 证明 反设e z 是g 的 条割边 则在g e 中有两个连通分支g 1 g 2 使得在g 中g 1 g 2 在同一个分支里并且g 1 中的任何一个点与g 2 中的任何一个点之间的路都经过 e 特别地 和钞之间的所有路都必须经过e 因此 e 不在任何圈上 这是一个矛盾 从而 e 不是g 的割边 口 4 华东师范大学局部连通图中的同胚不可约支撑树 1 3 树 一个无圈的连通图 被称为树 关于树 我们有如下的定理 定理2 设t 是一棵树并且t 恰好含有礼个顶点 则丁的边数为n 一1 为了证明定理2 我们需要下面的引理 引理3 设g 是一个图 如果6 g 2 则g 含有围 证明 取g 中的一条最长路p 并且假设z 是尸的一个端点 因为j g 2 z 肯定会 和一个不同于它在j p 上的邻点的顶点邻接 设那个点为y 但是 p 是g 中的最长路 所以 可一定在尸上 这样 z yuz 尸y 形成了一个圈 口 现在我们来证明定理2 证明 我们对丁的顶点数作归纳 当顶点数是2 时 结论显然成立 根据引理3 丁含 有一度点 比方说z 是丁的一个一度点 则 丁一z 仍然是一棵树 根据归纳假设 丁一z 含有 n 一2 条边 因此 t 含有n 一1 条边 因为在删除z 的同时 我们恰巧删除了一条t 的边 口 推论4 设g 是一个恰含有礼个顶点的连通图 如果g 所含的边数最小 则g 是一棵树 证明 g 不可能含有圈 否则删掉某个圈上的一条边所得图依然连通 但是具有更小 的边数 因此g 是树 口 定理5 设g 是一个连通图 则g 含有一支撑树 证明 我们对g 的边数进行归纳 设g 具有礼个顶点 则根据推论4g 所含的边数最 小为n 一1 如果g 不含有圈 则g 本身就是一棵树 现在 假设c 是g 的一个圈 删除c 上的一条边 所得图还是连通的 根据归纳假设 所得图含有一支撑树 那也是原图的支撑 树 口 1 4 1 嵌入 1 4 三角剖分图 一个连通的2 维流形被称为是一个曲面 给定一个曲面 和一个图g 如果g 可以被 画在r 上 使得g 的边只在其端点处与别的边相交 则说g 可以嵌入在i 上 5 华东师范大学 局部连通图中的同胚不可约支撑树 特别地 如果g 在平面上有一个嵌入 则称g 是一个平面图 设g 是一个嵌入在曲面r 上的图 则 一g 的各个弧连通的区域被称为嵌入图g 的 面 其中 一g 表示从点集r 中除去在g 的边上的那些点 1 4 2 三角剖分图 设g 是一个嵌入在曲面r 上的图 如果g 的各个面都是三角形 则称g 三角剖分曲面 r 或者g 是一个曲面三角剖分图 特别地 如果r 是一个平面 我们说g 是一个平面二角 剖分 关于三角剖分图 我们有如下引理 引理6 r 轨厕每一个顶点数至少为彳的三角剖分图部是局部哈密尔顿连通的俗个点的 邻域的导出子图是哈密尔顿的1 第二章局部连通图简介 本节所讨论的图 如无特别指出 都是连通图 2 1 1 局部连通图的基本概念 2 1 局部连通图的定义 定义1 设g 是一个图 如果g 的每一个顶点的邻域的导出子图都是连通的 则称g 局部 连通的 根据局部连通图的定义 局部连通图具有如下性质 食题1 设g 是一个至少含有3 个顶点的局部连通图 则g 的每一条边都在一个三角形中 证明 设e z 可是g 中任给的一条边 因为g 含有至少三个顶点 并且g 是局部连 通的 则z 一定会和可的邻域中的另一个点 不妨设名邻接 因此 z 鲈形成一个三角形 口 2 1 2 关于局部连通图的一些结论 局部连通图的概念最早是在1 9 7 4 年由c h a r t r a n d 和p i p p e r t 在他们的文章二d 坳 c t d 住n e c t 耐g r 印凰 c p 7 羽中提出来的 他们证明了如下结论 6 华东师范大学 局部连通图中的同胚不可约支撑树 1 如果g 是局部七一连通的 则g 本身是七 1 连通的 2 每一个局部3 连通图都是非平面图 3 如果g 是局部连通的 含有至少3 个顶点 最大度至多是4 则g 或者是哈密尔顿的或 者 一构于k l 1 3 2 2 1 局部连通图的一些性质 2 2 局部连通图的一些性质 1 9 7 9 年 o b e r l y 和s u m n e r o s 7 9 证明说如果一个连通且局部连通的图不含坼 3 则 g 是哈密尔顿的 个幽g 称为是上可嵌入的如果g 的最大亏格为 m 一礼 1 j 其中m n 分别为g 的边数和顶点数 n e b e s 蛐 n e b 8 1 在1 9 8 1 年证明 每一个连通且局部连通图都是上可嵌入 的 一个n 阶图g 称为是顶点泛圈的 如果g 的每一个顶点都在一个长度为七的圈上 对 于每一个3 七 n 1 9 8 1 年 c l a i r k c l a 8 1 证明每一个连通且局部连通的不含k l 3 的图都 是顶点泛圈的 同时 他证明每一个连通且局部3 连通的不含坼 3 的图是泛连通的 也即是 说 g 的任何两个顶点u t 之间都有一条长为 的路 对于每一个3 t n 一1 2 2 2 局部连通图的可收缩边 定义2 设g 是一个局部连通图 e 是g 的一条边 我们说e 是g 的一条可收缩边 如果 g e 仍然是局部连通的 定理8 设g 是一个顶点数至少为2 的局部连通图 则对于g 的任一个顶点u g 有一条 可收缩l 边e u u 证明 取u 使得t 不是g 让 的割点 接下来 我们将会证明t u 是g 的一 条可收缩边 记日 g 几u 很显然 日是连通的 因此只需要证明日局部连通即可 设伽为日中 的通过收缩让t 而得到的新顶点 对任意z y h 我们分如下两种情况来证明 情形l z 删 如果叫譬 日 z 日 z g z 因为g 小 g 0 是连通的 因此我们知道驯 日 z 是 7 华东师范大学局部连通图中的同胚不可约支撑树 连通的 因此我们假定硼 眦 z 如果i g z n u u i 1 那么我们有g g z 是 日 z 的支撑子图 如果 g z 我们同样有g g 是日 蜥 z 的支撑子 图 无论哪种情况 我们都有何 z 是连通的 因为g f b 是连通的 情形2 z 埘 在这种情况下 蜥 砌 t t 一u u g u 一u 假设g l g 2 g m 是g g u 一u 的 分支 因为g g 是连通的 对任意1 i m y g n g 一t 1 y g n g t d 因为g g u 一u 的连通性 我们知道 蜥 牡 g 一u ug lug 2 ug m 是连通 的 口 从以上证明可以看出 如果局部连通图g 的顶点数至少为3 则g 的每个顶点至少与两 条可收缩边相关联 2 3 1 猜想一 2 3关于局部连通图的两个猜想 设g 是一个连通且局部n 一连通的图 如果g 不含导出的k 1 七 2 则g 是哈密尔顿的 的 参见 o s 7 9 以上猜想对七 1 的情形已经在 o s 7 9 中证明了 2 3 2 猜想二 一个图称为是弱泛圈的 如果这个图含有从其围长 最短圈的长度 至周长 最长圈的 长度 之间的每一个长度的圈 对于局部连通图 我们有如下猜想 连通且局部连通图是弱泛圈的 2 4 七一树和弦图 在第一节中 引理6 说三角剖分图都是局部连通图 接下来 我们将证明七一树和2 连 通的弦图是局部连通的 8 华东师范大学局部连通图中的同胚不可约支撑树 2 4 1 关于七 树的一些性质 定义3 任给一个正整数七 图g 称为是一个缸树 如果存在g 的顶点的一个排序 u l 吨 七 仇 n u 1 忱 仇一l 是一个七团 很显然 1 树就是通常定义的树 h w a i l g 戤c h a r d s 和w i n t e r h r w 9 2 证明2 树是 m 凹i m 口ls e n e s p o m f f e f 图 关于3 树和一般七一树的研究可参见 a p 8 6 a c p 8 7 a p 8 9 a p c 9 0 l m n w 0 6 1 定理9 对于后 2 七 树是局部连通的 证明 设g 是一缸树 我们对g 的顶点数进行归纳 最小的七 树是一个顶点数为 七的完全图 显然是局部连通的 一般地 假设u 1 晚 在g 中除 中的点 外 其他顶点的邻域与在g 一 中相同 因此我们只需要考虑 f 各个点的局部连 通性 根据七 树的定义 g 是一个完全图 因此是连通的 对于珧 1 t 七 g 鼽 g g 玑 u y 1 沈 玑一l 鼽 1 鲰 是连通的 口 2 4 2 弦图 设g 是一个图 c 是g 的一个圈 e 是g 的一条边 如过e 的两个端点在c 上但是e 不 是c 的一条边 则称e 是g 的一条弦 一个图g 称为是弦图 如果g 的每一个长度大于3 的圈都含有弦 定义4 设g 是一个图 钞是g 的一个顶点 那么u 被称为是s i m p 托c i o j 的当且仅当g u 是一个完全图 关于弦图 我们有如下的著名论断 引理1 0 眈r 锄弦图有一个鲥唧屁c i 口2 的顶点 2 4 3 关于弦图的一些结论 引理1 1 设g 是一个参连通的弦图 含有至少彳个顶点口是一个3 唧屁c i 口f 的顶点 那么 g t 是2 连通的 9 华东师范大学局部连通图中的同胚不可约支撑树 证明 当u 的度至少为3 时 易于说明 因此假设 佃 可1 反设g u 不是2 连 通的 则z 之一为g 一 的割点 不失一般性 设z 是这样一个割点 并且假定g l 和g 2 是g 一 一z 的两个分支 因为g 含有至少4 个顶点 g l 和g 2 分别含有至少一个顶点 因 为在g 中g 1 和g 2 之间至少有两条内部不交的路 因此秒有邻点在g 和g 2 中 但是因为 t 是一个8 i m p l i c i a l 的顶点 其邻域中任何两个点之间都有边 这和g 1 和g 2 是g u z 的连通分支相矛盾 因此g u 是2 连通的 口 定理1 2 设g 是一个廖连通的弦图 则g 是局糊的 证明 我们对g 的顶点数n 进行归纳 当n 3 时g 娲 显然是局部连通的 一般 地 根据引理1 0 设 是g 的一个s i m p l i c i a l 顶点 根据引理1 1 g u 是2 一连通的 冈为 g 一 是2 连通的弦图 根据归纳假设 g 一 是局部连通的 现在来讨论g 的局部连通性 因为y g m 中的点的邻域在g 中与在g u 中相同 凶此我们只需讨论 m 中各个 点的邻域的导出子图是否连通 首先g f 1 是一个完全图 是连通的 记g 7 g u 对 于z 移 g z g g u u u y b u z 是连通的 口 第三章边不交的支撑树 3 1 定义及应用 设g 是一个图 如果丑和死 是g 的两棵支撑树 并且噩和乃没有公共边 那么我们 称互和疋是g 的边不交的支撑树 图的边不交的支撑树在网络理论中有很多应用 关于这方面的研究可以参考 l h m r 9 8 s s p 9 6 同时 图的边不交的支撑树在组合理论中也有很多应用 例如 根据 x u 0 7 9 一个 图是上可嵌入的如果g 有一支撑树t 使得g e t 至多只有一个奇分支 一个含有奇数 条边的连通分支 因此 如果能够证明g 含有两个边不交的支撑树 则g 是上可嵌入的 如果g 含有两个边不交的支撑树 则g 可以写成两个偶图 所有顶点的度都是偶数 的图 的并 同时 我们知道一个图有处处非零的垂流当且仅当g 可以写成两个偶图的并 i w 巍9 6 p 3 1 0 因此 如果g 含有两个边不交的支撑树 则g 有处处非零的4 流 1 0 华东师范大学局部连通图中的同胚不可约支撑树 3 2局部连通图中的边不交支撑树 3 2 1 边不交支撑树在局部连通图中的扩张性 引理1 3 设g 是一个局考隧通图 e 是g 的一条可收缩边 如果g e 含有两个边不交的支 撑树 则g 也含有两个边不交的支撑树 证明 设e z 并且假设伽是通过收缩e 所得的g g e 中的新点 因为g z 足连通的 我们不妨设可与z 的另一个邻点z 相邻接 让n 和乃是g e 的两个边不交的 支撑树 我们将对n 和死进行修正 使其成为g 的边不交的支撑树 将伽在乃和死中都用 替换 同时删除丑和死中的本不是g 的那些边 这些边对应 于g 中一条与z 相关联的边 将所得图记为趸和巧 不失一般性 设凡 最 昂为趸 的分支 吼 风为z 的分支 进一步 假设y 所在的分支分别为只和凰 将相应 的最 b 昂和地 风 风中的与删在g 中邻接而只与z 在g 中邻接的那些边记 为e 2 e 3 e p 和尼 厶 因为乃和乃边不交 e 2 e 3 e p 和如 厶 q 互不相 同 情形1 z 也在r 和皿中 此时墨u z 3 e 2 e 3 e p 和砭u z z 厶 3 厶 为g 的两个边不交的支撑树 情形2 不失一般性 设在肌中2 与 不在同一个分支中 此时碍u z 耖 e 2 e 3 e p 和zu 轳 厶 厶 为g 的两个边不交的支撑树 口 3 2 2 局部连通图所含的边数 引理1 4 设g 是一个恰有n 个顶点的局部连通图 则g 至少含有2 n 一3 条 边 证明 我们对n i y g l 进行归纳 当n 1 2 时 结论显然成立 根据定理8 我们收 缩边 比如说z y 并将所得图记为g 根据归纳假设 g 含有至少2 n 一1 一3 条边 并且这 2 n 1 一3 条边在g 中都有相应的边与之相对应 同时 根据命题7 在g 中 z 可在一个三 角形中 当收缩z g 7 比g 至少减少了两条边 因此g 含有至少2 佗一1 一3 2 2 n 3 条边 口 华东师范大学局部连通图中的同胚不可约支撑树 3 2 3 局部连通图中的边不交支撑树 根据定理9 我们知道2 树是局部连通的 同时再根据引理1 4 我们知道2 树是同阶的 局部连通中边数最小的一个 2 树含有恰好2 佗一3 条边 下面的定理将要说明 如果一个 局部连通图g 只含有 一3 条边 那么g 是一2 树 定理1 5 设g 是一个恰含n 个顶点的局部连通图 则g 具有恰好2 仃一3 条 边当且仅当g 是一棵2 树 证明 根据上文的讨论 我们只需要证明必要性 假设g 是一个佗个顶点2 钆一3 条边 的局部连通图 则g 的最小度至多为3 我们分两种情况来证明 情形1 6 g 2 我们对n 用归纳法来处理这种情形 当凡 2 时显然 一般地 我们收缩与那个2 度点 关联的一条边 再用归纳假设 也同样易于说明 情形2 6 g 3 设让是一个3 度点 并且有 钍 z z 则一定有 不妨说 z z 叠e g 否则g u z 将含有至多2 m 一1 一4 条边 因次我们假设z 名隹e g 因为6 g 3 并且z 的邻域的导 出子图是连通的 因此一定存在一个点叫与z 和可相邻接 这样 d y 4 因为z 名聋e g 2 点的度在收缩前后不改变 从而 当我们收缩u z 后 g t z 中仍然没有2 度点产生 因为 g 让z 含有2 一1 一3 边 其最小度是3 收缩与g u z 的一个3 度点关联的边 相同的论 证 再收缩与所得图的一个3 度点相关联的边 继续这个过程 一直到所得图只有4 个点为 止 根据我们的论证 这个图应该具有最小度3 同时含有5 条边 但是这不可能 因此 6 g 2 并且每收缩一条与2 度点关联的边之后在新图中都会有2 度点产生 因 此 对g 的顶点数进行归纳 容易看到 g 是2 树 口 定理1 6 设g 是一个局曹黟连通图 如果g 含有甄细分 则g 含有两个边不交序争支撑树 证明 我们对g 的顶点数n 用数学归纳法 当n 4 g 本身就是甄 结论显然成立 一般地 根据定理8 设z 是g 的心细分k 之外的一个点 如果这样的点不存在 则取z 是k 上的一个2 度点 收缩与z 关联的一条边 所得图仍然含有一个托细分 根据归纳假 设 所得图含有两个边不交的支撑树 再由引理1 3 我们知道g 含有两个边不交的支撑树 口 在 l 0 v 0 7 p 6 5 中说一个n 阶的含有2 n 一2 条边的简单图含有心细分 结合定理 1 6 我们有如下的定理 2 华东师范大学局部连通图中的同胚不可约支撑树 定理1 7 假设g 是一个竹阶序明糊图 则下面的条件相互等价 1 g 含有两个边不交的支撑树 例i e g l 2 住一2 j 3 g 含有k 4 细分 3 2 4 两类局部连通图 假设g 是一个n 阶的局部连通图 则g 可以被分为两类 一类恰好含有2 n 一3 条边 显然不含有两个边不交的支撑树 另一类边数至少为2 礼一2 含有两个边不交的支撑树 当g 含有2 礼一3 条边时 根据定理1 5 我们知道g 是一棵2 树 根据2 树的定义 从 尬开始 每次增加一个点 两条边 很容易构造出g 的一棵支撑树和一棵具有礼一1 个顶点 的树 利用x u o n g 的定理 x u 0 7 9 我们实际上已经得到了n e b e s 埘定理 也即是说 任何一 个局部连通图都是上可嵌入的 3 2 5 局部连通图与七一流 定义5 我们说一个定f 句图g 具有处处非零的七一流 如果存在映射 e g oz 七满足如 下条件 j 以 对任意 y g 钆u 叫 j u t t u 一 口 例 对任意e e g e 0 关于局部连通图 我们还有下面的结论 定理1 8 假设g 是一个局部连通图 则g 有处处非零的彳 流 证明 不妨设g 恰具有n 个顶点 因为当g 的边数至少是2 n 一2 时g 有两个边不交 的支撑树 g 可以被写成两个偶图的并 根据 w 西9 6 p 3 1 0 我们知道一个图有处处非 零的4 流当且仅当g 可以写成两个偶图的并 此时g 有处处非零的冬流 因此 我们只需 考虑g 恰有2 n 一3 条边的情形 我们对钆使用数学归纳法 当n 3 时 g 恐 给g 定向使得g 成一个有向的3 圈 让每条边的权值为1 我们得到一个g 的处处非零的垂流 一般地 设z 为g 的一个2 度 点 并且有 z z 易见g z 也还是2 树 根据归纳假设 g z 有处处非零的 垂流 不妨设班的定向是从y 到z 我们让名z 的方向是从z 到z 让z 可的方向是从z 到可 将妒的权值增加1 将z z 和z 扩的权值设定为1 我们得到了g 的一个处处非零的奎流 口 1 3 华东师范大学局部连通图中的同胚不可约支撑树 第四章局部连通图中的同胚不可约支撑树 4 1同胚不可约支撑树 如果一个图的支撑树不含有2 度点 则这棵树被称为是同胚不可约支撑树 h o m e o m o r p k c a l l y i r r e d u c i b l e 印a n n i n gt r e e 简记为h i s t 将一个图是否含有h i s t 的问题限制在平面图 上来考虑 a h i l l 阻i 1 7 4 l 猜想说除尥外的任何一个平面三角剖分都含有一h i s t j m 舭v i t c h m a l 7 纠将此猜想推广到平面近三角剖分 除至多一个面外的所有面都是三 角形的平面图 的情形 a l b e r t s o n b e r m a n h u t c h i 璐o n 和t h o m a 船e n a b h t 9 0 证明了 推广后的猜想 并且猜测任何一个曲面三角剖分也含有一h i s t d 撕d o w h u t c h i 璐o n 和 h u n e k e d h h 9 5 证明每一个环面上的三角剖分图都含有h i s t 本节我们将证明任何一个 顶点数至少是4 的局部连通图都含有h i s t 结合引理6 便得到任何一个曲面三角剖分也 含有一h i s t 的论断 4 2 1 弱2 树的引入 4 2 弱2 一树 容易观察到 每一个顶点数至少为4 的2 一树含有h i s t 因此如果可以证明一个图含有 2 树作为支撑子图 则这个图含有h i s t 但是 并不是所有的局部连通图都含有2 树作为支 撑子图 下图就是一个不含有2 树作为支撑子图的局部连通图的例子 不含2 一树作为支撑树的图 因此 我们将定义一类新图 使得其含有h i s t 并且使得任何一个局部连通图都含有这 类图中的一个作为支撑子图 4 2 2 弱2 树的概念 设日是一个图 仳l u 2 日是两个不同的顶点 并且移g 日是一个新顶点 我们让g 是通过给日添加顶点u 和边仳1 u 2 u 以及边让1 t 2 如果t 1 1 牡2 譬e 日 而得到的图 如果 1 4 华东师范大学局部连通图中的同胚不可约支撑树 边u l u 2 e 日 我们称g 是h 的与t 1 1 札2 相关的 型扩张 并且表示为风 坳 t 如果 u l u 2 簪e 日 我们称g 是日的与让1 t 2 相关的 型扩张 并且表示为风 啦 我们用 h u 来表示日的任意一个通过项点u 而得到的 型扩张 用日 u 来表示日的任意一 个通过顶点u 而得到的 一型扩张 定义6 一个阶为n n 3 的图丁被称为弱参树 如果丁的顶点有一个排序 u 1 啦 一 u n 满足如下条件 以 丁 u 1 忱 地 笺蚝 对任意i 3 4 n 一1 俐t u 1 忱 仇 1 竺t u l 咙 让 ou t l 其中0 八或者 我们将这个排寄 称为t 的一个弱2 树序 4 2 3 关于弱2 树的一些结论 引理1 9 设g 是一个至少含有彳个顶点的弱易树 并且假设彬 g 是一个2 度点 t 是 的礴个邻署 那么或者g 一哪或者g 一 一伽是一个弱2 树 在这种情况下 我们用 ge 埘表示相应的阶数少一的弱2 一树 证明 因为d 2 因此对于任意一个弱2 树序 训都可以被放在序列的最后一位 而不影响其他顶点的排序 因此我们假定存在g 的一个顶点序 使得加在这个序列中的 最后一位 那么根据定义6 引理结论显然 口 弓 理2 q 设t 是一个至少含有4 个顶点的弱2 树 且 是相应的顶点穿 那么t 至少满足 下面性质之一 p f 存在u u y t 使得d u d 2 并且 u n r u d j p 2 存在u u y 丁 使得d 扣 2 乱 u 并且出e t t 2 顶点对t u y t 被称为丁的可移除顶点对 证明 我们对佗 j y 丁 j 用数学归纳法 当n 4 时 t 同构于酊 甄中移去一条 边 让g 中的两个2 度点为缸 u 我们知道此时g 具有性质p 1 当n 5 时 让名为 中 的最后一个顶点 让 和 为gez 中的两个2 度点 如果 名 n z 妙 d 取z z 中 任意两个为仳 u 得知相应的图满足性质p 1 如果 名 n z 0 比方说耖 z 让 札 可 u z 得知相应的图满足性质p 2 1 5 华东师范大学 局部连通图中的同胚不可约支撑树 假定礼 6 假设顶点数小于佗的弱2 一树满足引理2 0 令t t 7 是顶点序 中的最后一个 顶点 并且让r te 协 很显然 r 是一个弱2 树 相应的顶点序是 那么 伽 将是t 的可移除点对满足p 2 如果 伽 n t l 口 兰 u 并且t 满足p l 那么 u 伽 将是丁的可移除点对满足 p 2 如果 n 并且心和口满足p 2 那么 移 伽 将是丁的可移除点对满足 p 1 如果 牡 t 那么 u 叫 将是丁的可移除点对满足p 2 口 引理2 1 至少含有彳个顶点的弱参树含有删z 证明 假设t 是一个至少含有4 个顶点的弱2 树 我们将通过对丁的顶点数扎使用归 纳法来进行证明 当n 4 那么t 蛭 丁含有h i s t 如果n 5 通过分情况讨论 也易 于说明t 含有h i s t 现在假设n 6 根据引理2 0 令 t l y t 是t 的可移除顶点对 那么 根据 可移除顶点对的定义和定义6 我们知道丁e u u 是一个弱2 一树 然后 根据归纳假设 t e t u 含有h i s t 比如说r 如果t 满足p 1 那么u 和u 在t 中有一个公共邻点 如 果t 满足p 2 比如说d u 2 那么 中的另外一个点将是u 和秒的公共邻点 因此 不管哪种情形 总存在一个点埘 t n 因此 t t u 叫t 加u 是丁的一个 h i s t 口 4 3 局部连通图中的h i s t 引理2 2 每一个局部连通图都含有一个弱参树作为支撑子图 证明 设g 是一个含有顶点数n 3 的局部连通图 因为3 圈是弱2 树 因 此g 含有弱2 树作为子图 令t g 是一个弱2 一树使得i y t i 最大 我们将证明 1 6 华东师范大学 局部连通图中的同胚不可约支撑树 y 丁 y g 否则 y g 一y 丁 d 因为g 是连通的 存在顶点耖 y 丁 使得 晰 t 0 其中蜥 u 是u 在 中的邻居 假设名是 中的一个点 因为t 是弱 2 树 u ny 丁 2 坼 u 0 义因为g u 是连通的 假设p 是一条 u 名 路 其中 u ny 丁 现在 让加是尸上的第一个不在y t 中的点 则 u u 加 导出一个三 角形 那么 丁 u ot t j 是一含有比丁有更多顶点的弱2 树 因为u 叫u t 彬 e g 并且 丁 g 我们有丁 扎 o 训 g 但是这与 l y 丁 i 最大相矛盾 口 定理2 3 每一个顶点数至少为4 的局部连通图都含有m s t 证明 根据引理2 1 和引理2 2 定理结论显然 1 7 口 a c p 8 7 1 a p 8 6 a p 8 9 a p c 删 c l a 8 1 c p 7 4 d h h 9 5 1 d i r 6 1 h i l 7 4 参考文献 m i c h lo a l b e r t s o n d a v i dm b e r m 觚 j o 觚p h u t c l l i 瑚o n a i l d a 瑙t e nt h o m a 鹋e n g r a p l l 8w i t hh o m e o 珊d r p l l i c l yi r r e d u c i b l es p 觚础唱t 嗍 zg 唧 弛 删 1 4 2 2 4 7 2 5 8 1 9 9 0 s t e f a na r i l b o r g d e r e kg c o m e i l 8 n da n d r z e jp r o s k u r o w g k i c o m p l e 妞t yo ff i n d i n g e i n b e d d i n g bi na 如t r 跏mza 幻e 6 m i cd 妇c 他t em e 纸d 幽 8 2 2 7 7 2 8 4 1 9 8 7 s t e f a na r n b o r ga n da n d r z e jp r o s k l l r o w s k i c h a r a u c t e r i z a t i o na n d 删t i o no fp a r t i 址 3 t r 嘲 翻m m 正a 幻e 6 m t cd 妇c 他 e 胁纨d 幽 7 2