（运筹学与控制论专业论文）半弧传递图与整数流的研究.pdf

北京交通大学博士学位论文中文摘要 中文摘要 摘要：本文的主要内窖分为两部分，前半部分是对4 度半弧传递图的研究，后 半部分是对整数流的研究这两部分内容都与群论有密切的关系半弧传递图与 整数流理论这两个研究课题同为国际著名数学家t u t t e ( 英国皇家学会会员) 所开 创 第一章引言中我们系统地介绍了群与图之问的联系详细的描述了争弧传递 图( 尤其是半弧传递图) 的概念及研究进展接下来我们对整数流的概念、问题的 由来，著名的三大猜想以及一些已知的结论进行简单的阐述 半弧传递图的研究是由t u t t e 在1 9 6 6 年提出的，从此，4 度半弧传递图的 构造和刻画成为代数图论的一个活跃分支4 度半弧传递图方面的内容主要是借 助群论的一些知识来构造半弧传递图并在某些条件下，给出4 度半弧传递图的分 类这一部分内容主要集中在第二章至第四章 第二章主要构造了一类4 虔半弧传递图本章的主要内容是把覆盖的理论作 为工具，研究亿a 的正则覆盖，并构造出一类无限族的4 度半弧传递图这类半 弧传递图的半径为偶数且紧相关，它们不属于前人构造的任何_ 类4 度半弧传递 图 第三章给出了当保纤维自同构群包含一个半弧传递子群而且覆盖变换群为素 数幂阶循环群时，托4 的4 度半弧传递正则覆盖的分类通过这种分类，我们构 造了两类无限族的4 度半弧传递图，它们是目前已知仅有的2 幂阶4 度半传递图 无限类 第四章给出了4 p 阶4 度半弧传递图的分类，同时，我们还证明：4 p 阶半弧 传递图一定不是c a y l e y 图 后五章主要围绕整数流理论，确切地说围绕t u t t e 的3 - 流猜想展开研究 t u t t e 3 - 流猜想已有五十多年历史，至今没有解决本文考虑满足某些条件的三大 类图，证明3 _ 流猜想对这三类圈成立 第五章给出了三角连通图的流存在性以及z 3 一流可收缩性的完全刻画三 角连通图是任意两条边均有连续的三角形相连的一类图有了这个完全刻画的结 果，很多已知结果的证明都可以大大简化 第六章刻画了在o r e - 条件下3 一流的存在性，除了六个特殊的图外，其它的 图在o r e - 条件下都能保证3 流的存在性 u 北京交通大学博士学位论文中文摘要 第七章则是应用第五章的成果来研究度数和与3 - 流存在性以及z 3 一流可收 缩性的关系，并且得到一个图的每条边的两个端点度数和不小于顶点数时3 一流存 在的一个充要条件当上面条件中的顶点数改为顶点数如2 时这个条件则是保证 z 3 一流可收缩性的一个充要条件( 心除。 第八章应用同样的方法研究最小度与3 - 流存在性的关系事实上，从第七章 的结论就可知如果一个图的最小度不小于顶点数的一半时，除了个别图外，都存在 非零譬流这里我们减弱了对最小度的要求，允许有两个点的度数小于顶点数的 一半除了八个小阶数的图之外，所有满足这一弱条件的图都有非零3 - 流。 关键词：半弧传递图；正则覆盖；非零3 - 流；三角连通；t u t t e3 - 流猜想 分类号：0 1 5 7 ，5 北京交通大学博士学位论文英文摘要 a b s t r a c t a b s t r a c t ：i nt h i st h e s i s ，w ec o n c e n t r a t eo nt w os u b j e c t sr e l a t i n gt og r o u p t h e o r y ：t e t r a v a l e n th a l f - a x c - t m u s i t i v eg r a p h sa n di n t e g e rf l o w si ng r a p h s t h e s e t w of i e l d sa r ea l li n i t i a t e db yt h ef a m o u sm a t h e m a t i c i a n - t a t t e ( t h er e e l n b e ro f r o y a ls o c i e t y ) i nt h ef i r s tc h a p t e r ，w ei n t r o d u c es o i y i ed e f i n i t i o n so fg r o u pt h e o r yr e l a t e d t og r a p h s a n dg i v eab r i e fi n t r o d u c t i o nt ot h er e s e a r c ho f8 a r c - t r a n s i t i v eg r a p h s ( e s p e c i a l l y , h a l f - a r c - t r a n s i t i v eg r a p h s ) ，t h e nw eg i v ea ni n t r o d u c t i o nt oi n t e g e r f l o w s ，a n dp r e s e n ts o m ee l e m e n t a r yp r o p e r t i e so fi n t e g e rf l o w s ，t o g e t h e rw i t hs o m e k n o w nr e s u l t sr e l a t e dt ot h ef a m o n sf l o wc o n j e c t u r e so ft u t t e t h ei n v e s t i g a t i o no fh a l f - a r c - t r a n s i t i v e 盯a p h sw a si n i t i a t e db yt u t t ei n1 9 6 6 s i n c et h e n ，c o n s t r u c t i n ga n dc h a r a c t e r i z i n gt e t r a v a l e n th a l f - a r c - t r a n s i t i v eg r a p h s h a sb e e na l la c t i v et o p i ci na l g e b r a i cg r a p ht h e o r y i nt h en e x tt r e ec h a p t e r s ， w i t ht o o l sf r o mg r o u pt h e o r y , w ec o n s t r u c ts o m ei n f i n i t ef a m i l i e so ft e t r a v a t e n t h a l f - a r c - t r a n s i t i v eg r a p h s ，a n du n d e rc e r t a i nc o n d i t i o n s ，c h a r a c t e r i z et e t r a v a l e n t h a l f - a r c - t r a n s i t i v e ；r 印1 1 8 t nt h es e c o n dc h a p t e r b yu s i n gc o v e r i n gt h e o r y , w ec o n s t r u c ta ni n f i n i t ef a m i l y o ft e t r a v a l e n th a l f - a r c t r a n s i t i v eg r a p h s ，w h i c ha r er e g u l a rc o v e r i n g so f t h ec o m p l e t e b i p a r t i t eg r a p h 甄4 m o r e o v e r ，t h e s eg r 印h sa r et i g h t l ya t t a c h e dw i t he v e nr a d i u s a n dd on o tb e l o n gt oa n yp r e v i o u s l yk n o w nf a m i h e so fh a l f - a r c - t r a n s i t i v eg r a p h s i nt h et h i r dc h a p t e r ，w ec m s s i f yt h ec o n n e c t e dh a l f - a r c - t r a n s i t i v er e g u l a rc o y - e r i n g so ft h ec o m p l e t eb i p a r t i t eg r a p hk 4 4 ，i nw h i c ht h ec o v e r i n gt r a n s f o r m a t i o n g r o u pi sc y c l i co fp r i m e - p o w e ro r d e ra n dt h ef i b r e - p r e s e r v i n gg r o u pc o n t a i n s a h a l f - a r c - t r a n s i t i v es u b g r o u p a sar e s u l t ，w eo b t a i nt w on e wi n f i n i t ef a m i l i e so f t e t r a v a l e n th a l f - a r c t r a n s i t i v eg r a p h so f2 - p o w e ro r d e r s ，t h e s ea r et h ef i r s tk n o w n s u c hg r a p h so f2 一p o w e ro r d e r s ，i nw h i c ht h es m a l l e s to n eh a so r d e r2 7 f u r t h e r m o r e ， t h e s eg r a p h sa r ea l s ot i g h t l ya t t a c h e dw i t hc v e nr a d i u s i nt h ef o r t hc h a p t e r ，w ef i n i s ht h ec l a s s i f i c a t i o no ft h et e t r a v a l e n th a l f - a r c t r a n s i t i v eg r a p h so fo r d e r4 p f u r t h e r m o r e ，i ti ss h o w nt h a tah a l f - a r c - t r a n s i t i v e g r a p ho fo r d e r4 pc a b o tb eac a y l e yg r a p h ， t h el a s tf i v ec h a p t e r sa r ed e v o t e dt ot h es t u d yo fi n t e g e rf l o w s ，m o r ep r e c i s e l y , 北京交通大学博士学位论文英文摘要 t ot h ee x i s t e n c eo fn o w h e r e - z e r o3 - f l o w si ns o i n ec l a s s e so fg r a p h s t u t t c s3 - f l o w c o n j e c t u r ei ss t i l lo p e na n db e l i e v e dt ob ev e r yd i f f i c u l t ，w es h m lf o c u so i lt u t t e s 3 - f l o wc o n j e c t u r ef o rs o m eg r a p h st h a ts a t i s f yc e r t a i nc o n d i t i o n s i nt h ef i f t hc h a p t e r ，w ec o m p l e t e l yc h a r a c t e r i z et h et r i a n g u l a r l yc o n n e c t e d g r a p h sw h i c ha r ez 3 一f l o wc o n t r a c t i b l eo rh a v ean o w h e r e - z e r o3 - f l o w w i t ht h e s e c h a r a c t e r i z a t i o n s ，w es i n l p l i f yt h ep r o o f so fs e v e r a lk n o w nr e s u l t s i tw a se o n j e c - t u r e dt h a ta4 - e d g e - c o n n e c t e dg r a p hw i t he v e r ye d g ei nat r i a n g l eh a san o w h e r e z e r o3 - f l o w o u rr e s u l ti sas i g n i f i c a n ts t e pt o w a r d sap r o o fo ft h ec o n j e c t u r e i nt h es i x t hc h a p t e r ，w es h o wt h a tw i t hs i xe x c e p t i o n s ，a l lt h eg r a p h so nn v e r t i c e s ，i nw h i c hd 0 ) + d ( y ) 2 礼f o re v e r yp a i ro fn o n a d j a c e n tv e r t i c e sza n dy ， h a v ean o w h e r e - z e r o3 - f l o w i nt h es e v e n t hc h a p t e r ，w ep r o v et h a tw i t hc o m p l e t e l yd e s c r i b e de x c e p t i o n s ， a l lt h eg r a p h so nn v e r t i c e s ，i nw h i c hd ( z ) + d ( y ) 2n f o re v e r ye d g ex y ，h a v ea n o w h e r e ，b e r o3 - f l o w w ea l s os t u d yt h ez s - f l o wc o n t r a e t i b i l i t y , a n dp r o v et h a ti f g i sa g r a p h o nnv e r t i c e s ，i n w h i c hd ( x ) + d ( v ) n + 2 f o re v e r ye d g ex y ，t h e n g i sz a - f l o wc o n t r a c t i b l e ，u n l e s sgi sk 4 i nt h ee i g h t hc h a p t e r ，w ec o n t i n u eo t l rs t u d yo ft h ec o n n e c t i o nb e t w e e nt h e d e g r e e so fag r a p ha n dt h ee x i s t e n c eo fn o w h e r e - z e r o3 - f l o w s ，b yr e f i n i n gp r e v i o u s a r g u m e n t s w er e l a xt h ed e g r e er e q u i r e m e n t st oa l l o wa tm o s tt w ov e r t i c e si nt h e g r a p ht oh a v es m a l ld e g r e e s k e y w o r d s ：h a l f - a r c - t r a n s i t i v eg r a p h s ；r e g u l a rc o v e r i n g ；n o w h e r e - z e r o3 - f l o w s ； t r i a n g u l a r l yc o n n e c t e d ；t u t t e s3 - f l o wc o n j e c t u r e c l a s s n o ：0 1 5 7 5 v 致谢 本论文的工作是在我的导师冯衍全教授和范更华教授的悉心指导下完成的， 冯衍全教授严谨的治学态度和科学的工作方法给了我极大的帮助和影响，而范更 华教授深厚的数学功底以及不乏幽默的讨论方式使我终生受益另外，冯老师和 范老师在生活上也都给予我无微不至的关怀在此衷心感谢三年来他们对我的关 心和指导 刘彦佩教授、常彦勋教授、修乃华教授以及郝荣霞教授对于我的科研工作和 论文都提出了许多的宝贵意见，在此表示衷心的感谢 特别要感谢福州大学离散数学中心的全体老师，我在福州大学期间，他们的 支持和帮助使我能安心地完成我的论文在此向他们表示感谢 在撰写论文期间，许燕、杨艳，刘文忠、孔令臣、周进鑫，王俊玲以及林海燕 等同学对我论文中的一些研究工作给予了热情帮助，在此向他们表达我的感激之 情。 另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业 v ( x ) e ( x ) a u t ( x ) a i a 2 ，至少存在一个k 度半弧传递图( 2 度正则图是若干个 圈的并，当然由点传递性和边传递性可推出弧传递性，即半弧传递图的最小度数 为4 ) 最小阶半弧传递图是一个有2 7 个点的4 正则图，它是h o l t 在1 9 8 1 年给 出的近年来，人们在构造半弧传递图方面做了大量的工作，采用的方法也多种 多样，这里我们不一一阐述半弧传递图的研究现在已经是代数图论的一个重要 研究领域，现如今，在半弧传递图的研究中有四个主要的研究领域第一个是研 究具有大阶数的点稳定化子的4 度半弧传递图，这方面的研究开始于m a r u g i e 和 n e d e l a 5 5 ，其中一些问题已经被m a r u g i e 5 1 1 部分地解决了，还有一些问题至今 还没有解决第二个是研究半弧传递图的本原作用或者非本原作用，见【6 9 】，以及 李，路和m a r u i 6 的近期的文章( 3 7 j ，第三个方面是研究与半弧传递图相关的一 些几何问题，这一问题在 1 l 】和 5 4 】中有详细的描述第四个方面的研究是有关 交错圈的相关性问题，可见m a r u i e 4 9 令x 是一个4 度( g ，j ) - 传递图考虑g 在v ( x ) v ( x ) 上的自然作用， x 的弧集就成为两个g - 轨道的并，设这两个轨道分别是a l 和a 2 ，而且这两个轨 道是成对出现的，也就是说a 2 = ( ，) i ( 札，u ) a 1 ) 每一个轨道分别对应一个 有向图，设为( 矿( x ) ，a i ) 和( 矿噬) ，a 2 ) ，则这两个有向图的出度和入度分别等于 2 ，雨且g 在这两个有向图上是点传递和弧传递的。不难看出，x 是( 矿( x ) ，a i ) 和( y ( x ) ，a 2 ) 的基础图假设d a ( x ) 是这两个有向图之一，从现在开始把这个 有向图固定下来假设u v ( x ) 并且( “：口) 是d a ( x ) 中的一条弧，我们称 u 和 分别是( ，口) 的尾和头，设g 是x 中的一个偶圈，如果g 中的每个点 都分别成为与它相关联的两条弧的头和尾( 在o a ( x ) 中) 且成为头与成为尾的点 在g 上依次相互交错，则g 称为g - 交错圈在 4 9 ，命题2 4 0 ) 】中已经证明了 x 中的所有g - 交错圈有相同的长度，而且构成了对x 的边集合的一个划分 g 交错圈长度的一半被称为x 的g 一半径，记作t o ( x ) 如果两个交错圈至少有 一个公共顶点，我们称这两个交错圈是相邻的另外在( 4 9 ，命题2 6 】中还证明了 x 中任意两个相邻的交错圈相交( 重合) 的顶点数都相同，相交的顶点数称为x 的g 一相关数，记作a o ( x ) 进一步，g - 相关数a a ( x ) 能够整除2 r a ( x ) 如果 r a ( x ) = 眈( x ) ，则我口7 称此g 是紧相关的在f 4 9 7 当中。所有的紧相关的丽且 d 半径是奇数的( g ， ) 一传递图的分类已经完成，更进一步，在这些图当中哪些 是 一弧传递的以及哪些是弧传递的也都已经给出了分类关于所有的紧相关的而 且g - 半径是偶数的( g ， ) 一传递图在 57 】中也给出了分类但是，这些图当中哪 4 北京交通大学博士学位论文 些是j 1 一弧传递的却还没有解决令x 是一个 一弧传递图，a u t ( x ) - 交错圈、 a u t ( x ) 一半径以及a u t ( x ) 相关数我们简单地称为x 的交错圈、x 的半径以及 x 的相关数类似地，如果x 是紧a u t ( x ) 一相关的，则我们称x 是紧相关的 接下来的三章，我们将重点讨论4 度半弧传递图在讨论过程中，我们要 用到一个工具，那就是块图( 商图) ，在证明一个图是否是半弧传递图时，引用商 图就会使问题大大简化。有了以上介绍的群和图的基本知识，我们来定义块图或 商图设x 是g - 对称图，并设g 在v = v ( x ) 上的作用是非本原的又设 肟= b 1 ，b 2 ，占乙) 是g 的一个非平凡完全块系如下规定的图x 称为x 关 于口的块图或者商图； v ( - z ) = 口， e ( 叉) = “& ，马) i 存在q 最，巧易使得 嘶， e ( x ) ) 其实块图的度数可以大于、等于或小于原图的度数而对于两个相邻的块，并菲由 一个块的任意一点都有边连到另外一个块的某一点如果考虑群g 在完全块系的 作用的核，那么在某一块b 上的作用可以是传递的，也可以是不传递的， 还可以是平凡的，即k = 1 由此可见，块图与原图之间关系是非常复杂的因 此，为决定非本原对称图，先决定它的块图( 块图具有较小的阶) ，然后再由块图和 原图的关系决定原图的路线并非总可行但是如果g 在嚣上的作用的核在每一 块b 8 上的作用是传递的，这时情况可能要简单的多而如果传递群g 具有 一个非传递正规子群1 ，则可以证明的轨道就是g 的一个非平凡块。从 而g 是非本原的所以我 r i l l 入定义：如果序是g 的某个正规子群的轨道集 合，且块图x 与图x 有相同的度数，此时称x 为膏的正规覆盖从理论上讲， 决定一个图的弧传递的正规覆盖比决定以这个图为块图的所有可能的原图要容易 得多，虽然前者也不是一件容易的事所以在证明( 或排除) 一个图是4 度半弧传 递图时，我们有时也采用对块图的讨论这时关键就是要找一个块图使得g 在舀 上作用的核k 在每个块上作用为传递的，根据正规覆盖的定义，我们可以根据 g 的某个非传递的正规子群的轨道来作这个块图，这时自然有k2n 因此，在 我们证明当中的一个重要环节就是寻找一个正规子群对于某些特殊的群找正规 子群还是相对容易的然后再通过分析这个正规子群作成的商图所具有的某些特 殊的结构来确定原图所应具有的结构对于解决这一类问题，商图是一个行之有 效的手段 5 第 一 章 引 言 1 4 整数流的定义及性质 整数流的概念是由t u t t e 在研究和推广平面图的染色问题过程中引入的，为 了给出整数流的定义，我们先给出图的一些基本概念图g 的顶点集和边集分别 记作v ( a ) 和e ( g ) 对于g 的一条边z y ，我们把y 叫z 的邻点，z 的所有邻点 组成的集合记作 b ( z ) ，简单记作( z ) 令片是g 的子图。 是g 一个顶点， 定义硅f ( t ，) = j ( z ) n v ( h ) t ，表示在中的锣点数当彤= g ，d a ( 口) 叫佑w 的度，简单记作d ( v ) 图g 的最小度和最大度分别记作6 ( a ) 和( g ) 对于g 的 子图a 和b ，e ( 4 ，b ) 表示一个顶点在a 中另一个顶点在b 中边的个数如果对 于每个顶点u y ( g ) ，d ( u ) 都是偶数，则g 称为偶图 图g 的一条边e 称为割边，如果g e 的连通分支数大于g 的连通分支数 连通图g 的边割指z ( a ) 的子集使得g 一不连通如果图g 的边集e ( a ) 可以被分成两个非空的子集肠和历使得毋和尼只有一个公共点弘则”称为 g 的割点，连通图g 的顶点割指v ( a ) 的子集y 7 使得g 不连通 k ，边 割( 或k 一顶点割) 指g 的含k 条边( 或k 个顶点) 的边割( 或顶点割) 如果把g 的一条边去掉并且把这条边的两个端点合并成一个顶点，我们称为 收缩这条边假设日是g 的一个连通子图，a h 表示通过收缩日中的所有 边并把可能产生的环去掉而产生的图对于s 矿( g ) ，g s 表示把s 中的所 有顶点从g 中删除并且把至少一个顶点在s 中的所有边也删除所得到的图当 s = u ) ，我们简单记作g 一口札个点上的完全图记为坼。k ：表示从中删 除一条边所得到的图 这里所涉及的图可以有环和重边，但是大多数都是没有割边的。假设d 是 e ( g ) 上的定向图g 在定向d 下的有向图记为d ( g ) 对于一个顶点口y ( g ) ， 令f + ( ”) ( 或者e 一( ”) ) 表示d ( g ) 中的所有以v 为尾( 或者为头) 的非环边 t a t t e 在研究平面图染色和整数流之闯的关系时( 见 7 3 i ) ，证明了下面的两个 命题等价 ( i ) 每个无割边的平面图4 面可染色；( i i ) 每个无割边的平面图有处处非零的 4 - 流 下面我们介绍一下k 流的几个等价定义： 定义1 4 1 令g 是一个有向图，r 是一个k 阶交换群r0 ”为单位元的加法群j ， 6 北 京交通大学博 士 学位论文 g 上的k 一流是一个函数，：e ( c ) 一r 满足下面的条件：对于任何顶点矿( g ) ， ，( e ) = ，( e ) e e e + ( o e e e 一砷 对于这种定义下的k 一流有时也称为z 一流 定义1 4 2 令g 是一个有向图g - l - 5k 流是一个整数值的函数，使得对于 每条边e e ( g ) ，满足一 1 图c k ：( 1 6 m ) 1 2 北京交通大学博 士 学位论文 定义为：点集是y ( c k ( 1 6 m ) ) = y ( 心，4 ) xz 2 。，边集是 e ( c c ( 1 6 m ) ) = ( u ，。) ( a ，。) ，( v ，z ) ( a ，z ) ，( v ，t ) ( b ，z ) ，( w ，z ) ( a ，z ) ， ( w ，z ) ( c ，z ) ，( x ，) ( a ，茁) ，( x ，) ( d ，童) ，( u ，z ) ( b ，石+ 1 ) ， ( u ，茁) ( c ，z ) ，( u ，。) ( d ，z + 2 铲+ 2 t + 1 ) ，( v ，。) ( c ，z + 2 t 2 + ) ， ( v ，z ) ( d ，z + t ) ，( w ，z ) ( b ，+ t + 1 ) ，( w ，。) ( d ，2 7 + 2 t 2 + 3 t + 1 ) ( x ，工) ( b ，茹一) ，( x ，z ) ( c ，z + 2 t 2 + t ) iz z 2 m ， 注意y ( 峨，4 ) xz 胁的每个顶点的第二个下标都取成是模2 m 的剩余我们用c l c 表示托，4 的循环覆盖很容易看出c 1 c ( 1 6 m ) 是二部图本章的主要结论就是下 面的定理 定理2 1 1 假设是一个正整数，m 1 是整除氛2 + c + 1 的数烈c e ( t 6 m 1 是阶为1 6 m 围长是4 的半弧传递图，而且c c ( 1 6 m ) 还是相关数为4 m 的紧相关 的半弧传递图 2 2 自同构的提手 假设x 是一个图，是一个群令x “d k 是x 的一个正则覆盖给定图 x 的一个生成树t ，咖是x 上的个电压分配，如果妒在生成树t 上的电压都 是单位元则称毋是? 一约化的g r o s s 和t u c k e r 2 7 涯明了x 的任何一个正则覆 盖x d 都可以由一个d 约化的电压分配得到，其中丁是x 的任意一棵生成 树很显然如果毋是d 约化的，覆盖图x dk 是连通的当且仅当非树边上的 电压生成整个电压群k 假设a a u t ( x0 4 k ) 是保纤维的自同构，并且设口a u t ( x ) 显然，由 a 诱导出来的在纤维上的置换是x 的一个自同构( 把纤维看成是x 的顶点) 如 果这个自同构恰好是n ，我们就把丘叫做q 的提升，并把a 叫做a 的投影可以 自然定义a u t ( x ) 的子群的提升以及a u t ( xx ok ) 的子群的投影很显然这些子 群的提升以及投影也分别是a u t ( xo k ) 和a u t ( x ) 的子群特别地，如果覆盖 图x 十k 是连通图，那么覆盖变换群是单位子群( 由单位元构成的子群) 的 提升显然，如果a 是o l 的一个提升，则k 5 是。的所有提升 给定x 的一个自同构a ，。到底能不能提升我们可以根据电压的情况决定 假设d a u t ( x ) ，我们定义一个函数石，西是从过固定的一点 v ( x ) 的所有基 本闭迹的电压集合到电压群的一个映射，满足条件。 ( 妒( e ) ) 万= 妒( c 峨) ， 第 二 章 一类 4 度半 传 递 图 这里c 取遍过点u 的所有基本闭迹，似p ) 和( c 4 ) 分别是e 和俨的电压值 注意有这样一个事实，如果k 是交换群，茌并不依赖固定点”的选择，基本闭 迹可以由基本圈来代替下面的命题是【1 2 ，定理4 2 】中的一种特殊形式 命题2 2 1 假设义o d k x 是连通的k 一覆盖，这里是丁一约化的那么x 的一个自同构能提升当且仅当西可以扩展成为的一个自同构 关于x 的自同构提升的更多的结果，建议读者参考f 1 3 ，4 1 ，4 7 】， 设x 的两个覆盖x l 和j 屯，投影映射分别是p 1 和耽，如果存在一个图同构 矗：x l 一尥使得a 沈= j ，l ，则我们称x 1 和x 2 是等价的下面的命题给出了两 个正则覆盖等价的充分必要条件 命题2 2 2 2 9 ，6 6 】两个x 的正则覆盖x “十k 和x p 供中和妒是丁一约 化的，是等价的当且仅当存在一个自同构莎a u t ( k ) 使得对于x 的每条余树边 ( t l ，”) 有毋( t ，) 4 = 砂( ) 2 3 定理2 1 1 的证明 令t 是一个正整数，m 1 是整除2 2 + 2 z + 1 的毅因而，在环砀。中 总有4 2 + 4 + 2 = 0 假设x = 确4 。j z 细是纸4 的正则覆盖且满足在生成 树t 的边上妒= 0 ，在图2 1 中，我们用粗边表示生成树在心4 的余树边上的 电压分配分别是0 1 = i ，勿= t + 1 ，动= 一t ，0 4 = 0 ，岛= 2 t 2 + t ，z 6 = 2 t 2 + t ， 研：2 t 2 + 2 t + 1 ，忽= 和匆= 2 t 2 + 3 t + 1 在这里，2 2 。，1 i 9 ，k 4 4 的 顶点集合为 a ，b ，c ，d ，u ，v ，w ，x 很显然，由于( z l = z 2 。，所以x 是连通图 根据定理前面定义的图c c ( 1 6 m ) ，我们可以得到x = ( 4 4 dz 2 。= c l c ( z 6 m ) 令a = ( a uc w ) ( bvdx ) ，芦= ( u v ) ( wx ) 则有o t 和口都是托，4 的自同 构令g = 妇，p ) ，不难看出( 口，矿) 型z 2 z 2 而且( 口，矿) 是g 的指数为4 的 正规子群从而我们可以证明l g l = 1 6 ，而且，f 4 4 是( g ，；) 一传递的 记i l i 2 i 。为一个圈且顶点顺序依次为 1 ，t 2 ，i ，很容易看出在甄4 中 一共有九个基本圈，分别为u b v a ，w b v a ，x b v a ，u c w a ，v c w a ，x c w a ，u d x a ，v d x a 和w d x a ，这九个基本圈分别是由下面九条余树边生成： ( u ，b ) ，( w ，b ) ( x b ) ， ( u ，c ) ，( v ，c ) ，( x ，c ) ，( u d ) ，( v ，d ) 和( w ，d ) 在n 和3 的作用下，每个圈还映射 到一个长度相同的圈我们把这些圈以及它们的电压列在下表当中，其中e 表示 凰再的基本圈庐( g ) 表示g 上的电压值 1 4 北 京交通大学博 士 学位论文 abcd vwx 图2 1 k 4 ，4 的电压分配 c ( g ) 伊 妒( 伊) c a 似伊) u b v a z l = 1 c v d uz 5 + z 8 一z 7 j rz 4v b u a z l w b v a 钇= t + 1 a v d u 施一幻 x b u e t 名3 一z l x b v a z 3 = 一t b v d u 施一勿+ 魏 w b u a ；5 2 一z 1 u c w a 血= 0 c w a u 勾 v c x a z 5 一 v c w a z 5 = 2 t 2 4 t d w a u 一句+ 幻 u c x a z 4 z 6 x c w a 翔= 2 t 2 + t b w a u 一功+ 名l w c x a 一铂 u d x a新= 2 产+ 2 f 年tc x b u 一+ 钝一z 1 + 讯 v d w a z 8 一却 v d x a 2 ：8 2 d x b u 一z l + z 7 u d w a幻一幻 w d x a询= 2 t 2 + 3 t + 1a x b u z 3 一z l x d w a 一勾 表2 1 ：基本圈的电压以及在口和筘下的像 因为4 t 2 + 4 t + 2 = 0 ，我们能够得到在z 2 。中有( 2 t + 1 ) 2 = - 1 显然，m 1 意味着在z 2 仇中有2 0 ，从而( 2 z + 1 ) 2 1 因此，2 t + 1 z k 的阶是4 下 面我们考虑映射露和万注意到西和万是从凰_ 的九个基本圈的电压到循环群 z 2 。的映射，分别定义为( e ) 5 = 驴( 俨) 和( p ) 9 = ( 伊) ，这里e 取遍刚才提 到的九个基本圈根据表格3 1 以及4 t 2 + 4 t + 2 = 0 和( 2 + 1 ) 2 = - 1 ，我们很容 易就可以验证出百和卢都可以扩展成为z 的自同构，其中西可由1 2 + 1 诱导出，可以由1 一一1 诱导出通过命题2 2 1 ，c e 和卢可以提升，从而g 也 可以提升设o 和矿分别是。和p 的一个提升因此，b _ ( z 2 。，矿，矿) 是 由g 提升得到的a u t ( x ) 的子群，这里z m 可以看作是对虬4 z 2 。的顶点的 第二个下标的右乘作用，因而它也是i u t ( x ) 的子群( 参考第一节) 由于g 作用 1 5 第 二 章一类 4 度半传 递 图 在心，4 上是半弧传递的，所以b 作用在覆盖图x = 段a “d z 2 。上也是半弧传 递的又因为lg i = 1 6 ，我们可以得到l b j = 3 2 m 令a = a u t ( x ) ，则bsa 要 想证明x 是半弧传递的，我们只需证明a = b 就可以了 为了叙述方便，我们用z 。表示x 的顶点( z ，z ) ，这里z y ( k 4 , 4 ) ，z z 2 。 我们很容易证明( a 0 ，1 1 0 ，c o ，w o ) 和( a 0 ，v o ，c 2 1 2 + ，x o ) 是x 中的长为4 且过点a 0 的两个圈，由此我们马上就能得出x 是点传递和边传递的x 的点传递性表明对 于任意给定的属于y ( x ) 的点，存在两个4 - 囤过这个点显然，对于任意z z 2 m ， 过点站的两个4 圈分别是( 钆，u 。，c 。，w x ) 和( a 。，v ，c z 4 - 2 t ，十c j 砀) 我们可以看出 这两个垂圈分别具有a u c w 和a v c x 的类型更进一步，每个x 的4 圈都具有这 样的形式我们把一个循环序列的所有类型看做是相同的类型所以a u c w ，u c w a ， c w a t l 和, w a u c 都是相同的类型，记住和矿分别是= ( a uc w ) ( b v d x ) 和= ( 1 1v ) ( wx ) 的提升不难验证4 圈( a o ，u o ，c o ，w o ) 在( o + ) 3 矿矿和 陋+ ) 3 矿a 作用下的像分别具有类型b v d x 和b u d w 注意到y ( 甄，4 ) 的每个顶点 在下面的四种类型中都出现两次，又因为过v ( x ) 的每一个固定顶点都有两个垂 圈，我们不难得出x 中的每个4 圈都具有下面的某一种类型； ( 1 ) a u c w ( 2 ) a v c x ( 3 ) b v d x ( 4 ) b u d w 因此，如果对于1sis4 ，z y ( ，4 ) 是类型( i ) 的四个字母之一，则过点玩 ( 。z 2 。) 有唯一一个( i ) 型的4 一圈我们用z 。( i ) 来表示这个4 - 圈例如，因为 v 是类型( 2 ) 和类型( 3 ) 中四个字母中的一个，所以过点v ，的两个垂圈具有类 型( 2 ) 和( 3 ) 再根据图2 1 和上面类型( 2 ) 和类型( 3 ) 中的4 - 圈的表达式，这两 个4 - 圈分别是v 。( 2 ) = ( v 。，c z + 2 t 2 + l x z ，) 和( 3 ) = ( v 。，d z + t , b 。) 令a 丘0 是a 0 在a 中的稳定化子我们知道a o ( 1 ) 和a 0 ( 2 ) 是仅有的过点a 0 的两个4 - 圈设a ；o 是a a 。中的保持a 0 ( 1 ) 和a o ( 2 ) 这两个4 - 圈不动的子群 我们断言心= 1 根据图2 1 以及上面的四种垂圈类型的描述，我们可以得到下面的4 - 圈： a 0 ( 1 ) = ( a o ，u o ，c o ，w 0 ) = c o ( 1 ) c o ( 2 ) 。( c o ，x 一2 5 2 一t ，a 一2 t 2 一f ，v 一2 2 一t ) u o ( 4 ) = ( u o ，d 2 庐+ 2 t + 1 w 咄b 1 ) = w f ( 4 ) w o ( 4 ) = ( w 0 ，b t + l ，u t ，d 2 t 2 + 3 t + 1 ) = u d 4 ) w d 1 ) 2 ( w 一，a f ，u 一，c t ) u d l ) = ( 1 i t ，c t ，w t ，a # ) 1 6 北京交通大学博 士 学位论文 令7 a i o 那么7 固定a o 和四圈a 0 0 ) ，这就表明7 固定 1 1 0 ，w o 不动 下面我们来证明1 分别固定u o 和w o 要证明1 分别固定u 0 和w o 不动，我们将 要通过上面的前两个垂圈来证明，固定巩，再由后面的四个4 - 圈来证明了不能 对换1 1 0 和w 0 由于7 固定a o