（应用数学专业论文）图式流形拓扑分类问题的图论方法.pdf

摘要 摘要 图式流形是一个以无向图g 为框架产生的管形曲面。本文运用图论中的向量空间， 包括圈空间及割空间，研究图式流形的同胚等价类计数问题，一方面简化了群论方法的 证明，另一方面推进了一般的计数结果。给出了一种确定图式流形日一等价类代表系的 方法，称之为“余树法 。任意选定图g 的一个余树于，以于的全体不同构的边导出子 图为黑边子图，所得到的图集就是图式流形的一个日一等价类代表系。 我们运用“余树法讨论了以三棱台为框架的图式流形，绘制了它的割集空间和日一 等价类代表系的全部图形，以及最终得到日一等价类个数是6 。给出了顶点个数不超过 1 1 的轮图睨的日一等价类个数。引入新的编码方法来标记p e t e r s e n 图的h 一等价类的 代表系，得到以p e t e r s e n 图为框架的图式流形m ( g ) 的h 一等价类的个数是6 的新结果。 3 一正则图的研究也是目前比较热门的一个课题，3 一正则图的许多拓扑性质还没有得 到结果。我们运用匹配的概念讨论了以3 一正则图为框架的图式流形的计数问题，给出了 一个构造代表系的有效算法，称其为“匹配法。运用此方法求出了以三棱台、立方体 以及五棱台为框架的图式流形日等价类个数，分别是6 、6 和1 2 。由匹配算法得到了 五棱台的代表系由3 6 个子图构成，经丁一变换以及同构变换后我们得到一个仅有1 2 个 子图构成的代表系，分别绘制了代表系的3 6 个图和横贯的1 2 个图，并进一步给出了此 代表系就是横贯的证明。 在本文最后一章，应用q b a s i c 语言编写计算机程序，实现了机器计算图式流形同 胚分类的计数问题。 关键词：图式流形，同胚等价类，圈空间，割集空间，程序 i i a b s t r a c t t h eg r a p h l i k em a n i f o l d sm ( g ) i sat u b u l a rs u r f a c ew i t ht h ef r a m eo fas i m p l ec o n n e c t e dg r a p hgt h i s p a p e rs t u d i e s t h ee n u m e r a t i o np r o b l e mo fh o m e o m o r p h i ce q u i v a l e n c ec l a s s e so fg r a p h l i k em a n i f o l db ya n a p p r o a c hb a s e do nt h ec y c l es p a c ea n dc u ts p a c ei ng r a p ht h e o r y t h i sa p p r o a c hn o to n l ys i m p l i f i e st h e p r o o f sb a s e do ng r o u pt h e o r y , b u ta l s oi m p r o v e st h ee n u m e r a t i o nr e s u l t s g i v e na m e t h o dt od e t e r m i n et h e r e p r e s e n t a t i v es u b g r a p yo fh e q u i v a l e n c ec l a s s ，ar e p r e s e n t a t i v es y s t e mo fh c l a s s e sc a nb ec o n s t r u c t e db y t a k i n ga l ln o n i s o m o r p h i ce d g e i n d u c e ds u b g r a p h so fc o t r e eo fga st h e b l a c ks u b g r a p h s t h i sa p p r o a c hf o r s o m eg r a p h sw i t hg o o du s a b i l i t y , w ec a l li ta s ”c o t r e es c h e m e ” w eu s e dt h et h e o r yo f “c o t r e es c h e m e ”t od i s c u st h ee n u m e r a t i o np r o b l e mo fh - e q u i v a l e n c ec l a s s e so f t h r e e - p r i s mg r a p h ，g i v et h eg r a p h so fc u ts p a c ea n dh - e q u i v a l e n c ec l a s s e so ft h r e e p r i s mg r a p h b a s e do n t h e s e ，w eg e tt h en u m b e ro fh e q u i v a l e n tc l a s so ft h em ( g ) i s6 f o rt h ew h e e lg r a p y , g i v et h en u m b e ro f h - e q u i v a l e n c ec l a s s e su pt oh a v e12v e r t i c e s a tl a s t ，f o rp e t e r s e ng r a p h ，u pt oh o m e o m o r p h i s m ，t h e r ea r e j u s t6g r a p h l i k em a n i f o l d sw i t hc o n t r a c t i o np e t e r s e ng r a p h i nt h ec o u r s eo fd i s c u s sw eg i v ea n e wc o d i n g m e t h o dt om a r kt h es u b g r a p h so fr e p r e s e n t a t i v es y s t e mo fh - e q u i v a l e n c ec l a s s e s i ti sw e l lk n o w nt h a tt h r e e - r e g u l a rg r a p hi st h ek i n do fg r a p h st h a ti so f t e nb ed i s c u s s e d t h r e e - r e g u l a r g r a p hh a v em a n ys p e c i a lp r o p e r t i e s w e w i l ld i s c u st h ee n u m e r a t i o np r o b l e mo fh o m e o m o r p h i c e q u i v a l e n c ec l a s s e so fg r a p h l i k em a n i f o l dw i t hc o n t r a c t i o nt h r e e - r e g u l a rg r a p h ，a n dw i l lp e r f o r mt h e e n u m e r a t i o nb ya na p p r o a c hb a s e do nt h ed e f i n i t i o no fm a t c h i n gi ng r a p ht h e o r y a na l g o r i t h mn a m e d “m a t c h i n ga l g o r i t h m ”a r eg i v e nf o rc o n s t r u c tt h er e p r e s e n t a t i v es y s t e m a tl a s t ，w eo b t a i nt h en u m b e ro f h e q u i v a l e n tc l a s s e so fg r a p h l i k em a n i f o l dw i t hc o n t r a c t i o no ft h r e e - p r i s mg r a p h ，c u b ea n df i v e - p r i s m i i i g r a p ha r es i x , s i x , a n dt w e l v er e s p e c t i v e l y b yt h e m a t c h i n ga l g o r i t h m ”，w ek n o wt h a tt h en u m b e ro ft h e r e p r e s e n t a t i v es y s t e mo ff i v e p r i s mg r a p hi st h i r t ys e v e n ，a n db ya na u t o m o r p h i s mo ff i v e - p r i s mg r a p h a n d o rs e v e r a lt w i s to p e r a t i o n sw eh a v ean e wr e p r e s e n t a t i v e s y s t e mt h a tc o n g i t u t eo n l yb yt w e l v e c o l o r i n g s w eg i v et h ep r o o ft h a tt h en e wr e p r e s e n t a t i v es y s t e mi se x a c t l yt h et r a n s v e r s eo ff i v e - p d s m g r a p h i nt h i sl a s tc h a p t e r , a p p l i c a t i o nq b a s i cc o m p u t e rp r o g r a mt or e a l i z et h em a c h i n ec a l c u l a t i o nt h e e n u m e r a t i o np r o b l e mo ft h eh o m e o m o r p h i ce q u i v a l e n c ec l a s s e so fg r a p h l i k em a n i f o l d sg r a p h l i k em a n i f o l d s k e yw o r d s ：g r a p h l i k em a n i f o l d ，h o m e o m o r p h i ce q u i v a l e n c ec l a s s e s ，c y c l es p a c e ，c u ts p a c ep l a n e ， p r o g r a m m e i v 目录 摘要i a b s t r a c t i i i 目录。v 第一章绪论l 1 1 基本概念1 1 2 图式流形拓扑分类问题的研究概况。1 1 3 本文的主要研究结果一5 第二章基本理论7 2 1 边导出子图的同构变换一7 2 2 丁一变换9 2 3 丁一等价类的横贯13 2 4h 一变换1 4 第三章图式流形的向量空间方法1 7 3 1 图式流形的等价分类1 7 3 2 图的圈空间与割空间1 9 3 3 计数定理2 0 第四章几类图的计数问题2 3 4 1 三棱台的h 一等价类2 3 4 1 1 割集空间2 3 4 1 2 日一等价类的代表系2 4 4 1 3 日一等价类的横贯2 8 4 2 轮图的日一等价类2 8 4 3 p e t e r s e n 图的日一等价类2 9 4 3 1 日一等价类的代表系2 9 4 3 2h 一等价类的横贯31 第五章对h ai n 图的计数3 5 5 1 关于h ai in 图a 的h 一等价类3 5 5 2 关于h a | - n 图b 的h 一等价类3 6 5 3 关于h al in 图c 的日一等价类3 7 5 4 关于h ai n 图d 的日一等价类3 8 第六章对3 一正则图的计数4 1 6 1 关于h 一等价类计数的匹配法4 1 6 2 运用匹配法讨论图的日一等价类。4 2 6 2 1 三棱台的日一等价分类。4 2 6 2 2 完全二部图的日一等价分类4 3 6 2 3 立方体图的一等价分类4 3 6 2 4 五棱台的日一等价分类4 4 v lv 6 2 5 讨论m o biu s 梯子的日一等价类5 0 第七章运算性质及分解定理5 3 7 1 同胚变换5 3 7 2 割集的分解5 3 7 3 割点的分解5 5 第八章程序设计5 7 参考文献8 5 附录ae 的全体不同构子图8 7 攻读学位期间发表的学术论文目录9 1 致 射9 3 创造性声明。9 5 v i g 的无序对集合( 即e nv = o ，e v xv ) 。y 中的元素称为图g 的顶点，e 中的元素称 为图g 的边，通常用v ( g ) 和e ( g ) 分别表示图g 的顶点集和边集。本文用空心小圆圈表 示图的顶点。若边( “，v ) e ，则在甜和1 ，间连线，并用此连线表示图的边u v ，此时顶点 u 和v 称为相邻的。对图g 的任意顶点“和v ，若存在顶点序列叭吃咋，满足序列中 相邻的顶点在g 中亦是相邻的，则称顶点“和v 是连通的。易知顶点集上的连通关系是 等价关系。若图g 中任何两个顶点都连通，则称g 为连通图。以下讨论的图均为无向简 单连通图。 若简单图g 的每一对不同的顶点均有一条边相关联，称其为完全图，刀阶完全图记 作k 。 图的积运算g l g 2 ，考虑v = k 中的任意两个点“= ( u 1 ”：) 和v = ( v l ，v 2 ) ，当 i = v 1 以及甜2 和吃相邻；或”2 = v 2 以及甜l 和u 相邻时，“和1 l ，在g = g lxg 2 中邻接。 本文所用术语与符号基本上与文献 2 5 一致。本节中未介绍的其它图论术语将在谈 及相关问题时予以阐述。 1 2 图式流形拓扑分类问题的研究概况 流形概念的提出是近代数学的一项重大发现。1 9 7 4 年，j w m o r g a n 和d p s u l l i v a n 在文献 1 中讨论了z ”流形，提出了杯( b o c k s t e i n ) 的概念。1 9 9 4 年，刘亚星和李 起升借助b o c k s t e i n 的概念在文献 2 中引入了图式流形的概念并研究其在同胚分类意 义下的图式流形计数问题。 图式流形拓扑分类问题的图论方法 恻釜罴豢篡嚣u g e 】。借助映射 y 和运算在集合丁( g ) 上导入的运算木，可得到群仃( g ) ，宰) 。并且群( b ，) 与群( 丁( g ) ，) 是同构的，映射缈是二群之间的同构映射。从而得命题2 2 6 。 命题2 2 6 r ( g ) 对运算宰形成群，且群( 丁( g ) ，木) 是群( ，幸) 的子群。 口 引理2 2 1 啪1n 阶连通图g 关于生成树丁的基本割集( 恰好含有r 的一个树枝的 割集称为基本割集) 是线性无关的。 证明：因为图g 的每一个基本割集恰好包含树丁的一条树枝，所以图g 关于r 的 割集的对称差不会是空图。 口 引理2 2 2 幽1图g 的任一边割集均可以表示为若干个基本割集的对称差。 证明：因为任一非空边割集【s ，习至少包含生成树丁的一个树枝，不妨设 s = 气，e i 2 ，气，勺+ i ，气 ，其中气，气，气为树枝。又设含树枝气的边割为墨。 那么瓯墨= 陋，亍】是图g 的边割，且只含树枝气，气，气。于是 i s ，g a s ，亍 不含树枝，与边割定义矛盾，所以其必是空图。故 s ，两= i s ，翮，即 【s ，s = 夏墨，。 口 由以上两个引理，知行阶连通图g 关于树丁的基本割集是图g 的割集空间b 的一组 基，且d i m ( b ) = 万一l ，l b i _ 2 ”1 。 命题2 2 7 刀阶连通图g 的割集空间b 的维数是胛一1 ，阶是2 ”1 。 口 命题2 2 8 门阶连通图g 的边割集子图t ( g ) ，i t ( g ) i - 2 ”1 。 口 定义2 2 4 在上定义丁一变换：v 口，f t ( g ) ，口与f 做一次乘积运算奉，就称 为对口做一次丁一变换。 v ，若j f t ( g ) ，使得q 牛f = ，则称q ，o f 2 是丁一等价的，记为r 口2 。 或者说子图可经丁一变换变成子图。 命题2 2 9r 关系，是上的等价关系。 1 2 对比丁( g ) ，有y z = 口z 成立，即( 口) ，( ) ，；对比r ( g ) ，有口，z = , s z 成立，即( ) ，( 口) ，。于是( ) r = ( 口) ，。 口 命题2 2 1 1 非空集合上的等价关系关系r 把划分为2 “2 ”1 个等价类，其中 ，2 = iy ( g ) i ，m = ie ( g ) i 。 证明： 由命题2 2 6 知( r ( g ) ，幸) 是群( ，掌) 的子群。所以子群( 丁( g ) ，奎) 在群( ，宰) 中 的陪集即的丁等价类，故被划分为2 ”2 ”1 个等价类。 口 因此在子群叮( g ) ，木) 的每个陪集中取一个元，就构成了的全体丁等价类的代表元。 定义2 2 6 丁一等价类的一个“代表系，是指这样的子图集合r ，它至少包含每 一个丁一等价类的一个元素。 2 3 丁一等价类的横贯 定义2 3 ir 一等价类的一个“横贯 ，是指这样的代表系尺+ ，它恰包含每个丁一 等价类的一个元素。 定义2 3 2 啪1 设图g = ( y ，e ) ，满足矿( 日) = y ( g ) ，e ( 日) e ( g ) 的子图称为g 的生 成子图。 图式流形拓扑分类问题的图论方法 定义2 3 3 啪1 若丁是图g 的生成子图且又是一棵树，则称丁是图g 的生成树。树 r 的边称为树枝。树丁关于图g 的补图称为余树，记为于。余树的边称为连枝。 换言之，在图g 中将树r 的边删去，便得到余树于= g e ( t ) 。由于生成树的边数 为疗一l ，所以余树于的边数为l a = m n + l 。由连枝集组成的边导出子图有2 ”肿1 个，包 括空图及余树自身。由于图g 的边割集中必有树枝，所以仅由连枝组成的边导出子图不 是边割集子图，即不属于丁并且这些子图分属于不同的丁等价类。因为两个相异的丁等 价子图至少有一个含有树枝。 命题2 3 1 设图g = ( v ，e ) ，iy ( g ) | _ n 和ie ( g ) i _ m ，及其一个余树于，图g 的丁一 等价类数目等于于中所有边导出子图的数目。同时，于的所有边导出子图，构成丁一等 价类的一个横贯。 证明：由命题2 2 11 知图g 的丁一等价类数目为2 ”2 ”1 。另一方面，于中所有边 导出子图的数目为2 ，其中= m n + l 。因为于的边数是，故它的所有边导出子图 的数目为( ： + ( f + + ( z ) = 2 一。所以命题的第一个结论得证。其次，设e 及岛是余树于 的两个不同的边子集。由于g 一( 5 必) 包含生成树丁，所以它是连通图，从而巨岖不 是边割集。因此，根据定义2 2 3 ，互及易对应的边导出子图q 及c r 2 ( 分别以巨及易为 边子集) 不是丁一等价的。这样一来，由于的所有2 个边导出子图是两两不等价的，从而 它们构成丁一等价类的一个横贯r + 。 口 2 4 h 一变换 定义2 4 1 对图g = ( y ，e ) ，v q ，吃，若j f 丁( g ) ，缈r ( g ) ，使得 呼o ( o q 奉f ) = 哆，则称，吃是日一等价的，记为q 何。 命题2 4 1 非空集合上的日关系是等价关系。 证明：v 口，了囝= v ，v _ 】t ( g ) ，s r ( g ) ，s je ( a 木g ) = 口，所以自反性成立。 下证对称性，v 口l ，口2 ，若j f 丁( g ) ，缈1 1 ( g ) ，s d 缈( 口l 幸f ) - - - - a 2 ，即q o - 1 ( 缈( q 掌f ) ) = 1 4 第二章基本理论 缈- 1 ( ) ，q = 伊- 1 ( 口2 f ) ，所以日。 再证传递性，v ，若j ，r 2 丁( g ) ；缈，少1 1 ( g ) ，s j 伊( 喁木q ) = ， 沙( 口2 幸2 ) = ，贝0 卿( q 宰宰吃) = a 3 。所以了卿= 矽r ( g ) ，q 幸吃= f t ( g ) s j ， 矽( q 幸f ) = 5 3 。故上的日关系是等价关系。 口 定义2 4 2 与子图5 日一等价的全体边导出子图记为位) h = i ，胃5 ) ，称 为5 所在的日一等价类，口称为该等价类的代表元。 日一变换定义是先执行丁一变换后同构变换。由命题2 2 3 知妒以宰f ) = 缈 ) 宰缈( r ) ， 所以由妒( 吼木r ) = 口2 ，得缈( q 幸f ) = 伊( q ) 掌缈p ) = 口2 其中j f 7 = 伊( r ) 且f t ( g ) ，所以 缈( ) 枣f = 5 2 。也就是说丁一变换和同构变换的执行没有次序限制。由此得命题2 4 2 。 命题2 4 2 q h 吃，则j 缈r ( g ) ，f 丁( g ) ，s jf = 缈( q ) 证明： 由定义2 4 1 若q 片，则了伊1 1 ( g ) ，r 丁( g ) ，j 75 1 = 伊( 宰f ) 5 1 = 伊( 口2 事f ) ，? - i ( ) = 幸f ，伊( 5 1 ) * 5 2 = f 口 命题2 4 3 对v 口，子图5 所在的一等价类( 口) = ur ( a ) = u ( 口) r 。 口e ( a ) r口e r ( a ) 证明： v 口，口所在的日、丁一等价类以及同构类分别记为 ) h ， ) r 和( 口) r 。 v ( 口) 胃，3 7 r ( g ) ，f 丁( g ) ，j j5 = 伊( 枣f ) 即：= 伊一1 ( 口) 木缈一1 ( 缈p ) ) = 伊一1 ( 口幸缈( f ) ) u r ( 5 ) 口e ( a ) r = ? - 1 ( 口) 宰f - u ( 口) r 口 图式流形拓扑分类问题的图论方法 1 6 第三章图式流形的向量窄间方法 第三章图式流形的向量空间 在第二章，我们考虑图g 的全体边导出子图组成的集合，在该集合上建立同构变换、 丁一变换以及一变换，详细阐述了每种变换的相关理论及三种变换之间的关联，同构变 换结合丁一变换就是h 变换。以图g 为框架的图式流形m ( g ) 的同胚分类问题就转化为 求在日一变换下图g 的全体边导出子图的等价分类计数问题。 众所周知，图的计数理论分为两大部分：标定图的计数与非标定图的计数。一般地 说，前者较易，后者较难( 因为涉及同构判定) 。在丁一变换下对图g 的全体边导出子图 的等价分类问题属于标定图的计数问题，而在日一变换下对图g 的全体边导出子图的等 价分类计数问题就是非标定图的计数。文献 2 1 运用群论方法，推导出标定图的计数公 式及相关结果。本文运用图论中的向量空间，包括圈空间及割空间，建立基本的计数方 法。这一方面简化了群论方法的证明，另一方面更深入地揭示出同胚分类与圈结构的关 系。关于图的向量空间及其它图论术语参见 2 4 ，2 5 。 3 1 图式流形的等价分类 文献 2 1 ，2 2 将此问题转化为图g = ( y ，e ) 的着色计数问题。图g 的一个2 一边着色 是指边集e 的一个划分盯= ( 晶，磊) ，其中g o 的边染成白色，表示正边；置的边染成黑 色，表示负边。如图3 1 中的粗线表示黑边，细线表示白边。若对顶点h 执行一次扭转 变换，则关联于，的白( 正) 边变为黑( 负) 边，黑( 负) 边变为白( 正) 边。2 一边着色盯经扭 转顶点m 后变为2 一边着色盯。 由着色盯的黑边导出的子图记为g 1 ，由着色仃的黑边导出的子图记为g 2 。对顶点h 执行一次扭转变换相当于对子图g l 执行丁一变换，g l 幸f = g 2 ( 其中f 是边割集子图，运 算宰见定义2 2 1 ) 。 1 7 图式流形拓扑分类问题的图论方法 露融 毒k 2 l 边导出子图g l 边割集子图r 边导出了图g ； 图3 1 扭转变换( 乘积运算) 不总图 给定无向连通图g = ( y ，e ) ，其中v = h ，屹，以 ，e = p 。，e 2 ，) 。所谓标定图， 是指所有顶点m 及边e ，均有标号( 可以区别) 。对此，我们只考虑在丁一变换( 见定义 2 2 4 ) 下的等价类，称为丁一等价类。所谓非标定图，是指顶点及边均无标号( 不可区 别) ；图g 经过一个自同构变换仍然得到同一个图g 。在这种情况下，要考虑在丁一变换 及自同构变换作用( 两种变换的结合即日一变换) 下的等价类，称之为h 一等价类( 即图 式流形的同胚等价类) 。 对图g 的边导出子图仃，我们不再另给图形，而以粗线表示盯的边集巨( 仃) ( 这样 与着色概念也达成一致) 。由置( 盯) 导出的子图仍记为仃，也可称其为黑边子图。 图g 的两个黑边子图仃与盯7 ，若存在g 的自同构妒，使得缈( 盯) = 仃7 ，则称黑边子 图盯及盯是同构的，记为盯兰盯。 图g 的两个黑边子图仃及盯，若存在边割集子图f 丁( g ) ，使得盯木f = 盯7 ，则两个 黑边子图o r 与盯是丁一等价的，记为盯7 盯； 若盯可经过若干个丁一变换及自同构变换后变为盯，则称两个黑边子图仃与仃是 日一等价的，记为仃仃1 7 。 图g 的形如 s ，可】= u v eu s ，v s 一) 的边子集称为g 的边割集( 余圈) ，其中 国scv j = v s 囝。图g 中所有边割集的全体记为b ，称为割空间。这里约定b 包 括空集( 作为线性空间的单位元) 。若一个子图仃的边集是一个边割集，e 1 p ) = 蹬，习， 则称盯为“边割集子图”。一切边割集子图的集合记为t ( g ) = 盯ie l ( 盯) b ) 。 引理3 1 1 子图盯与盯7 是丁一等价的当且仅当存在一个边割集子图r r ( g 1 ，使 得盯= 盯木f 。子图盯与盯是h 一等价的当且仅当存在边割集子图f r ( 0 1 ，使得 盯兰盯幸r 。口 事实上，若f 对应的边割集为巨( f ) = 【s ，司，则在丁一等价的情形下，e ( 盯) = 巨p ) 1 8 第三章图式流形的向量窄间方法 【s ，习，即巨( 仃盯) = 【s ，习。这里s 就是执行扭转变换的顶点集。 定理3 1 1 判定子图的丁一等价性具有多项式时间算法( 好算法) 。 证明： 根据引理3 1 1 ，判定子图盯与盯是否丁一等价，等价于判定巨( 仃) 屿( 盯) 是否图g 的边割集。而要判定一个边子集e 是否g 的边割集，首先看g e 7 是否连通。 若g e 连通，则e 不是分离集，因而不是边割集；否则e 7 是分离集。然后检验分离 集e 是否边割集( 即能否表示为陋，习的形式) 。为此，可将g e 的每一个连通分支收 缩为一个顶点，再判定所得的图是否二部图。如果它是二部图，则将两部顶点构成划分 ( s ，i ) ，e 就表示为的 s ，习形式，从而e 是边割集；否则不是。在上述步骤中，判定 连通性及二部性，均可采用图搜索算法b f s 或d f s ，在多项式时间( 至多d 伽) 时间) 完成。 故结论成立。 口 然而，判定日一等价性是一个困难问题，因为它归结为判定两个图g 】( 仃) 与g 】p ) 是 否同构，而图的同构问题是著名的未解问题( 猜想它既不是多项式可解，也不是n p 一完 全的) 。因此，对一般图的同胚分类( 日一等价类) 不太可能存在有效算法。我们的目标 只能是研究一些特殊图类，或n 较小的情形。有时候可以运用同构的必要条件( 如度序 列相同) ，判定两个图不同构。当 较小时，可以借助于直观判断，构造同构映射。 总之，我们明确了两种等价性的不同特征。下面就来讨论如何确定图g 的丁一等价 类数目r ( g ) 及h 一等价类数目r ( g ) 。文献 2 2 2 已取得一系列成果。本文提出一种 新的观点，运用图的圈空间与割空间，探讨图式流形的等价分类，以便推进已有的工作。 3 2 图的圈空间与割空间 对标定图g ，它的m 条边e l ，e 2 ，e r a 可以排成一个序列。因此一个子图仃可以用一 个m 维( o ，1 ) 向量矗= ( 而，而，) 表示，其中 影彩霎鬈： 这里k 称为边集巨p ) 的关联向量。 设是所有子图的全体，则对应于一个m 维向量空间 0 ，1 ”。我们往往对子图矿及 其关联向量不加区别。所以认为就是这个m 维向量空间。显然i i _ 2 册。特别要注 1 9 图式流形拓扑分类问题的图论方法 意的是，这里向量空间是定义在二元域z 2 = 0 ，1 ) 之上的。边集的对称差运算恰好对应于 关联向量的模2 运算。若子图仃及盯对应的( 0 ，1 ) 向量分别为 = ( 葺，x ：，) 及，= ( 爿，) ， 则盯宰盯对应的关联向量为= ( 而+ 而，而+ 吃7 ，+ ) ( m o d 2 ) 。 这是 e , ( c r * o - ) = e ( 盯) 蝎( 一) 的等价写法。 图g 的所有边割集构成割空间b 。其中每一个割集b b 对应于一个正则着色 f 7 ( g ) ，而一个边割集子图f 对应于一个m 维关联向量。并且边割集对于对称差运 算是封闭的。所以b 就是m 维空间的子空间( 包括零向量( 0 ，0 ，0 ) ) 。另一方面，割 空间b 的正交补空间是圈空间c ，它由零向量及圈向量组成( 圈向量是若干个边不交的 圈的关联向量) 。在图论中，已知b 的维数是刀一l ，ib | _ 2 ”1 ；c 的维数是m n + l ， c | _ 2 ”肿1 。其中y = 刀一1 称为图g 的秩，a = m n + l 称为图g 的余秩( 或圈秩) ，即独 立圈的数目( 参见 2 3 ，2 4 ，2 5 ) 。有了这些图论知识，我们可以建立如下的计数方法。 3 3 计数定理 下面是文献 2 2 提出的的定理，我们用图论方法给出证明。这样一来，得到了与 2 2 中一致的结果。不仅如此，图论方法可以揭示出更多的结构性质。 定理3 3 1 蚴对任意n 个顶点及聊条边的连通图g ，流形m ( g ) 的丁一等价类数目 为坼( g ) 爿ci _ 2 ”肿1 。 证明：根据引理3 1 1 ，每一个子图仃，它所在的等价类( 轨道) 为 盯木fif 丁( g ) ) 。而这个等价类包含的子图数目为i7 ( g ) i = | b | _ 2 ”1 。这就是说，每一个 子图仃都与2 ”1 个子图等价。所以中的丁一等价类个数为坼( g ) 刊i i b i = ici - 2 ”肿1 。口 若求出丁一等价类的一个横贯r + ，则坼( g ) = | r + i 。同理，若求出h 一等价类的一个横 贯尺，则( g ) = ir i 。由此得到确定坼( g ) 及( g ) 的一般方法。 对图g 的一个支撑树丁，树丁关于图g 的补图称为余树，记为于。换言之，在图g 中 2 0 第三章图式流形的向量空间方法 将树丁的边删去，便得到余树于= g e ( 7 ) 。由于支撑树的边数为疗一1 ，所以余树于的边 数为= 朋一n + l 。对余树的每一条边p ，t + e 的唯一圈称为g 的基本圈；所有这些基本 圈构成圈空间c 的基。因此圈空间c 的维数是= 所一n + l 。对偶地有基本余圈( 基本边割 集) 的定义；所有基本余圈构成割空间b 的基( 详见 2 4 ，2 5 ) 。运用余树的概念，我们建立 如下的基本计数定理： 定理3 3 2 伫力对任意连通图g 及其一个余树于，坼( g ) 等于于中所有边导出子图 的数目。同时，以于的所有边导出子图为黑边子图，构成丁一等价类的一个横贯。 证明： 根据定理3 3 1 ，坼( g ) = 2 ，其中= 1 7 1 一n + l 。另一方面，于的边数也是 1 , 故它的所有边导出子图的数目为( ： + ( f ) + - - + ( ： = 2 。所以定理的第一个结论得证。 其次，设巨及岛是余树于的两个不同的边子集。由于g 一( 臣蝇) 包含支撑树t ，所以 它是连通图，从而巨最不是边割集。因此，根据引理3 i 1 ，置及易对应的2 一边子图 q 及c r 2 ( 分别以臣及易为黑边子集) 不是丁一等价的。这样一来，由于的所有2 个边导 出子图对应的子图是两两不等价的，从而它们构成丁一等价类的一个横贯r + 且 坼( g ) 爿r i 。 口 对日一等价类的情形，由于涉及困难的同构变换，不能得到这样完整的结果。类似 的方法只能得到( g ) 的一个上界。 定理3 3 3 乜力对任意连通图g 及其一个余树于，设s ( 7 ) 表示于中所有不同构的边 导出子图的数目，则n h ( g ) s ( 于) 。同时，以于中所有不同构的边导出子图为黑边子图， 构成h 一等价类的一个代表系。 证明： 根据定理3 3 2 ，于的所有边导出子图对应的子图，构成丁一等价类的横贯， 因而也是日一等价类的代表系。注意到这些子图均不r 一等价，但可能同构( 并且经过同 构变换之后还可能是丁一等价的) 。因此剔除同构的子图之后，得到于中所有不同构的边 导出子图，仍然是一等价类的代表系，于是( g ) s ( 于) 。 口 2 l 图式流形拓扑分类问题的图论方法 关于上述定理的一个注释：定理中的s ( t ) ，表示于中所有不同构的边导出子图的数 目。这里所说的不同构，是指于的子图作为图g 的子图是不同构的( 不存在g 的自同构 使一个变为另一个) 。考查图g 的日一等价类代表系中的元素，若存在经过r 一变换后同 构的黑边子图，则删去其中一个，两两验证所有元素后，得到图g 的h 一等价类的横贯。 此定理提供的上界，对某些特殊图而言，是紧的( 即等号成立) ；同时，所述的代 表系就是横贯。而对另外一些图而言，这样的代表系比较小，只要删去少量的等价子图， 便得欲求的横贯。 4 。1 三棱台 在本小节，我们依据图式流形拓扑分类的概念以及r 一等价与日一等价的关系，给出 三棱台日一等价类的详细求解过程。得出三棱台的日一等价类个数是6 ，并绘制三棱台的 h 一等价类代表系及代表元所在的丁一等价类。 4 1 1 割集空间 设图g 的顶点集y ( g ) = “，v 2 ， 。以图g 边割集 s ，习，s 的阶isi 将丁( g ) 分为 n 2 类( 边割集【s ，可】= 歹，跚，当isi n 2 ，存在边割 歹，s 】= i s ，两，is i n 2 ) 。 当is | _ 1 时，即由一个顶点咋确定的边割集导出的子图，基本边割集子图。子图的 顶点集是z ( g ) ，边集由顶点心关联的边组成。共有疗个基本边割集子图，分别记为 q = g m ， 屹，码，) 】，c r 2 = g v 2 ， m ，b ，屹 】，吒= g 【， m ，v 2 ，屹一。) 】。 当i s i - 2 时，将第一类中的子图两两做乘积运算得到第二类。q ：= q 吼= g m ，v 2 ) ， m ，屹) 】 ，q 3 = q 幸吧，q 。= o i 木吒；3 = 吼吧，c r 2 。= c r 2 宰吒； 吒圳12 吒一1 书吒。 直到i s | - n 2 】时，若即是奇数，则继续上述过程。对于忉2 卜1 类中的每个边割集 子图气岛伽h ，构造子图一驴伽2 气f 2 班h 吒，k2 栊卜i + 1 ，栊】一l + 2 ，胛；若刀是偶数， 只需考虑 n 2 一1 类中这样的边割集子图，含有顶点m 的边割集导出的子图。即 盯垤，砘一2q 岛眚胁卜i 毒吒，k2 。2 1 一l + 1 ，2 1 一l + 2 ，刀。 按照上述操作构造三棱台的割集空间，共有1 + q + 暖+ 2 = 3 2 个，如图4 1 所 示。我们以图g 顶点的下标号来标记边割集子图，例如标号2 5 表示子图 图式流形拓扑分类问题的图论方法 0 2 ，= g 【 v 2 ，v 5 ) ， 吃，屹) 】 。 0 1 2 a 3 4 a 5 6 公1 2 1 3 a a a ，。 a a a 2 6 1 3 4a1 3 5a1 3 6 1 4 5 1 4 6 1 5 6 l p 4 1 2 日一等价类的代表系 选择三棱台图g 的一个“梳子树”为支撑树丁，则其余树于= kuc 3 有一个- _ - n 及 一条孤立边组成。则以于中所有不同构的边导出子图( 相对于图g 的) 为黑边子图，可 以得到一个日等价类的代表系。已知c 3 有4 个不同构的边导出子图，与孤立边k 2 组合 起来，可以得到较多的不同构子图。 子图的编码： 下面我们给这些子图一个编码嘶钐，其中口表示是否包含孤立边局；表示包含c 3 中的边数；y 表示边数给定的第几个子图。例如下面的前4 个图( 首位为0 ) 为c 3 的4 个不同构子图，后面6 个图( 首位为1 ) 为包含孤立边墨的不同构子图。由1 - ( g ) 可知 1 0 1 与0 1 1 同构。在孤立边k 的边给定时，g 的自同构不能包含旋转，只有对称翻转。 因此，在口= 1 ( k 为黑边) 及= 1 ( c 3 中一条黑边) 的条件下，由两个不同的旋转得 到 等 1 1 01 2 a