（应用数学专业论文）完全多部多重图的路因子分解.pdf

完全多部多重图的路因子分解 摘要 摘要 关于多重图a g 的r 因子分解问题已经有不少人研究过，并且得到若 干的应用特别的，n 锄o t o 锄du s h i o 等 17 】在数据系统的h u b m f s 2 方案 中给出它的一些应用对于完全多重图a j 的r 因子分解，完全二部多重 图a ，n 的最一因子分解，以及完全多部多重图a ( j 厶掌及) 的r 因子分解 已经有一些已知的结果入；的r 因子分解存在性问题已经由h o r t o nf l o l 及b e r m o n d ，h e i n r i c h 和y u 【4 】完全解决a ，n 的r 一因子分解存在性问题 也已经由u s b j o 【1 2 】，w 衄g 【1 4 】，d u 【7 】及w a n g 和d u 【8 ，9 ，1 5 ，1 6 】完全解决 在本文中我们将研究多部多重图a ( 。，c 凰) 的r 因子分解问题我们已 经知道多部多重图a ( ，宰厩) 存在r 一因子分解的必要条件是m 讫三o ( m 甜南) 和a ( m 一1 ) 础三o ( m d d2 ( 七一1 ) ) 易知a ( 木风) 存在恳因子分解当且仅当 m 礼兰o ( m 甜2 ) u s h i o 和t s u m n o 【1 3 】及d u 【6 】已经证明当七= 3 时，上述必 要条件也是充分的对于一般的老，y uf 1 8 1 已经证明了当奄 3 且是是素数时 上述必要条件也是充分的，并提出猜想：当七为非素数幂时，完全多部多重 图a ( 函，仇木鼠) 存在r 因子分解的必要条件也是充分的在本文中我们将证 明当七= p + 1 且p 是素数时，上述必要条件也是充分的这样，当七= p + 1 且p 是素数时，我们解决了y u 【1 8 】关于完全多部多重图的r 因子分解的猜 想 关键词：多部多重图；路；因子分解；h u b m f s 2 方案 作者：吴章贵 指导教师：杜北梁( 教授) o np a t hf a c t o r i z a t i o no fc o m p l e t em u l t i p a r t i t em u l t i g r a p h 8a b s t r a c t o np a t hf a c t o r i z a t i o no fc o m p l e t em u i t i p a r t i t em u l t i g r a p h s a b s t r a c t r f a c t o r i z a t i o no f 入gh a v eb e e ns t u d i e db ym a j l yr e s e a r c h e r sa n df o u n dam lm _ b e r o f 印p l i c a t i o n s e s p e c i a l l y ，y 衄a m o t oa n du s h i oe t c 1 7 】h a 鹏g i v e ns o m ea p p l i c a t i o 璐 i nh u b m f s 2s c h e m 镪o fd a t a b a s es y s t e m s t h e r ea r ea 1 8 0s o m ek n 侧nr 髑u l t so n t h ee ) d s t e n c eo ft h er - f a c t o r i z a t i o no fc o m p l e t e m l t i g r a p h sj 、k n ，c o m p l e t eb i p a r t i t e m u l t 睁印h s 入。na n dc o m p l e t em u l t i p 缸t i t e 眦l t i g r a p h sa ( j o 牛k 1 ) t h ee ) 【i s t e n c e o fr f a u c t o r i z a t i o no fa k nh a 代b e e nc o m p l e t e l ys o l v e db yh o r t o n 【1 0 】a n db e m o n d ， h e i n r i c ha n dy u 【4 1 t h ee ) 凼t e n c eo f 最- f 缸t o r i z a t i o no fa ，nh a v eb e e nc o m p l e t e l y s o l v e db yu s h i o 【1 2 l ，v g 【1 4 】，d u 【7 ja n dv ga n dd u 8 ，9 ，1 5 ，1 6 】 i nt h i sp a p e rw e 研us t u d yr 一五a c t o r i z a t i o no fa ( k n 爿cj ) i ti se a 盯t o8 t h a ta ( k n 木k 1 ) h 鹪a 岛f 址t o r i z a t i o ni f 鲫do n l yi j fm n 兰o ( m d d2 ) u s h j oa n d t s u r u n o 【1 3 】a n dd u 【6 】h a v e8 h o w nt h a tt h en e c e 鹤a 唧c o n d i t i o n sa r ea l s o8 u 伍c i e n ti f 七= 3 n u 恤e r ，y ，u 【1 8 】h 嬲8 h 帆mt h a tt h e s et w on e c e 鹃a r yc o n d i t i o 璐a r es u 伍c i e n ti f 七 3a n d 惫i sap r i m e ，a n dr a i ac o n j e c t l l r e ：t h en e c 鹤s a 珂c o n d i t i o n sf o rc o m p l e t e m u l t i p 鲫t i t em u l t i g r a p h sa ( j 厶事k 。) t oh a v ea 最一f a c t o r i z a t i o a r es u 伍c e n tw 1 1 e np i sn o tt h ep o w e r0 fp r i m e i no u rp 印e rw e 诵us h o wt h a tt h en e c e 鹃a 哆c o n d i t i o 璐 f o rc o m p l e t em u l t i p a i r t i t em u l t i g r a p h st oh a ：、，ear f a c t o r i z a t i o na r e6 u 伍c i e n 七w h e n 七= p + 1a n dpi sp r i m e t h i sa n s w e r st h ec o n j e c t u r eo f y h 【1 8 】o nr f a c t o r i z a t i o n s o fc o m p i e t em u i t i p a r t i t em u i t i g r a p h s ，w h e n 凳= p + 1a n dpi sp r i m e k e yw o r d s ：m u l t i p a r t i t em u l t i g r a p h s ；p a t h ；t o r i z a t i o n ；h u b m f s 28 c h e m e s 1 1 w t i t t e n 坶w uz h a n g g u i s u p e n r i s e d 坷d ub e i l i a n g 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本 声明的法律责任。 研究生签名：数日 觏：船、 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：墨叠墨日期：鲤：丝五查 导师签名：丞兰拦日期：型：墨坐 完全多部多重图的路因子分解 一引言 芦i 士 ji 置 多重图a g 是互不相交a 个图的并，且其中每个图都同构于g a g 的一 个r 因子是a g 的一个生成子图，它的每一个分支是一条长为七一1 的路 ( r ) 如果a g 的所有边可以被划分成若干个r 因子，我们就说天g 有个 r 因子分解，并记为r i i 入g 设g 和日是两个图它们的圈积g 宰日的顶点集为y ( g ) y ( 日) ，并 且点( 夕1 ，h 1 ) 和点( 夕2 ，) 关联当且仅当夕1 9 2 e ( g ) 或9 l = 夕2 且h k e ( 日) 、 木风称为完全正则m 部图，其中以是完全图的补图我们可以称 之为完全正则多部图相关的定义可以参见【5 】 入g 的r 一因子分解问题已被不少人研究过，并且得到若干的应用特别 的，y a m 锄0 t oa n du s h i 0 等 1 7 】在数据系统的h u b f s 2 方案中给出它的一些应 用对于完全多重图入j 的艮因子分解，完全二部多重图a n 的r 因子 分解，以及完全多部多重图a ( ，c 赢) 的r 一因子分解已经有一些已知的结 果入j 的最因子分解存在性问题已经由h o r t o n 【1 0 】及b e m o n d ，h e i n r i c h 和 y u 【4 】完全解决a ，n 的r 因子分解存在性问题已经由u s h j o 【1 2 】，w 抽g 【14 】， d u 【7 】及w 如g 和d u 【8 ，9 ，1 5 ，1 6 】完全解决 在本文中我们将研究a ( j o 木风) 的r 因子分解问题我们已经知道 1 8 】 入( 甬，m 牛风) 存在r 因子分解的必要条件是m 几兰o ( m d d 尼) 和入( 仇一1 ) 础兰 o ( m d d2 ( 七一1 ) ) 易知入( 宰砍) 存在p 2 因子分解当且仅当m 扎兰o ( m d d2 ) u s h i o 和t s u m n o 【1 3 1 及d u 【6 】已经证明当七= 3 时，上述必要条件也是充分 的对于一般的七，y u 【1 8 l 已经证明了当七 3 且七是素数时该必要条件也 是充分的事实上，他给出了更强的结论： 定理1 1 ( 1 8 】) 如果爻( 仇一1 ) 砒兰o ( m 以2 ( 奄一1 ) ) 且m 三o ( m 以七) 或 礼三o ( 仇o d 七) ，则r 忪( 宰或) 然而，完全多部多重图入( 木赢) 的r 因子分解的存在性问题 1 8 1 仍 然未完全解决y u 【1 8 1 给出了下面的猜想： 猜想1 2 当七为非素数时，r 忪( 木凰) 当且仅当仇扎兰o ( m o d 七) 且 a ( m 一1 ) 佗七三o ( 仇d d2 ( 七一1 ) ) 完全多部多重图的路因子分解 一引言 在m u t h u s 锄y 和p a u l r a j af 1 1 】的文章中，他们给出了宰疋存在r 一因 子分解的一个充分条件，从而解决了上述猜想的七= p + l 且a = 1 的情形， 其中p 是素数这个充分条件可以叙述如下： 定理1 3 设七为偶数如果m n 兰o ( m d d 七) 且n 三o ( m d d 七一1 ) 或m 一1 兰 o ( m o d 七一1 ) ，则最| i 宰赢 在本文中，我们将给出入( ，c 讯) 存在r 因子分解的充分条件，从而 当七= p + 1 ，p 是素数，且a 为任一个正整数时，我们解决了上述猜想 2 完全多部多重图的路因子分解 二 预备知识 二预备知识 在这节我们将定义一些辅助设计，并建立一些后面将用到的基本的结 果读者可以从著作【5 】上得到更多的信息设g 一个r 部图，其分部为 m ，k ，贝0y ( g ) = u ：1k 如果对于所有的 和歹，i f = i 巧f ，1si 歹r ， 且顶点集为k u ，二分类为( k ，巧) 的g 的一个二部子图是t ( “歹) ) 一正则的， 其中是从集合 托歹) ：l i 歹r ) 到非负整数集的一个映射，那么我们 称图g 是可压缩的 设g 是一个可压缩图，它的分部是，w 那么g 的商图的顶点 集为y ( q ( g ) ) = 【u 1 ，忱，珥) ，边协的重复度为( 【i ，歹) ) ，其中1 i 歹7 ， 并记g 的商图为q ( g ) 设y ( 爻( 书鼠) ) = ( u ，匆) ：l i m ，1 歹礼) 为方便起见，我们 把( ，哟) 记为u ；，于是y ( a ( 木风) ) = 嵋：1 i 仇，1 歹n ) 从而 y ( a ( 事反) ) 可以有两种方式表示，即u ；，屿和u 竺。k ，其中= 牡；： 1 i 仇) ，k = 【u ；：1 歹n ) 设日是a ( 车取) 的子图如果日关于 分部，k ，是可压缩的，则记日的商图为q y ( 日) 如果日关于分部 巩，巩，是可压缩的，则记日的商图为q u ( 日) 对于t 1 ，2 ，n ) ，我们定义正则二部图b = b ( x ，y ) 如下：b 的分 部为x = _ 【茁1 ，z 2 ，) 和y = 【y l ，珈，孙) ，并且对于每个s t ，它有边集 a 。( x ，y ) = 【z 。蜘，z ：可j + l ，z 。玑一1 ) ，其中的加法是在模扎余1 ，2 ，n 下进行 的显然，对于每一个s t ，( x ，y ) 都是b 的个1 因子因此，b 的边集 e ( j e i ) = 0 。盯【a 。( x ，y ) ) ，其中0 表示边不交的子图的并如果t = 【1 ，2 ，n ) 则b 就是分部为x 和y 的完全二部图 因此，如果g 的边集可以象上面图b 的边集那样表示的话，则对于某 个t ，我们可以用0 。e r q 。( x ，y ) ) 来表示二分类为( x ，y ) 的完全二部图g 的 边集在不产生混乱的情况下，我们可以把( x ，y ) 简写为e ( x ，y ) 表 示一个顶点在x 上，另一个顶点在y 上的所有边的集合 如果( i ) g 是偶正则的，e ( g ) 是边不交的哈密尔顿圈的并或者( i i ) g 是 奇正则的，e ( g ) 是边不交的哈密尔顿圈及一个l 一因子的并，则称图g 存 在哈密尔顿圈分解( 日g d ) ( 或g 是可哈密尔顿圈分解的( 日d 分解) ) 3 完全多部多重图的路因子分解 二 预备知识 对于哈密尔顿圈分解，我们有下面的一些结果： 引理2 1 ( 【1 1 ) 完全图虬是可哈密尔顿圈分解的 引理2 2 ( 【3 】) 若( r 一1 ) 礼为偶数，则坼丰鼠是可哈密尔顿圈分解的 为建立本文的结果，我们需要入g 的商图的一些结果； 引理2 3 如果a g 是一个可压缩的多部多重图，并且q d g ) 存在最因子 分解，则a g 也存在r 因子分解 证明：设多部多重图a g 的顶点集为y ( a g ) = u ：，风，分部为日1 ，日2 ，研 由于a g 是可压缩的，故i 凰i = l 毋i ，1 i 歹，并假设顶点集为甄u 马，分 部为日i ，马的二部子图是t ( i ，歹) ) - 正则的令q ( a g ) 有一个r 因子分解： r ( 1 ) ，r ( 2 ) ，r ( z ) ，其中z = i e ( q ( a g ) ) l i e ( r ) i 每个r ( i ) 都可以按如下方 式产生a g 的一个最因子：对于每条边加e ( r ( 吡可以得到个顶点集 为日p u 凰，分部为日p ，日口的二部子图中的1 一因子，从而由边p 口( 重复度为 t ( p ，g ) ) ) 产生的t ( 仞，g ) ) 个1 - 因子都是边不交的显然，u 辨e ( a ( i ) ) 是a g 的一个r 因子口 引理2 4 如果a g 存在r 一因子分解，则( a g ) 宰雇也存在r 因子分解 证明：设 沪。，伊：，汐。) 是a g 的个r 因子分解则对于汐；的每条边 t j t ，我们可以得到( a g ) 木忍中的一个完全二部图群门连结群，的r 个1 因 子后，我们可以得到( a g ) 半鼠中r 个r 一因子因此，从入g 的甩因子分 解中，我们可以得到( a g ) 丰豇的r 一因子分解 口 a c k 表示m 个顶点的圈，其边的重复度为a ( ) 。，入：) 表示m 个顶点 的圈，其中边的重复度是a 。或a 。，且重复度为入。的边和重复度为a 。的边交 替出现为证明我们的结果，需要下面的引理 引理2 5 ( 【1 1 】) 设q ( g ) 是g 的商图，g 是下面任一情形的图： ( a ) a i ：k ，其中a 三o ( f n o d 七一1 ) ，m 兰o ( m o d 七) ， ( b ) ( a l ，a 2 ) ，其中m 兰o ( m d d 七) ，七为偶数，入l = ( 七2 ) 一l ，a 2 = 七2 ， ( c ) & ，其中有r 条边的重复度为七一r ，另外的忌一r 条边的重复度为七一( r + 1 ) ， 其中r o r 忪( j 0 木k ( 七t ) ( ( 七一1 ) 闾8 ) 证明：易知，a ( 石0 木稚t ) ( 似一1 ) 阚，) 星a ( ( 甄，宰豇七t ) 。) 木豇奄一1 ) d ) 下面我们分两 种情况来证明 情形1 ：( 打一1 ) 砖t 为偶数由于，- c 露( k 。h 是( 打一1 ) 砖t 正则的，即 偶正则的，由前面引理2 2 可知：幸露( 女。p 是可h d 分解的，设它分解成 哈密尔顿圈凰，飓，甄钾一。) h 2 。，因此 ( t r 一1 ) 七s a ( ( ，木甄七t ) 。) 木甄k 1 ) d ) =0a ( 凰木甄七一1 ) d ) 由引理2 6 知：上面每个入( 风宰露( k 一1 ) d ) 都是可r 因子分解的，因此r 盼( 幸 豇七t ) ( ( 七一1 ) 田。) 情形2 ：( 打一1 ) 七s t 为奇数设环宰露( 七t ) ，= 口由于日奇正则的，此时 打为偶数，七s a 为奇数，由引理2 7 知存在b 的个哈密尔顿圈分解h c d 【d 1 ，d 2 ，d ( ( t r 一1 ) ( k 。t ) 一1 ) 2 ，使得对于某个i ，矾o ，有完美1 - 因子分解 不失一般性，我们不妨设d to f 7 有完美1 - 因子分解： 只，尼，f 7 ) ，其中毋，r 是d 。的两个1 因子为得到子图a ( b 木最) d ) 的商图，我们需要一个它的 顶点划分为此，设札1 ，t 1 2 ，矿h 是图b 的顶点，并设u 1 ，乱2 ，u ( 七一1 ) d 是图 量七- 1 ) 屉的顶点因而y ( 又( b 书豇七- 1 ) 肛) ) = u 尝k ，其中= 铭i ，鸸，咄_ 1 ) 弘) ， 1 i r s 七 因此 ( 渺一1 ) ( k 5 t ) 一1 ) 2 ) a ( b 术风1 ) d ) =o ( a ( d i 宰露( ) d ) ) i = 2 。 o ( a ( ( r oro f 7 ) 幸k ( 七一1 ) d ) ) ， 其中n o r = d 1 由于i 取i 三o ( m d d 七) ，根据引理2 6 ，每个入( d 木豇知一，) d ) 都是 可r 因子分解的为完成证明，我们还需要证明r 忪( ( r o 马o f ) 木豇七一- ) d ) 由引理2 3 ，我们只需证明r i i q y ( a ( ( f 1 0 r o f ，) 木豇七一- ) d ) ) 根据商图的定义， 7 完全多部多重图的路因子分解 三 主要结果 q y ( a ( f l 木露( 七一1 ) d ) ) = 爻7 f 1 ，q y ( a ( r 木丘k 1 ) d ) ) = a 7 岛，q y ( a ( f 7 木豇一1 ) d ) ) = 入f ，其中a r ，a 7 f 2 和a 7 f 7 分别是图b 的入7 个1 因子，a 7 = a ( 七一1 ) d = ( 七一1 ) ，a = 剥 显然我们有，入日= ( a 1 日o a 2 局) ，a 7 f 2 = ( a 1 兄。沁f ，) ，入7 f ，= q l p o 入2 日) ，其中a = ( 七2 ) 一l ，入2 = 七2 由于 日，b ，f ) 中任两个1 因子形成图 b 中的个哈密尔顿圈，故( a 1 只o a 2 易) 兰( 入l 咒o a 2f ，) 竺d ，( a 1 o a 2 r ) 望 g 础( a l ，a 2 ) 因此，由引理2 5 ( b ) 可得：r i l ( a l f lo 入2 r ) ，r | | ( a 1 岛o a 2 f 7 ) 及 r j j ( a 1 oa 2 只) 从而有最| j ( 入1 只oa 2 b ) ，rj j ( 爻l 易oa 2 f 7 ) 和rj j ( a 1 f 7e 入2 只) ，这三个式子表明了q y ( a ( ( no 易of ) 车豇k 1 ) d ) ) 是可r 因子分解 的口 引理3 2 若七是偶数，啦，t 1 ，且d = 夕c d ( a ，七一1 ) ，那么对于每个s o ， 有最l i a ( 勇，( 女t ) ( ( 七一1 ) d ) 。+ t ) 事j 乙) 证明：令r = ( ( 七一1 ) d ) s + t ，则有 a ( 甄七t ) ，车盈) 鲁a ( 木或) oa ( ( k ( 知t ) 木兄) ( r ) ) ( 1 ) 这里( 甄七t ) 木鼠) ( 7 _ ) 表示r 个图的并，其中每一个图都同构于甄七。) 木兄 设u l ，铲，矿是珥的顶点，则有 y ( a ( 坼率最) ) = y ( a ( 墨宰最) 0 久( ( 甄坼) 木或) ( r ) ) = uk = u 屿， 其中= 让i ，遽，堪) ，= ( u ；，田，嵋) 由注2 9 知：a ( 甄七。) 奉兄) 可以被分解成若干条边重复度为入，长为七一1 的 路及个边重复度为a 的线性森林的并不失般性，我们可以假定线性森林 中的路的顶点的下标是相邻的设y ( a ( 殛七t ) 幸凰) ) = y ( 最) = 乱1 ，u 2 ，牡k 下面我们将分两种情况来完成剩下的证明 情形1 ：r 为偶数根据引理2 1 ，设 日1 ，岛，坼一2 ) 2 ，f 7 ) 是坼的个 哈密尔顿圈分解为方便起见，给哈密尔顿圈皿的边个定向，使它成为 定向哈密尔顿圈；给1 因子f ，的边任意一个定向我们仍然记定向的哈密 尔顿圈甄和定向1 因子f ，为凰和f 7 对应于坼的每条弧，我们可以得 8 完全多部多重图的路因子分解 三主要结果 到a ( 墨木凰) 中的一个完全二部图虬芦对应于矾中的每条弧饥吻，我们按 如下方式得到，嵋中的一个l - 因子r 码： r 勘= 缸i ，u ；，u ；一，q ( 2 ) 对应于的每条弧虢吻，我们按如下方式得到，的中的一个1 一因子凡叼： r 码= 遁趣，钍；遁，t 遥，诞以，牡：一。以一。，以一。以一。，让：q ，u i ) ( 3 ) 由于鼠和f 的每条边都有一个定向，因此r 。q 是唯一确定的令 g = l ，由引理2 5 ( c ) 知，( 一1 ) 2 ) go 爿) 是可r 一因子分 解的从而久( ( 一1 ) 2 ) 瓯。影) 也是可最一因子分解的至此，根据引理2 3 ， 我们可以得出结论：a ( gor ( r ) ) 是可r 一因子分解的口 现在，我们开始证明本文的主要结果 定理3 3 设七为偶数如果肼l 三o ( m d d 七) 且h 兰o ( m d d 七一1 ) 或 a ( m 1 ) 兰o ( m d d 南一1 ) ，勇5 么r 0 久( 石，m 宰j 乙) 证明：如果仇三o ( m 以七) 或n 三o ( 仇d d 七) ，那么由定理1 1 可知r 盼( 奉砍) ， 因此，我们假设m ，n o ( 仇0 d 七) 首先，如果 m 三o ( m 以七) 且a 他兰o ( m d d 七一 1 ) 设亡= 夕以( 是，m ) ，我们可以得到，对于某个r o ，有m = 打，9 c d ( 七t ，州t ) = 1 于是同余方程m n 兰o ( m d d 膏) 和爻佗三o ( 仇以南一1 ) 可化简为：n 三o ( m d d ( 七t ) ) 和n 三o ( m 砌( 七一1 ) d ) ，其中d = 夕c d ( 入，七一1 ) 由中国剩余定理【2 】 我们得 到t 对某个s o ( 仇o dt ) ，n = ( 忌t ) ( ( 七一1 ) 由s 这样，根据引理3 1 就有 r 忪( 木赢) 下面，我们考虑懈三o ( m 础奄) 且天一1 ) 三o ( m o d 足一1 ) 的情形设= 9 以( 后，n ) ，则对于某个t _ o ，有礼= 打，夕c d ( 七t ，几t ) = 1 又由于仇，礼o ( m d d 忌) 且t 1 ，我们将同余方程仇他兰o ( 仇甜七) 和a ( m 一1 ) 三o ( m 甜七一1 ) 化为： m 三o ( m d d ( 七) ) 和m 一1 兰o ( m 以( 七一1 ) d ) ，其中d = 夕c d ( a ，七一1 ) 再由中国 剩余定理【2 】，对于某个s o ( m d dt ) ，有m = ( 七) ( ( 七一1 ) d ) 占) + 七我们容易验 证：a ( 木琢) = 久( ( 木丘) 事墨) = ( a ( 木元) ) ：c 忍根据引理3 。2 和引理 2 4 ，我们得r 忪( 赢) 口 推论3 4 设七= p + 1 3 ，p 为素数则r 盼( 宰赢) 当且仅当m n 兰o ( m d d 七) 且a ( m 一1 ) 仡七三o ( 仇o d2 ( 七一1 ) ) 证明：通过计算入( 木赢) 中的r - 因子的顶点数和边数，容易验证必要性 成立 反之，设一1 为素数如果礼三o ( m o d 忌一1 ) 或m l 三o ( m d d 是一1 ) ，那 么由定理1 3 ，r0 木取因而r i i ( 木砍) ( a ) 现在，设礼o ( 仇d d 七一1 ) 且 1