（运筹学与控制论专业论文）曲面的极小禁用子图与图的亏格.pdf

d o c t o r a ld i s s e r t a t i o ni n2 0 11 u 1 1 i v e r 8 i t yc o d e ：1 0 2 6 9 s t u d e n tn m n b e r ：5 2 0 8 0 6 0 1 0 2 0 d e p a r t m e n t ： m a t h e m a t i c s s p e c i a l t y ： m a j o r ： s u p e r v i s o r ： a u t h o r ： h a nr e n d e n 舀um a 一- a p r i l2 0 ，2 0 1 1 _ 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文曲面的极小禁用子图与图的亏格， 是在华东师范大学攻读硕士嘎夕( 请勾选) 学位期间，在导师的指导下进 行的研究工作及取得的研究成果。除文中已经注明引用的内容外，本论文不 包含其他个人已经发表或撰写过的研究成果。对本文的研究做出重要贡献 的个人和集体，均已在文中作了明确说明并表示谢意 作者签名：蝉 日期：2 口，年，月2 7 日 华东师范大学学位论文著作权使用声明 曲面的极小禁用子图与图的亏格系本人在华东师范大学攻读学位 期间在导师指导下完成的硕士壤影( 请勾选) 学位论文，本论文的研究成 果归华东师范大学所有。本人同意华东师范大学根据相关规定保留和使用 此学位论文，并向主管部门和相关机构如国家图书馆、中信所和”知网”送 交学位论文的印刷版和电子版；允许学位论文进入华东师范大学图书馆及 数据库被查阅、借阅：同意学校将学位论文加入全国博士、硕士学位论文共 建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采用影印、缩 印或者其它方式合理复制学位论文。 本学位论文属于( 请勾选) ( ) 1 经华东师范大学相关部门审查核定的”内部”或”涉密”学位论 文丰，于年月 日解密，解密后适用上述授权。 2 不保密，适用上述授权 导师签名二陵本人签名咝 2 0 ，年y 月7 日 涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定 过的学位论文( 需附获批的华东师范大学研究生申请学位论文”涉密”审批表方为有 效) ，未经上述部门审定的学位论文均为公开学位论文此声明栏不填写的，默认为公开学 位论文，均适用上述授权 马登举博士学位论文答辩委员会成员名单 姓名职称单位备注 邵嘉裕教授同济大学主席 魏木生教授上海师范大学 张晓东教授上海交通大学 薛军工教授复旦大学 詹兴致 教授华东师范大学 摘要 论文主要研究了曲面上的极小禁用子图的构造及其相关问题论文系 统地讨论了曲面上的极小禁用子图的构造方式，研究了可定向曲面上的无 玩 3 - 图子式的极小禁用子图的结构特征和嵌入特征，证明了克莱因瓶上的 无甄3 图子式的不同构的极小禁用子图仅有1 2 2 个同时，论文还研究了 一条路与一个连通图的联图的亏格与不可定向亏格问题以及交叉数临界图 的构造问题其主要结果如下 一、给出了六种构造一个可定向曲面的极小禁用子图的方式这些 方式包括粘合两个图的一个顶点，一个图替换另一个图的一条边，粘合两个 图的一条边，粘合两个图的两个顶点，一个图放在另一个图的某个嵌入的一 个面内，以及顶点分裂等类似于一个可定向曲面的极小禁用子图的构造方 式，给出了四种构造一个不可定向曲面的极小禁用子图的方式同时，作为 对a r c h d e a c o n l 4 j 提出的一个公开问题的探讨，给出了环面上的7 个孓正则 的极小禁用子图 二、 研究了可定向曲面上的无虬3 - 图子式的极小禁用子图的结构特 征，并用一组定理刻画了其嵌入特征 三、 证明了克莱因瓶上的无蚝3 图子式的不同构的极小禁用子图的 个数仅有1 2 2 个 四、 确定了一条路与另一条路的联图，一条路与一个圈的联图，以及 一条路与某个完全图的联图的亏格和不可定向亏格这些结果与e 1 1 i n g h a n l 和s t e p h e n s 【2 0 j 在2 0 0 7 年提出的一个问题有密切的关系 五、 给出了几种构造一个詹交叉数临界图的方式这些方式包括融 合两个图的一条边，一个图替换另一个图的一条边等特别地，给出了两 种构造一个3 _ 正则的肛交叉数临界图的方式还确定了分别用蚝，娲3 蚝一e ，3 一e 替换一个图的每一条边得到的图的交叉数 _ 关键词： 嵌入， 曲面的极小禁用子图，图的亏格，图的不可定向 亏格，交叉数临界图 中图分类号：0 1 5 7 5 a b s t r a c t i nt h ed 汝沦r t a t i o n ，w es y s t e m a t i c a l l yd i s c u _ s st h ep r o b l e ma b o u tc o n - s t r u c t i n gi n i n i m a l lf o r b i d d 阻s u b g r 印l l sf o ras u r f ：a c ea n dp r o p e r t i e so fm i n i m a lf o r b i d d e ns u b 铲a p l l s 诵t h o u t 蚝，3 一m i n o r 五d ra no r i e n t a b l es u r f 如e w - e s h o wt h a tt h e r ea r ee x a c t l y1 2 2n o n - i s o m o r p l l i cm i l l i m a lf o r b i d d e ns u b 铲a p h s w i t h o u tj 岛3 一m i n o rf o rt h ek 1 e i nb o t t l e ，a l l dd e t e h i l i n a t et h eg e n l 瑕a n d n o n o r i e n t a m eg e i l u so ft h ej o i no fap a t hw i t hac o m c t e dg r a p h a l s o ， w ed i s c u s st h ep r o b l e ma b o u tc o 璐t r u c t i n ga 缸c r o s s i n 眇c r i t i c a l 目a p h t h e d e t a l i l sa r ea sf b l l o 瓢璃 1 s i ) ( m e t h o d so fc o 璐t r u c t i n gm i n i m a lf o r b i d d e ns u b 口印h sf o ra no r i e n t a b l es u r f a c ea r eg i v e n ，s l l c ha s9 1 u i n gav e r t e x ( t w dv e r t i c e s ，r e s p e c t i v e l y ) o fag r a p h 诵t hav e r t e x ( t w ov e r t i c e s ，r e s p e c t i v e l y ) o fa n o t h e rg r 印h ，r e - p l a c i n g 瓶e d g eo fag r 印hb ya n o t h e rg r a p h ，p l a c i n ga 铲a p hi naf a u c e0 f a ne l b e d d i n go fa n o t h e r 铲印ha n ds p l i t t i n gav e r t e x ，e t c s i m i l a r l y f 6 u r m e t h o d s0 fc o n s t r u c t i n gm i n i m a lf o r b i d d e ns u b g r 印h sf o ran o n o r i e n t a b l e s u r f a c ea r eg i v e n a l s o ，7c u b i cm i l l i m 以f o r b i d d e ns u b g r 印h sf o rt h et o r u s a r e 舀v e n ，w h i c ha r e 行o md i s c u s s i o na b o u ta no p e np r o b l e mp r o p o s e db y a r d 【l d e a c o n f 4 】 2 s t r u c t l l r a la n d 如e d d i n gp r o p e r t i e so fm i i l i m a lf o r b i d d e ns u b g r a p h s w i t h o u tj g 3 m i n o rf o ra no r i e l l t a b l es u r f a u c ea r ed i s c u s s e d 3 i ts h 佣，st h a tt h e r ea 鹏e x a c t l y1 2 2n o n - i s o m o r p m cm i i l i m a lf o r b i d d e ns u b g r a p l l s 、) l ，i t hn o 娲，3 一m i n o rf o rt h ek l e i nb o t t l e 4 t h eg e n u sa n dn o n o r i e n t a b l eg e n u so ft h ej o i no fa n o t h e rp a t h 们t h ap a t h ，ac y c l e ，o rs o l ec o m p l e t eg r 印ha r ed e t e r i i l i n e d t h e s er e s u l t sh a e t h ec l o s e dr e l a t i o n 谢t ht h eq u e s t i o np r o p o s e db ye l l i n 曲锄a n ds t e p h e i l s 【2 0 1 l n2 d u 7 5 s o m em e t h o d so fc o i l s t m c t i n ga 克c r o s s i n 争c r i t i c “g r a p ha r e 舀v e n ， s u c ha u s 西u i n g8 ne d g eo fag r a p h 丽t ha ne d g eo fa n o t h e rg r a p h ，r e p l a u c i n g a 1 1e d g eo fa 伊印hb ya n o t h e r 黟a p h ，e t c i np a r t i c t l l a r ，t w om e t h o d so f c o n s t r u c t i n ga3 - r e g u l 盯b c r o s s i n 分c r i t i c a lf 印ha r e 舀v e n t h ec r o s s i n g 玎u m b e ro fag r 印hw h i c hi so b t a j n e d 矗o mag r a p hb yi t sa n ye d g er e p l 掀姐 b y 蚝，飓，3 蚝一eo r 蚝，3 一i sd e t e r i l l i n e d k e yw b r d s ： e m b e d d i n g ， 面n i m a lf o r b i d d e ns u 畸印hf o ras 1 1 r f a c e ， g e i m s0 fag r 印h ， n o n o r i e t a b l eg e i m so fag r 印h ， c r o s s i n 分c r i t i c a lg r a p h a m ss u b j e c tc l a s s i f i c a t i o n ：0 5 c 1 0 ，0 5 c 7 5 中文摘要 英文摘要 主要符号说明 目录 第一章绪论 1 1 研究背景 1 2 图的基本概念 1 3 图的曲面嵌入的基本概念 第二章可定向曲面的极小禁用子图的构造 2 1 一些引理 2 2 粘合一个顶点 2 3 用一个图替换另一个图的一条边 2 4 粘合两个顶点 2 5 粘合一条边 2 6 将一个图放在一个面内 2 7 顶点分裂 2 8 环面上的3 正则的极小禁用子图 第三章不可定向曲面的极小禁用子图的构造 3 1 一些引理 3 2 粘合一个顶点。 3 3 用一个图替换另一个图的一条边 i 一 一 1 l 4 6 1 1 4 5 2 5 6 0 3 卜- 7 s d ； 谳 碰 1 l 4 6 n n m璩挖弱弱弘 盯卵鼹如 目录 3 4 粘合两个顶点4 7 3 5 将一个图放在一个面内4 9 第四章可定向曲面的无玛3 - 图子式的极小禁用子图5 1 4 1 结构特征5 1 4 2 嵌入特征5 6 第五章克莱因瓶上的无娲3 - 图子式的不同构的极小禁用子图 6 3 5 1 不可定向曲面上的极小禁用子图的性质6 3 5 2克莱因瓶的无凰3 - 图子式的极小禁用子图6 6 第六章一条路与一个连通图的联图的亏格和不可定向亏格8 3 6 1 构造新嵌入的两种方式8 3 6 2 一条路与另一条路的联图的亏格和不可定向亏格8 6 6 3 一个路与某个完全图的联图的亏格与不可定向亏格9 2 第七章交叉数临界图的构造 1 0 1 7 1 融合一条边1 0 1 7 2 用一个图替换另一个图的一条边1 0 3 7 3 正则的交叉数临界图的构造1 0 9 第八章结束语 1 1 3 附录 1 1 5 附录一克莱因瓶上的无凰f 图子式的不同构的极小禁用子图1 1 5 附录二读博士期间完成的科研工作1 2 3 参考文献1 2 5 致 射1 3 3 s g ，y ( g ) 彳( g ) y ( g ) e ( g ) t 凹( g ) f x f p m f+h 7 g 一6 主要符号说明 亏格为夕的可定向曲面 亏格为 不可定向曲面 图g 的亏格 图g 的不可定向亏格 图g 的顶点集 图g 的边集 树 图g 的交叉数 集合x 中的元素的个数 有仇个项点的路 f 和日的联图 顶点t ，的旋转系统 图g 删去边6 得到的图 第一章绪论 本章旨在介绍研究背景、图的基本概念、以及图的曲面嵌入的基本概 1 1 研究背景 一个曲面是指一个紧的没有边界的2 维流形曲面可分为可定向曲面 与不可定向曲面一个可定向曲面是一个球面添加夕个环柄构成的曲 面，这里，夕是一个非负整数，且夕被称为最的亏格一个不可定向曲面 是一个球面挖掉 个不相交的圆盘后分别补上麦比乌斯( m 孙i i l s ) 带构成的 曲面，这里， 为正整数，且 被称为的亏格 一个图g 在一个曲面s 上的一个嵌入是指一个从g 的顶点集到s 的 一个子集的一一映射和从g 的边集到s 的一个由两两不交的简单开曲线组 成的集合的一个映射，使得每条边的像连接两个顶点或一个顶点的像，且这 条边的像不包含任何顶点的像一个曲面s 的一个极小禁用子图是这样的 一个图，它的任一个顶点的度不小于3 ，且它不能嵌入在曲面s 上，但是，删 去这个图的任何一条边后所得到的图可以嵌入在曲面s 上 图在曲面上的嵌入理论是拓扑图论的重要的研究领域十九世纪，对四 色问题的研究和对h e a w o o d 地图问题的研究导致人们对图在曲面上的嵌入 的关注从二十世纪六十年代起，图在曲面上的嵌入理论开始了飞速的发 展h e a w d o d 地图问题的解决以及r 加e r t s o n 和s e y m o u r 一系列利用图在 曲面上的嵌入来研究图子式( i i l i n o r ) 的文章推动了图在曲面上的嵌入理论 的发展 1 9 3 0 年，k u r a t o w s l 【i f 删证明了一个图是平面图当且仅当这个图没有 子图同胚于蚝或恐由于一个图可嵌入在平面上当且仅当它可嵌入球 2 第一章绪论 面上，所以球面的不同构的极小禁用子图只有蚝和玛3 随后，e r d 6 s 提 出下面的问题：对于任意一个曲面，它的不同构的极小禁用子图是否有限 多个? 1 9 7 9 年，g 1 0 v e r ，h m l e k e 和w a n g 等人【州发现了射影平面的1 0 3 个 不同构的极小禁用子图心c h d e a u c o n 【1 1 在他的博士论文中证明了射影平面 只有这1 0 3 个不同构的极小禁用子图1 9 9 0 年，r o b e r t 8 0 n 和s e y m o u r 刚 证明了对于一个曲面，它的不同构的极小禁用子图是有限多个，回答了 e r d 掘的问题需要指出的是，r 0 b e r t s o n 和s e y m o u r 的证明运用了反链的 方法，但是，他们没有给出不同构的极小禁用子图个数的一个上界另外， a r c h d e a u c o n 和h 1 1 i l e k e 【6 j 独立的证明了不可定向曲面的极小禁用子图有有 限个 接下来的问题是一个曲面的极小禁用子图的个数与曲面的亏格关系是 怎样的? 如何构造? 对于固定的曲面，它的任一个极小禁用子图的顶点数或 边数是怎样的? e n e u f e l d 曾使用计算机找到了6 5 6 个2 连通的有1 0 个顶 点的环面上的极小禁用子图，又找到3 1 7 8 个2 连通的有1 1 个顶点的边数 不超过2 4 条的环面上的极小禁用子图( 见【4 0 】) 到目前为止，环面上的极 小禁用子图的个数仍未知a r c h d e a u e o n 在文献 4 】中提出一个寻找环面上 的孓正则的极小禁用子图的公开问题m o h a u r 和t h o m a s s e n 在文献【4 0 】中 提出了如下的问题：是否环面上的每一个极小禁用子图的边数小于1 0 0 7 这 些问题都没有解决 尽管一个曲面上的极小禁用子图的个数乃至顶点数或边数的界很难确 定，然而，我们可以从构造方式去研究在本论文的第二章中，我们通过粘 合两个图的一个顶点或两个顶点，粘合两个图的一条边，用一个图替换另一 个图的一条边，将一个图放在另一个图在某个可定向曲面的一个嵌入的面 内，以及顶点分裂等方式来构造一个可定向曲面上的极小禁用子图作为对 a r c h d e a c o n 在文献4 1 中提出的一个公开问题的探讨，在第二章中，我们给 出了7 个环面上的3 正则的极小禁用子图 在第三章中，我们通过粘合两个图的一个顶点或两个顶点，用一个图替 换另一个图的一条边，以及将一个图放在另一个图在某个不可定向曲面的 一个嵌入的面内等方式来构造一个不可定向曲面上的极小禁用子图 研究曲面的极小禁用子图有一个途径是对极小禁用子图附加某种条件 2 0 0 9 年，g a g a r i n ，m y r v o l d 和c h a m b e r s f 2 5 】等人证明了环面上的无蚝，3 图 1 1 研究背景 3 子式的极小禁用子图只有1 1 个，并将它们列出从列出的这1 1 个图中，可 以看出环面上的任一个无蚝3 图子式的极小禁用子图至多有1 2 个顶点 在论文的第四章中，我们研究了可定向曲面上的一个无蚝3 _ 图子 式的极小禁用子图的结构特征和嵌入特征另外，我们构造了可定向曲面 上的一个无飓 3 - 图子式的极小禁用子图，使得它的顶点数为7 9 + 5 球面 或环面上的无蚝丁图子式的极小禁用子图的最大顶点数恰好都满足上面 的式子 在论文的第五章中，我们证明了克莱因瓶上的无蚝3 - 图子式的不同构 的极小禁用子图仅有1 2 2 个 与曲面上的极小禁用子图密切联系的一个问题是图的亏格以及不可定 向亏格问题一个图g 的亏格，记为7 ( g ) ，是最小的g ，使得g 可嵌入在可 定向曲面鼠上，而一个图g 的不可定向亏格，记为彳( g ) ，是最小的 ，使 得g 可嵌入在不可定向曲面上确定一个图的亏格是一件很困难的事 t h o m a s s e n i 叫证明了图的亏格问题是n p - 完备问题到目前为止，仅有少 数几类图的亏格和不可定向亏格被确定，像完全图( 见f 4 9 1 5 0 1 ) 、完全二部 图( 见【4 7 】【4 8 】) 等人们一直努力地确定一些特殊图类的亏格和不可定向亏 格，并不断有新成果出现，见文献1 4 1 1 9 1 f 2 0 】f 2 1 】等 由于完全二部图的亏格和不可定向亏格都已确定，在2 0 0 7 年，e l l i n g - h a m 和s t e p h e n s l 2 0 j 提出下面的问题：设有最大度至多为扎的具有m 个项 点的图f 和最大度至多为m 的具有礼个顶点的图日，使得这两个图的边数 之和至多为警在什么情况下，完全二部图m 的一个最小亏格嵌入可以 扩展为f + 日的一个嵌入而不增加亏格? 这里f + 日表示f 与日的联图 在本论文的第六章中，我们证明了当m 2 且佗2 时，r + p m 的亏 格等于，。的亏格，且r + r 的不可定向亏格等于，n 的不可定向亏 格，这里，p m 和r 分别是有m 和死个顶点的路我们还证明了m 2 且 n 2 时，r + 的亏格等于m 的亏格，且r + 的不可定向亏格 等于m 的不可定向亏格，这里是有m 个顶点的圈我们的结果与上 述的问题有密切的关系另外，在本章中，我们还研究了路与几个完全图的 联图的亏格和可定向亏格问题 与曲面上的极小禁用子图相关联的另一个问题是交叉数临界图问题 如果一个图是某个曲面的一个极小禁用子图，那么它有可能是一个交叉数 4 第一章绪论 临界图，比如玩和凰3 都是球面的极小禁用子图，它们也是1 交叉数临 界图反之亦然一个图g 称为肛交叉数临界的，如果g 的交叉数不小于 尼，但是对于g 的任意一条边e ，g e 的交叉数小于七如果存在一个正整 数七，使得一个图是虹交叉数临界的，那么这个图是一个交叉数临界图 一般说来，确定一个图的交叉数是很困难的g 盯e y 和j o h i l s o n 在文献 2 6 1 中证明了确定任意一个图的交叉数的问题是n p 完备的图的交叉数 在技术领域有广阔的应用，如电子线路板设计中的布线问题( 见文献【9 】) 另 外，它与离散几何、数论等数学分支也有密切的联系( 见文献【6 1 】等) 关于交叉数临界图的构造常利用平面图或嵌入在射影平面的图，( 见文 献f 3 0 1 f 5 6 1 等) 尉c h t e r 和t h o m a s s e n 州证明了对于某个七，如果有无限多 个r - 正则的七交叉数临界图，那么，r 等于4 或5 于是，对于固定的南，孓 正则的“交叉数临界图有有限个人们要问这样的图的结构怎样呢? 有怎 样的性质呢? 瞰d l t e rf 删证明了交叉数为2 的2 交叉数临界图只有8 个 在本论文的第七章中，我们通过两个图的边融合，一个图替换另一个图 的一条边的方式来构造一个交叉数临界图特别地，我们通过边融合以及顶 点替换这两种方式，构造了一个3 _ 正则的肛交叉数临界图另外，我们还 确定了分别用蚝，蚝3 蚝一e ，蚝，3 一e 替换一个图的每一条边得到的图的 交叉数 1 2图的基本概念 在这一节中，我们介绍图的一些基本概念若在其它章节出现而本节没 有介绍的概念，可在文献【1 3 】，【1 7 】，【4 0 】中找到如果没有特别说明，本论文中 的图都是简单图，即没有环及重边的图如果一个图有环或重边，那么这个 图称为一个伪图 两个图g 和日称为同构的，如果存在两个一一映射1 9 ：y ( g ) 一y ( 日) 和：e ( g ) 一e ( 日) ，使得e = 乱钉当且仅当砂( e ) = 口( u ) 目( u ) ；这样一个映 射对( p ，咖) 称为g 和日之间的一个同构 把g 的一条边e 从g 中删去，并使它的两个端点重合，这个过程称为 收缩边e 如果一个图日同构于将另一个图g 的一个子图g 中的一些边 收缩后得到的图，那么日称为g 的一个图子式 1 2 图的基本概念5 设g 是一个图如果日同构于g 或者日是由向g 的一些边上添加度 为2 的顶点得到的图，那么日称为g 的一个细分图对于两个图日和g ， 如果存在第三个图q ，使得q 既同构于日的一个细分图，又同构于g 的一 个细分图，那么我们称日同胚于g 设e = u 移为图g 的一条边，如果让和 口在g 中的度都大于2 ，那么在e 上添加一些度为2 的顶点后，就得到一条 以珏和 为端点的路p 此时，p 被称为g 的一条拓扑边 一个圈c 称为g 的一个非分离圈，如果g y ( c ) 是连通的否则，c 被称为g 的一个分离圈 将n ( 礼2 ) 个顶点与同一个顶点u 连接得到的树，称为一个星图，而 让称为这个星图的中心一个图g 的支撑树是指g 的生成子图，它同时 又是树设g 是一个连通的图，且t 是它的一个支撑树对于任意一条边 e e ( g ) e ( t ) ，在t + e 中存在唯一的一个圈倪e 被称为g 的一个基 本圈 如果一个图g 能画在平面上使得它的边仅在端点相交，则称g 为平面 图下面的定理是判定一个图是否为平面图的一个标准 k u r a t o w s k i 定理p 卅一个图g 是平面图当且仅当它没有子图同胚 于蚝或3 设日是g 的一个子图g 的一条不在日中而两个端点在h 中的边， 或者g y ( 日) 中的一个分支连同所有一个端点在日中另一个端点在这个 分支中的所有的边，称为一座日一桥设b 是一座日一桥，则，bn 日中的每 个顶点都称为b 的一个附着点 设c 是图g 的一个圈，再设b 1 和岛是c 的两座桥如果b l 和岛 满足下列的一个条件： ( 1 ) b 1 和b 2 有三个相同的附着点； ( 2 ) c 上有四个按下列顺序z 1 ，勋，z 3 ，瓢出现的顶点，使得z l 和z 3 是 b l 的附着点且z 2 和观是岛的附着点； 那么，b l 和岛称为c 的两座交叠的桥关于c 的两座交叠的桥，有 下面的定理 定理1 2 1 【6 6 4 0 】设c 是一个平面图g 在平面上一个嵌入的一个圈， 再设b 1 和岛是c 的两座交叠的桥则，b 1 和岛应嵌入在c 的不同的面 6 第一章绪论 1 3 图的曲面嵌入的基本概念 我们已在研究背景中给出了曲面的定义这一节的开始，我们介绍几种 特殊的曲面可定向曲面岛就是球面，而s 1 称为环面不可定向曲面l 称为射影平面，而2 称为克莱因瓶下面，我们给出拓扑学中的两个定理 定理1 3 1 1 7 j对球面添加m 个环柄( 或管子) ，并将n ( n 0 ) 个不相 交的圆盘换成麦比乌斯带，所得的曲面就是在球面上将2 仇+ n 个不相交的 圆盘换成麦比乌斯带的结果 j o r d a n 曲线定理p 8 j平面上的一个简单闭曲线c 将这个平面分成两 个连通分支这两个分支都以c 为边界 一个图g 嵌入曲面s 上称为2 胞腔嵌入，如果s g 中每个分支同胚 于一个开圆盘此时，每个分支称为g 在曲面s 上嵌入的一个面 以下提到的图无特别说明是指连通图 一个曲面s 的e u l e r 示性数x ( s ) 定义如下：当s = 岛时，x ( s ) = 2 2 9 ；当s = i 时，) ( ( s ) = 2 一危 e u l e r 公式设g 是一个2 胞腔嵌入在曲面s 上的图，如果g 有n 个顶点，g 条边，在曲面s 上有，个面，那么佗一口+ ，= x ( s ) 我们可以用组合的方式来描述一个图g 在一个曲面s 上的2 胞腔嵌 入假定图g 己2 胞腔嵌入曲面s 上对任一个顶点 ，按某个方向，比如 顺时针方向，给与顶点u 关联的边一个循环置换，记为仉它称为口的一个 旋转系统令7 r = ( ；u y ( g ) ) 再给出一个定义在g 的边集上的示性函 数入：e ( g ) _ 1 ，一1 ) 如下设e = 删是g 的一条边，如果沿着e ，吼与 一致，那么a ( e ) = 1 ；否则，令a ( e ) = 一1 再令= ( 丌，a ) 它称为g 的 一个嵌入系统这样，g 在曲面s 上的这个嵌入就可以用= ( 7 r ，入) 表示 反之，给定一个图g 的一个嵌入系统= ( 7 r ，入) ，可以确定g 在某个 曲面s 的一个2 胞腔嵌入首先，任取一个顶点z 和与z 关联的一条边 e = z 牡然后，从z 出发沿e 到乱，再沿边e = 吼( e ) 继续走下去如果遇到 图的曲面嵌入的基本概念7 某条边百= 伽名满足a ( 习= 一1 ，则从叫出发沿百到z 后，沿边f = 1 ( 动 继续走下去，这里7 r 1 ( 百) 表示百按死( 习的逆向旋转后得到的边这样，经 过有限次后，又回到开始的边e 且沿e 走下去的方向还是从z 到t 的，如此 得到的一个闭迹称为的一个面迹如果一个面迹上的任何一个项点仅出 现一次，那么这个面迹是一个圈，称为一个面圈按照上述方式将n 所有的 面迹找出来，作成集合f 接下来，对于每一个面迹f ( 假定它有m 条边) ，取一个僻凸多边形连 同它的内部来表示它，并在这个凸多边形的顶点处标上与f 的顶点一致的 字母最后，将这f f | 个凸多边形沿边按照的g 标号要求粘合就构成了一个 曲面这样，由g 的嵌入系统n = ( 7 r ，a ) 就确定了g 在某个曲面s 的一个 2 胞腔嵌入，并且这个嵌入就可以用表示 如果在g 的一个2 胞腔嵌入n 中，一个圈上有奇数条边的示性函数值 为1 ，那么这个圈称为单侧的；否则称为双侧的如果在g 的一个2 - 胞腔 嵌入中存在一个单侧圈，那么称是g 在一个不可定向曲面上的嵌入； 否则，称是g 在一个可定向曲面上的嵌入 在g 的一个2 一胞腔嵌入中，设c = e l 钉1 e 2 e l 饥是一个双侧圈 对于任意的t = l ，2 ，z ，如果e 件1 = 硅( 岛) ，那么所有的边( e t ) ，磋( e i ) ， ，7 喹- 1 ( e ) 称为圈c 的左侧边，所有含有圈c 的左侧边的c 的桥的并集 称为c 的左图，记为g f ( c ) ；类似地，可以定义c 的右图，记为g ，( c ) 在 g 的一个2 胞腔嵌入中，如果一个圈c 可连续形变收缩为一个点，那么 c 称为的一个可收缩圈否则，c 称为的一个不可收缩圈 设是一个图g 在一个曲面上的一个2 - 胞腔嵌入如果c 是双侧的 且g f ( c ) 和g ，( c ) 没有公共边，那么c 称为一个曲面分离圈特别地，一个 面圈是一个曲面分离圈设圈c 是g 的一个非分离圈，且c 上没有弦如 果c 是n 的一个不可收缩圈，那么c 不是一个曲面分离圈 设c = z l z 2 z 七z 1 不是一个图g 在某个曲面上的一个2 胞腔嵌入 的一个曲面分离圈我们说沿c 剪曲面是指下面的过程： ( 1 ) 如果c 是双侧的，那么，沿c 剪开曲面后，曲面上出现两个洞，并且 出现c 的两个复制品和g ”，使得c 的所有左侧边都与g 7 上的相应的 顶点关联，而c 的所有右侧边都与c ”上的相应的顶点关联然后，取两个 圆盘分别封住两个洞 8 第一章绪论 ( 2 ) 如果c 是单侧的，那么，沿c 剪开曲面后，曲面上出现一个洞，并 且g 被一个圈= z l z 2 一z l 替换，使得c 的所有左侧边相 应的与z l z 2 孤关联，而所有右侧边相应的与硝关联然后，取 一个麦比乌斯带封住这个洞 设是一个图g 在一个曲面s 上的一个2 胞腔嵌入，再设c 不是 的一个曲面分离圈设g 是沿c 剪曲面得到的图，再设是相应的嵌入 则的所有的面迹都是g 的嵌入的面迹，而c 上的边被它在g 7 的复 制品替换得到当c 是双侧圈的时候，如果s 是一个可定向曲面，那么n ， 是一个在亏格比s 小1 的可定向曲面上的嵌入；如果s 是一个不可定向曲 面，那么，是一个在亏格比s 小2 的不可定向曲面或球面的嵌入同时，c 的两个复制品都是，的面圈当c 是单侧圈的时候，7 是一个在亏格比s 小l 的不可定向曲面上的嵌入，且c 是7 的面圈 一个图的亏格与不可定向亏格有如下关系： 定理1 3 2 l 删如果一个连通图不是树，那么 彳( g ) 2 7 ( g ) + 1 一个图g 在可定向曲面s ( g ) 上的一个嵌入称为一个最小亏格嵌入 而在不可定向曲面彳( g ) 上的一个嵌入称为一个最小不可定向亏格嵌入 这两种嵌入与2 - 胞腔嵌入的关系如下 定理1 3 3 【7 3 1每一个连通图的最小亏格嵌入都是2 胞腔嵌入 定理1 3 4 【4 l l 设g 是一个连通图如果彳( g ) 2 ，y ( g ) + 1 ，那么g 的 每一个最小不可定向亏格嵌入都是2 一胞腔嵌入如果_ 彳( g ) = 2 7 ( g ) + l ，且 g 不是树，那么g 在不可定向曲面彳( g ) 上，既有2 一胞腔嵌入，也有非2 一 胞腔嵌入 最后，我们介绍图的交叉数的概念 一个图g 在平面上的一个画法( 简称一个平面画法) 是指g 的顶点被 平面的不同的点表示，边被平面的( 直的或曲的) 线段表示图g 的一个好 的平面画法是指满足下列要求的平面画法： ( 1 ) 任何一条边不与自身相交且不经过任何一个顶点， ( 2 ) 与同一个顶点关联的边不相交， 生生塑型塑塾墅塑壁奎堡垒 ：皇： 一一 口 ( 3 ) 任何两条边相交不多于一次， ( 4 ) 多于三条的边不会相交于平面的同一点 如果g 的一个好的平面画法中它的所有交叉点的数目达到最小值，那 么，称这个画法是g 的一个有利的平面画法g 的交叉数是指它的任一个 有利的平面画法的所有交叉点的数目，记为凹( g ) 第二章可定向曲面的极小禁用子 图的构造 在这一章中，我们用六种方式构造可定向曲面的极小禁用子图，这些方 式体现在第二节至第七节中g 1 0 v e r h u n e k e 和w a n g 等人在文献f 2 7 1 中 构造射影平面的1 0 3 个极小禁用子图的时候，先给出5 个图，然后通过顶点 分裂以及删边的方式构造其它的图我们构造可定向曲面的极小禁用子图 的六种方式之一，就是顶点分裂在第四节中，我们通过粘合两个图的两个 顶点的方式来构造可定向曲面的极小禁用子图，其中的定理2 4 3 推广了文 献【1 6 】的推论o 2 作为对a r c h d e a c o n 在文献【4 】中提出的公开问题的探 讨，在第八节中，我们给出了环面上的7 个孓正则的极小禁用子图另外， 在第三节中，我们还构造了可定向曲面的极小禁用图子式 v b l l m e r h a u s 【6 9 】和g l o v e r 2 8 ，p p5 3 】曾猜想可定向曲面上的一个极 小禁用子图与玩和娲，3 有下面的关系：设g 是可定向曲面上的一个 极小禁用子图，则g 可被至多2 夕+ 1 个子图覆盖，其中，每个子图都是蚝 或蚝，3 的一个细分图s i r 赫【5 8 】证明了下面的结果：如果g 是可定向曲面 岛上的一个极小禁用子图，那么g 可被蚝和配，3 的细分图覆盖在这一 章中，我们构造可定向曲面的极小禁用子图的时候，所用的图中有很多就是 蚝和凰3 2 1 一些引理 这一节中，我们给出几个引理它们将在其他章节中被应用先介绍几 个概念琏和蚝，3 统称为库拉托夫斯基( k u r a t o w s k i ) 图由于将蚝的 任意一条边删去后得到的图都是同构的，所以，我们用甄一e 表示蚝删 1 2 第二章可定向曲面的极小禁用子图的构造 去一条边后得到的图，且蚝一e 的每个度为3 的顶点称为它的悬挂点同 样地，将甄3 的任意一条边删去后得到的图也都是同构的，所以，我们用 蚝，3 一e 表示飓，3 删去一条边后的得到的图，且蚝，3 一e 的每个度为2 的顶 点称为它的悬挂点 引理2 1 1设是一个图g 在某个可定向曲面上的一个2 - 胞腔 嵌入，再设c 是的一个面圈，且z l ，沈，铷是c 上按这个顺序出现的三个 顶点设可1 是g 的一个不在c 上且与z 1 ，耽和如都相邻的顶点，再设沈 是g 的一个不在c 上的顶点，且在g 中存在三条两两内部不交的且都与 c 内部不交的路最，恳和b 分别连接沈与z l ，娩，铂令圈g = 可l z l 现l ， q = 1 钇z 3 玑则，a 和q 中一定有一个圈是的一个不可收缩圈 证明：假定a 和q 都是的可收缩圈则，由q ，q 和c 的边作 对称差得到的图是的一个可收缩圈，记为显然，z 2 在c 7 的内部如 果垅在c 的外部，由于在曲面上有一个开圆盘包含和现，而一个开圆 盘同胚于一个平面，由约当曲线定理，恳与c 7 的某条边相交，矛盾如果沈 在c ，的内部，那么p l ，岛和r 都在c 的内部不妨设可2 在a 的内部设 g 7 是由y ( p 1 ) uy ( 岛) uy ( b ) 一 z 。，z 2 ，z 3 所导出的g 的子图然后，将 g 的不在e ( 尸1 ) ue ( 岛) ue ( b ) 中的边全删去在c 的内部，我们可以画 一条曲线连接秒1 和沈，使得它沿可1 2 1 ，再沿p 1 ，到达沈，且不与任何边相交 记日是由e ( c ) u ( u 冬1 e ( g ) ) u ( u ；：l e ( 弓) ) u 秒l 沈) 所导出的子图，则日 同胚于蚝令d 是曲面上包含c 7 及其内部的开圆盘于是，日被画在 d 内且没有交叉点，这与库拉托夫斯基定理矛盾因此，a 和q 中一定有 一个圈是的一个不可收缩圈 由引理2 1 1 ，可直接得到下面的结果 推论2 1 2设是一个图g 在某个可定向曲面上的一个2 胞 腔嵌入，再设z 1 ，。2 ，z 3 ，z 4 和奶是g 的五个顶点，且这五个顶点所导出 的g 的子图q 同构于蚝或蚝一e 如果q 同构于地一e ，那么q 的 两个度为3 的顶点分别为z l 和如令圈g = z 2 2 3 2 4 2 2 ，q = z l z 2 0 3 2 1 ， g = z 。z 3 z 。z 。如果g 是n 的一个面圈，那么g 和g 中一定有一个圈 是的一个不可收缩圈 2 1一些引理1 3 引理2 1 3设是一个图g 在某个可定向曲面& 上的一个2 胞腔 嵌入，再设c 是n 的一个面圈，且z l ，z 2 ，z 3 ，z 4 是c 上按这个顺序出现的 四个顶点设y l 是g 的一个不在c 上且与z 1 和都相邻的顶点，再设沈 是g 的一个不在c 上的顶点，且在g 中存在两条内部不交的且都与c 内 部不交的路只和r 分别连接沈与z 2 ，观令圈a = 可l z l z 2 2 3 可1 则，a 是 的一个不可收缩圈 证明：假定a 是的一个可收缩圈则，由a 和c 的边作对称差 得到的图是的一个可收缩圈，记为显然，z 2 在c 7 的内部如果耽在 的外部，由于在曲面上有一个开圆盘包含c 7 和耽，而一个开圆盘同胚于 一个平面，由约当曲线定理，那么r 与c 7 的某条边相交，矛盾如果珑在 的内部，我们考虑z 4 如果瓤在c 7 的外部，那么易与的某条边相 交，矛盾如果z 4 在c 的内部，那么只和恳都在c 的内部设g 7 是由 y ( 只) uy ( 恳) 一【z 2 ，甄) 所导出的g 的子图将g 7 的不在e ( 只) ue ( 恳) 中的边全删去在的内部，我们可以画一条曲线连接可。和耽，使得它沿 秒1 2 1 以及c 上的z 1 与z 2 之间的片段，再沿r ，到达沈，且不与任何边相 交记日是由e ( e ) ue ( a ) u