（运筹学与控制论专业论文）两类图的亏格分布.pdf

声明 y 8 78 6 5 8 本人郑重声明，本论文的所有研究工作都是在我的导师一刘彦 佩教授的指导下，由本人独立创作完成论文中引用已知的结论 均已列在参考文献中未经本人许可，任何擅自更改、抄袭本论 文之内容的行为，都将承担相应的学术和法律责任 目录 摘要 拓扑学是近代发展起来的高度抽象的一门几何学名称源于希腊语 t 0 p o l o g y 音译而来发展到现代，拓扑学主要研究拓扑空间在拓扑变换 ( 或同胚) 下的不变性质，或者说不变量所谓同胚的空间x 与y 是指 x 与y 之间存在双向连续的对应，形象地说，就是橡皮泥x 在不允许隔 断的情况下可以随意捏成y 经过拓扑变换( 或同胚变换) 之后，长度、 面积、共线性都变了，但是仍有许多不变的东西，例如连通性、维数等 拓扑学正是研究这些不变性质，叫做拓扑性质 图的嵌入理论是拓扑图论中一个重要的研究分支，h i l b c r t 和c o h n v 0 8 s 。n 于十九世纪初曾提出过所谓的引线问题吼在六十年代末由r i n 9 1 0 和y b u n g s 等人解决了在解决这个问题的过程中，引起了对图的嵌入的 研究 嵌入理论主要研究的问题有图的可嵌入性理论和嵌入计数理论图 的可嵌入性理论是判断一个图是否可以嵌入到一个给定的曲面上，可以 应用在电子线路的分析与设计，逻辑电路的分析与故障诊断上；计数理论 主要是对图所能嵌入曲面的亏格分布的范围与该图在这些曲面上的不同 嵌入进行计数，与理论物理、量子力学及统计力学有着密切的关系 本文利用加边法得到两类图的可定向亏格分布一梯图( 已知，但这里 的求取过程较简单) 与蜻蜓眼图；其中，辅以联树理论加以严格论证，使 推理过程更严密 该论文共分为四章： 第一章，结合本文研究课题的背景、发展现状及原有结论，介绍所需 了解的拓扑学与图论基础知识，为读者对第二章与第三章的理解做好铺 t h i st h c s i sg o t s 协eo r i o n t a b l eg e n u sd i s t r i b u t i o n so ft w ok m d so f g r a p h sw i t ht h eh c l po fe d g e - a 饥a c h i n g s u r g c 。yt e c h n i q u 。一c l o s c d c n d l a d d e r s ( k n o w nb e f o r e ，b u th e r eg i v e sa8 i m p l e rs o l u t i o n ) a n dd r a g o n n y - c r a c t c r lo ri n otherw o r d si n v a n a n to ft o p o l o g i c a ls p a c e u h “m ? 0 尊t h k 鼙i _ 珥楚i 措 藩峙疆f誉n#占p 砖魁ib “x j 攫n h 扭& j 嚣盆；_ 鬟l 蛙； n ；鏖鬟x - s 鱼“4 1 l p 一鞋i 矾* “r muggi挚如垂 对、lnq每|嚣g圭u囊捌0囊薷凳钝薛_h1删越qcsqlj可r譬圳i目l耄mer e s u l t so fth e 矗e l d8 b o u tg e n u sd i s t r i b u t i o n ，w ee x p i a i ns o m e ba。8 l cc 。n c o p t l o n sint o p o i o g y8 n dg r a p ht 1 1 r y ，w h i c h w 1 1 lh e l pr e a d e r t ol l n d e r s t a n dt h en e x t chapter8i ne h a p t e r t w o ，wi t h t h e h e l po fe d g c a 土t a c h i n s u r g c r y teehnique，w cg o tt h oo r i e n ta b l eg e n u sd i s t r i b u t i o n 。fc l o s e e n d l a d d o r sb e c a u s e w ca n d aw a yt og e t t h ec o e茁d e n t so fa nc x p a n d t i o no ft h ep o w e r function，w cs h n p l l 矗e dt h epr o b i 。ma n dg a i n e da no x p l i c i tr 。s u l to nt h c s u r f a c e o fg e n u sl ，t h el a d d e r 厶w a ss h 。w nt o have 2 ”州一1 ( 礼一t ) ! ( 2 礼一3 i + 2 ) 1 丽面1 11t o p o l og i c a l l yn o n e q u i v a l e n t embeddingsi nc h a p te rt h r e e ，e v e r yc i r c u l a t i o nn e e d st w oe d g e - a t t a c h i n g s b utt h i st im cw ch a en o tg e t aw a yt og e tt h ec o e 伍c i e n t so fa n cxpandcdtiono ft h cdo w e rf u n c 七i o na n dh e n c eo n l yw i t ha ni m p l i c i t rcsulti nc h a pe rf o u r ，t h et a g ss h o wt h e c h a t a c t e r i s t i c so f edge。attachin哥s u r g c y t e c h n i q u ek e vwor 目录 d i s t r i b u t i o n 第一章图亏格分布的介绍 1 1 研究现状 对于一般图的亏格分布，很少得到结果，在短时间内不可能完全解决 这个问题，但可以选定一类图求它在一定亏格曲面上嵌入的个数先得到 一些基本图类的亏格分布，找出一般的性质，为进一步的研究提供基础 至今为止，对一些特殊图类的研究已经有了进展( 仅限于点状和链 状的图类) ，相继得到了一些图的亏格分布公式 f u r s t 等已经得到 c l o s c d e n dl a d d e r s ( 梯图) 和c 。b b l c s t o n ep 戤h s 两类图的可定向亏格分布 l ；g r o s s 等人利用j a c k s o n 给出的一个计算公式，得到了环束b 。可定向 亏格分布的递推公式 2 】；t e s a r 在2 0 0 0 年得到了r i n g l el a d d e r s 闺1 】和 c o b b l o s t o n cp a t h s 【图2 】的亏格分布 1 1 】；k w a k 和l e 0 给出了环柬 图3 和d l p l e ( 双极图) 旧4 】的亏格分布f 4 6 3 1 9 7 9 年，刘彦佩在图的嵌入表示 的基础上，揭示了联树表示法 8 l ，把原来的拓扑几何问题转化为组合问 题。 第一章图亏格分布的介绍 g 称为节点，和y 上的一个二元关系e v v = ( ，u ) i 地， k u ) 称为边集，它的元素称为边其中( u ，”) = ( u ，“) 有时，( “，“) 以及在f 中重元素也是允许的( u ，u ) 称为环，e 的重元素称为重边若y 中 含有有限个节点，则称g 为有限图，本文所讨论的图只限于有限图记 ”= i y l 被称为g 的阶，e = i e f 为g 的度，g 的顶点的度是指g 中与 该点关联的边的数目，每个环算作两条边 1 3 多面形理论的介绍 在拓扑学中，所说的面就是无边缘的2 一维紧闭流形事实上，可以视 为平面上的一个偶数条边的正多边形，每边分配一个方向且两两成对，将 同一对边依同方向合而为一所得到的( 在合而为一过程中，可以收缩或 伸长，但不能断裂) 闭曲面曲线公理在曲面上的任何一条闭曲线，要么有两侧( 左侧和 右侧) ，要么只有一侧，二者必居其一 有两侧的闭曲线被称为双侧曲线，否则称为单侧曲线 一个曲面，若其上的所有闭曲线全是双侧的，则称它为可定向曲面； 否则为不可定向曲面 一个多面形，令t = 如，6 ，c ，) 为互不相同字母的一个有限集其 中，每个字母n t 用两个方向矿和。一区别记b n = 。，0 4 ) ，q ，卢= + 或一，则 b t = 。t b o 被称为基本集( u 。t b o ，b n n b 6 = 0 ，n 6 ) 这里，b 可以视为一个算 第一章图亏格分布的介绍 1 2 运算( 3 ) 日= ( a 。b 掣口) f 亡= h l = ( a z 。z + ) ，马= ( z b 可卢) f ，o + ，一，z 不属于t 其中，f 和f 。为两个多面形的面集，a 和 b 为带方向角标字母的线性序 以上三种运算确定的是一类拓扑等价，记为一，统称为初等变换 不难验证，初等变换使示性数和可定向性不变由于可迁性和运算3 ， 可导出任何多面形均与一个具有一个面的多面形等价则只需研究单面形 就可以了 已被证明 7 1 】一个单面形是不可定向的，当且仅当存在一个字母两次 出现的方向角标是相同的而一个单面形是可定向的，当且仅当每个字母 两次出现的方向角标不同 对单面形的循环表示，利用恒等变换和初等运算，我们有以下三条规 则： 规则( 1 ) ( a n + b 6 十g 口一d 6 一e ) 一( a d g b e o + b + o 一) 规则( 2 ) ( a + b o + e ) ( 4 b g 。+ o + ) 规则( 3 ) ( a n + 一6 + c + 6 一c 一) 一( a o + 矿6 + 矿c + c + ) 以上这些运算中，集合h ，日，a ，d ，e 均为字母的线性序，可取空集， b 一与算术中一个乘积的取逆规则一致通过反复利用规则( 1 ) ，以及恒等 变换与初等运算，可得 定理1 3 2 对任何一个可定向多面形p ，均存在一个整数p ，p o 俐，使 得 p jn 娶1 ( 。醇i 6 i ) ，p 1 f ( 。+ 。一) ，芦= o 这就是说，可定向多面形只需要用一个整数p ( p o ) ，即确定一个等价 类，我们将p 定义为它的亏格 第一章圈亏格分布的介绍 1 3 定理1 3 3 7 对任何一个不可定向多面形p ，均存在一个整数q ，q 1 使得 口 p n ( o j 。j ) t = 1 同样的，不可定向多面形也只需要一个整数g ，g l ( 不可定向亏格) ，即 确定一个等价类 1 4 嵌入的基本概念 一个无圈的图称为树图的一个支撑树，就是图的一个子图，它本身 是一个树，而且它的阶( 顶点个数) 与图的阶相同图的不在这个树上的 边的数目，称为这个图的b e 垅数，记为卢( g ) 定理1 4 1 【1 0 】任何一个图g = ( v e ) 总可嵌入到亏格至多为眵2 】的 可定向曲面上和亏格至多为口的不可定向曲面上 由图g 的一个支撑树r 连同每条非树边，分割为带相同字母的两边而得 的，被称为g 的联树( 下图为一个图和它的联树9 1 ) 图l 对于图g 的两个嵌入，：g s 和9 ：g r ，如果存在一个方向 保持的同胚映射 ：( s ，( g ) ) 一( f9 ( g ) ) ，使得 ，= g ，则称两嵌入式等 价这里，将图g 在某个睦面上的嵌入数目，视为等价类的数目 第二章梯图的可定向亏格分布 州一“( “i ) s 。c ，= 。a ：一- c 厶一- ，= z ”+ l 一1 ( ? 二) ，。c 厶，= a 。c 厶，+ 是c 厶，= z ”+ i 1 z ( “i i ) + ( ? 二? ) ( i 【孚】) 定理2 0 4 梯圈厶在亏格为i 的曲面上，有 i ! ( n 一2 + 1 ) 个拓扑不等价的嵌入 下表给出对于较小值的n 和 ，9 ( 厶) 的分布情况 3 | g9 09 19 2卯 肌9 5 9 6 00000 如 1 2ooo0o 也 84 01 60 o 00 山 1 61 1 21 2 80000 3 22 8 85 7 61 2 8 0o o 6 47 0 42 0 4 81 2 8 0oo0 3 1 1 2 81 6 6 46 4 0 07 1 6 81 0 2 400 2 5 63 8 4 01 8 4 3 23 0 7 2 0 1 2 2 8 80o 5 1 28 7 0 45 0 1 7 61 1 2 6 4 08 1 9 2 08 1 9 2o o 1 0 2 41 9 4 5 61 3 1 0 7 2 3 7 2 7 3 64 0 9 6 0 01 1 4 6 8 80 1 9 第三章蜻蜒眼图的可定向亏格分布 对于卵石路图p n m 表示卵石路中4 度点的数目，自然r 有n + 1 个圆) ，在每一个圆的对应边上加两个点，并连接它们，就得到了蜻蜓眼图 l 。 图4 图5 图6 2 0 第四章结束语 f u r 8 t 等已经得到c l o s c d c n dl a d d e r s ( 梯图) 和c o b b l c s t o n cp a t h s 两 类图的可定向亏格分布，其中后者就是用加边法求取的，用此法求解前 者有同样简洁的效果但能用加边法求得亏格分布显式的，到目前为止， 就发现这两类图 此方法可用来求解可通过重复加边法构造，但点的度数又受到限制 ( 一般不超过4 ) 的图的亏格分布多项式大多只能得到间接的结果，把问 题都集中到怎样去求复杂函数中z 的任意次幂的系数这也表明，分支 数学很多问题的探讨，有待基础数学的向前发展 最后需要说明的是，关于亏格分布多项式的求解，只能是有限的几种 办法解少数几种图类，对于亏格分布多项式的单峰性猜想还未有实质性进 展 2 4 参考文献 f l im l n r 8 t ，j l g r 0 8 sa n dr s e a t m a n ，g e n u s 曲t r i b u t i o n 8 矗竹t 啪c i a 8 s e so f g r 印h s ，j c o m b i t h e o r y l 4 6 ( 1 9 8 9 ) ，2 2 3 6 f 2 1j l g r o s s ，d p r o b b i sa dt w n c k e r ，g e n u 8d i s t r i b u t i o sf b rb o u q u e t s o fc i r c l e s ，j c o m b i n t h e o r y l 4 7 ( 1 9 8 9 ) ，2 9 2 3 0 6 【3 】h i l b e r t ，d a n dc o h n - v b s s e n ，s ，a n s c l l a u u c h eg e o m a t r i c e ，s p r i n g e r ，1 9 3 2 1 4 j j h k w a ka n djl e e ，g e n u s p o l y n o m i a l s o f d i p o i e s ，k y u n g p o 。k m a t h j ，3 3 ( 1 9 9 3 ) ，儿5 1 2 5 【5 1 j h k w a ka n dj l e e ，e n u m e r a t i o o fg r a p he m b e d d i g s ，d i s c r e t e m a t h ，1 3 5 ( 1 9 9 4 ) ，1 2 9 _ 1 5 1 6 lj h k w a ka n dj l e e ，g t o t a le m b e d 池gd i 8 t 曲u t i o n sf o r b o u q u e t 80 fc i r - c l e s ，d i 8 c r e t em a t h ，2 4 8 ( 2 0 0 2 ) ，9 3 - 1 0 8 7 】刘彦佩，问题与进展( i ) 一数多面形，北京交通大学学报，2 6 ( 2 0 0 2 ) ，6 ：1 7 【8 】刘彦佩，图的不可定向最大亏格【j 1 中国科学，( 1 9 7 9 ) ，数学专辑 i ：1 9 i 一2 0 1 ， 9 】刘彦佩，组合地图进阶 m 】，北京交通大学出版社，( 2 0 0 3 ) 1 2 5 1 0 】刘彦佩，图的可嵌入性理论 m 】，科学出版社，( 1 9 9 4 ) 1 1 je h t e s a r ， g e n u sd b t r i x 参考文献 t i o n s m a c m i l a n l l o n d o n ，( 1 9 7 6 ) 【15 】jc h c n ，t h c d i s t r i t u