（计算机应用技术专业论文）flower+snark图与knodel图的亲切素标号.pdf

大连理工大学硕士学位论文 摘要 图的标号问题是图论中一个比较新的课题，它可追溯至u 1 9 5 0 年信号带宽的优化问 题：源于主要的非零数字信号通常位于一个比较窄的带宽中。1 9 6 6 年r o s a 给出了图 标号的一个新的概念图的优美标号( g r a c e f u ll a b e l i n g ) ，并提出了著名的所有的树都 是优美的猜想。图的标号是指在一定规则条件下对图的顶点与边进行标号。个图的顶 点标号是图的顶点集到整数集的映射，而边标号则是图的边集到整数集的映射，根据对 映射的不同要求，产生了各种类型的图的标号，例如优美标号、超幻和标号、调和标号 和亲切素标号等等。 图的亲切素标号是由s u m n d a r m ，p o m a j 和s o m a s u n d r a m 于2 0 0 5 年提出来的。如果一个 带有顶点集v 的图存在一个从v 至o 1 ，2 ，i m ) 双彤对每条最大公约数舻锨“) ，苁v ) ) = 1 的边标号为1 ，并且对最大公约数g c d ( t ( u ) ，苁v ) ) 1 的边标号为0 ，则标号为l 的边的数量和 标号为0 的边的数量相差最多为l ，这类图被称作有亲切素标号。 g 是一个简单的非平凡的连通的三正则图，点集坎g ) = 嘞b 6 “西：0 茎脚1 ，边 集以g ) = 口艘件i ，b s b f + 1 ，c a ：f + ，如6 劬6 咖，：0 5 锄1 ，点的标号对n 取模，风可以由g 通过用边b n - i c o ，c n - l b 0 替换b n q b o ，o n 1 e o 得到。如果n 为奇数且庀5 ，风被称作f l o w e rs n a r k 图。其他的图，被称作f l o w e rs n a r k 图的相关图。 s u m n d a r m 等证明了如下几类图是可亲切素标号的：循环图c 。6 ) 、路径 ( 群3 ， 5 ) 、星图k l “行为奇数) 、双星 虱( b i s t a r sg r a p h ) 、龙m ( d r a g o ng r a p h ) 、皇冠图( c r o w ng r a p h ) 、 三角蛇图死铆芝3 ) 以及梯子i 虱( l a d d e rg r a p h ) 本文设计了计算机辅助下求解的k n 6 d e l 图和f l o w e rs n a r k 及其相关图的亲切素标号， 并用数学的方法给予了证明。 关键词： f l o w e rs n a r k ；k n o d e l ；素标号；亲切标号；亲切素标号 大连理工大学硕士学位论文 p r i m ec o r d i a ll a b e l i n go ff l o w e rs n a r k g r a p h sa n dk n 6 d e lg r a p h s a b s t r a c t g r a p hl a b e l i n gi sar e l a t i v e l yy o u n gs u b f i e l do fg r a p ht h e o r y t h ef i r s tb o n af i d eg r a p h l a b e l i n gp r o b l e mi s t h eb a n d w i d t hp r o b l e m ，w h i c hi sc o n c e r n e dw i t hm i n i m i z i n gt h e d i f f e r e n c eb e t w e e nt h el a b e l so fa d j a c e n tv e r t i c e s b a n d w i d t hw a s o r i g i n a l l ys t u d i e di nt h e 19 5 0 s ，i nr e l a t i o nt om a t r i c e sw i t ha lln o n - z e r oe l e m e n t sl y i n gw i t h i nan a r r o wb a n da b o u t t h em a i nd i a g o n a l i n19 6 6 ，r o s ai n t r o d u c e dt h ef a m o u sc o n j e c t u r et h a ta l lt r e e sa r eg r a c e f u l w i t han e wt y p eo fg r a p hl a b e l i n g “g r a c e f u ll a b e l i n g ”ag r a p hl a b e l i n gi sa 1 1a s s i g n m e n to f i n t e g e r st ot h ev e r t i c e so re d g e s ，o rb o t h ，s u b j e c tt oc e r t a i nc o n d i t i o n s v e r t e xl a b e l i n gi sa m a p p i n gt h a tm a p st h ev e r t e xs e ti n t oi n t e g e rs e t ，a n de d g el a b e l i n gm a p se d g es e ti n t oi n t e g e r s e t a c c o r d i n gt ot h ed i f f e r e n tr e q u i r e m e n t sf o rt h em a p p i n g ，m a n yv a r i a t i o n so fg r a p h l a b e l i n g sh a v eb e e ne v o l v e d ，i n c l u d i n gg r a c e f u ll a b e l i n g ，m a g i cl a b e l i n g ，h a r m o n i o u sl a b e l i n g a n dp r i m ec o r d i a ll a b e l i n ga n ds oo n t h ec o n c e p to fp r i m ec o r d i a l l a b e l i n g i si n t r o d u c e db y s u m n d a r m ，p o n r a ja n d s o m a s u n d r a mi n2 0 0 5 ag r a p hw i t hv e r t e xs e tvi ss a i dt oh a v eap r i m ec o r d i a ll a b e l i n gi f t h e r ei sa b i j e c t i o n f f r o mv t o l ，2 ，iy 1 ) s u c ht h a ti f e a c he d g el n ，i sa s s i g n e dt h el a b e ll f o rt h eg r e a t e s tc o m m o nd i v i s o rg c d 妖u ) , 贝v ) ) = 1a n d0f o rg c d ( 1 ( u ) , 贝d ) lt h e nt h en u m b e r o fe d g e sl a b e l e dw i t h0a n dt h en u m b e ro f e d g e sl a b e l e dw i t hld i f f e rb ya tm o s t1 l e tgb eas i m p l en o n t r i v a lc o n n e c t e dc u b i cg r a p hw i t hv e a e xs e t 坎g ) = 瓯b c 6 西： o s 脚一1 ) a n de d g es e t 以g ) = 口矽，+ l ，ib i b 1c 而+ 1 ，妇 a , b 6 咖，：0 5 _ i 5 ，- i ni sc a l l e das n a r k ，n a m e l yf l o w e rs n a r k w h i l et h eo t h e rg r a p h s ，a r ec a l l e dt h er e l a t e dg r a p h so ff l o w e rs n a r k s u m n d a r m p r o v e dt h a tt h ef o l l o w i n gg r a p h sa r ep r i m ec o r d i a l ：gi fa n do n l yi fn 之6 ；p n i fa n do n l yi fn 3o r5 ；k i ，o d d ) ；b i s t a r s ；d r a g o n s ；c r o w n s ；t r i a n g u l a rs n a k e s 兀i fa n do n l y i f 力兰3 ；l a d d e r s i nt h i st h e s i s ，w ep r o v et h a tf l o w e rs n a r ka n di t sr e l a t e dg r a p h sg ( 焉) a r e p r i m ec o r d i a l i nt h i sp a p e rw ep r o v i d ea na l g o r i t h mt os e a r c ht h ep r i m ec o r d i a ll a b e l i n g so ff l o w e r s n a r kg r a p h sa n dk n 6 d e lg r a p h sb yc o m p u t e ra n di ti sp r o v e di nam a t h e m a t i cw a y k e yw o r d s ：f l o w e rs n a r k ；k n 6 d e l ；p r i m el a b e l i n g ；c o r d i a ll a b e l i n g ；p r i m ec o r d i a ll a b e l i n g ； 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：劲之釜淑日期：即8 筝多日f 8r 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 文版权使用规定 ，同意大连理工大学保留并向国家有关部门或机构送交 位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理工 学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可 用影印、缩印或扫描等复制手段保存和汇编学位论文 储龆至丝塑 剔币勰杨荔七 导师签名：! l 竺二： 塑墨年上月旦日 大连理工大学硕士学位论文 引言 1 7 3 6 年是图论的历史元年，这一年欧拉( e u l e r ) 研究了著名的柯尼斯堡七桥问题，发 表了图论的首篇论文，开创了图论科学的研究。1 9 3 6 年，匈牙利著名图论学家k o n i g 发表了有限图与无限图理论，这是图论的第一部专著，它总结了图论二百年的主要 成果，是图论的重要里程碑。此后，图论开始飞速发展起来，成长为数学科学中一门独 立的学科。它的分支很多，例如，算法图论、极值图论、网络图论、代数图论、随机图 论、模糊图论、超图论等等。由于现代科技尤其是大型计算机的迅猛发展，使图论大有 用武之地，无论是数学、物理、化学、天文、地理、生物等基础科学，还是信息、交通、 战争、经济乃至社会科学的众多问题，都可以应用图论方法予以解决。 图论所涉及的问题比较广泛，而解决问题的方法千变万化，非常灵活。现实世界中 的许多事物( 或对象) 能用图表示其拓扑结构，把实际问题的研究转化为图的研究，利用 图论的相关结论对这些问题做出分析和判断。因此，图论在自然科学和社会科学的许多 领域有着广泛的应用，同时也是计算机科学的重要基础【确】。 图论是离散数学的骨干分支，离散数学则是计算机科学技术与网络信息科学的思想 基础。多年来，为了实现高速计算的目的，数学促进了计算机科学的形成与发展，例如 图灵机的数学理论为计算机的诞生打下了基础。另一方面，随着计算机科学在社会发展 中作用的日益提升，它又反过来促进数学的发展，例如1 9 7 6 年伊利诺大学的a p p e l 和 h a k e n 用计算机证明了四色猜想成立。1 9 9 3 年罗彻斯特理工学院的r a d z i s z o w s k i 和澳大 利亚国立大学的m c k a y 用计算机求得r a m s e y 数r ( 4 ，5 ) = 2 5 。我国著名数学家吴文俊、张 景中等用计算机进行了几何定理的机器证明，发展出一套成熟的机器证明的新理论与新 方法。 图论蕴涵着大量强有力的思想、漂亮的图形和巧妙的论证，即使是非常困难的尚未 解决的问题，它的表述也可能是平易近人的。现实生活中处处可以发现图论的难题，图 论是最接近百姓生活、最容易阐述的- 1 7 数学分支，具有实质性的难度又有简朴的外表 是很多图论问题的特点之一，使得每个搞图论的人在图论问题面前都必须谨慎严肃地思 考，它的证明往往需要极其繁琐的细节，并且往往需要艰苦的计算【7 1 。 图论与数学的其它分支不同，它不象数论、拓扑等学科那样有一套完整的理论体系 和解决问题的系统方法。图论所涉及的问题比较广泛，而解决问题的方法千变万化，非 常灵活，常常是一种问题一种解决方法，而这些方法之间又毫无联系。因此，解决图论 中的问题不仅需要知识，而且更需要智慧和灵活深入的思考。 f l o w e rs n a r k 图与k n s d e l 图的亲切素标号 从2 0 世纪6 0 年代之后，图论的算法受到了更多的重视【8 l 。算法的有效性一直困惑 着我们。例如我们建立了求两个项点之间最短路径的d i j k s t r a 有效算法，却建立不起来 求两个顶点间最长轨道的有效算法；也没有有效算法判别图的顶点是否全部处于一个圈 上，没有有效算法确定能否用三种颜色对地图正常( 邻国异色) 着色。在网络理论中，已 经有有效算法，把商品在铁路上由产地最快地运往销地，但对两个工厂产的两种商品， 分别运往各自的销地时，建立不了安排运输方案的有效算法，使得两个销地的需求同时 得以满足，等等。至今已积累了数以千计的实际问题，其数学模型是图论问题，但这些 问题皆未建立起有效算法。2 0 世纪8 0 年代，e d m o n d s ，c o o k 和k a r p 等发现，这批难题 有一个值得注意的奇特性质，如果这些问题中有某个问题不存在有效算法，则不能指望 这批问题中的任何一个存在有效算法了。这批问题组成的集合记成n p c ，或称n p 完全 问题。数学与计算机科学的最大挑战之一就是回答n p e 问题是否真的不存在有效算法。 如果一个带有顶点集y 的图存在一个从v 到 1 ，2 ，lv 1 ) 双射，：对每条最大公约数 g c d ( ( u ) 火v ) ) = l 的边标号为1 并且对最大公约数d 状甜) j 贝d ) 1 的边标号为0 ，则标号为 l 的边的数量和标号为0 的边的数量相差最多为1 ，这类图被称作有亲切素标号。 本文设计了计算机辅助下求解的k n o d e l 图和f l o w e rs n a r k 及其相关图的亲切素标 号，并用数学的方法给予了证明。 一2 一 大连理工大学硕士学位论文 1图论基础知识 1 1 图的基本概念 为了便于理解，先说明一下与本文相关的图的基本概念： ( 1 ) 图 一个无向图g 定义为一个二元组( 以d ，记作g = ( y 固其中肛坎g ) 是一个非空集 合，它的元素叫做项点；e w e ( g ) 是无序积v 和y 的一个子集合，它的元素叫做边，即 以回= ( “，v ) l u ，1 ，坎6 9 ) ，称为无向图g 的边集。集合y 中的元素在e 中出现可以不止一 次。 一一个有向图g 定义为一个二元组( 形d ，记作g = ( 形毋。其中肛坎g ) 是一个非空集 合，它的元素叫做顶点；e w e ( g ) 是有序积v 和y 的一个子集合，它的元素叫做边，即 以g ) = l 的边标号为0 ，则 标号为l 的边的数量和标号为0 的边的数量相差最多为l ，这类图被称作有亲切素标号。 一6 一 大连理工大学硕士学位论文 1 3 本文工作 针对图的亲切素标号的研究，本人完成的主要工作有： ( 1 ) 给出 f l o w e rs n a r k 图r 及其相关图g 的亲切素标号，从而证明 f l o w e rs n a r k 图及其相关图是亲切素标号图。 ( 2 ) 给出了k n 6 d e l 图职3 ，刀) 的亲切素标号，从而证明了k n 6 d e l 图职3 ，”) 是亲切素 标号图。 f l o w e rs n a r k 图与k n 6 d e l 图的亲切素标号 2f l o w e rs n a r k 图的亲切素标号 2 1f l o w e rs n a r k 图及其相关图的定义 g 是一个简单的非平凡的连通的三正则图，点集坎= b 6 “d j ：畦鳓一1 ) ，边 集以g ) = 即f + l ，b i b 川，c 矽州，咖 劬6 和f ：0 5 f 勤一1 ，点的标号对n 取模，玩可以通过 g 通过用边以1 c o ，“1 b o 来替换b i b o ，c n 1 c o 得到。如果以为奇数且力5 ，1 - 1 被称作f l o w e r s n a r k 图。其他的图，被称作f l o w e rs n a r k 图的相关图。见图1 1 。 g 5 g 5 ( 5 ) 图1 1f l o w e rs n a r k 图及其相关图 f i g 1 1 t h ef l o w e rs n a r ka n di mr e l a t e dg r a p h s 一8 一 大连理工大学硕士学位论文 2 2f l o w e rs n a r k 图及其相关图的亲切素标号 观察2 1 让x 是两个正整数，并且让卜一j ，i = 开硝z 开，其中p l 是不同的素因 子并且是其中的序列，如果对于1 s 母，x - c om o dp i 则x , y 互素。 定理2 1 对于所有n 3 ，q ( f t , ) 可亲切素标号。 证明：对于o i _ 4 n - 1 ，我们定义函数厂如下： 厂( 也) = f + 1 ， f + 2 ， i + 3 ， f + 4 ， f + 5 ， “6 ， ，1 , 8 ，3 , 1 ，5 ，7 ff - 9 f 暑1 1 ( m o d l 2 ) ； 0 ( m o d l 2 ) ； ( m o d l 2 ) ； ( m o d l 2 ) ； ( r o o d l 2 ) ； ( m o d l 2 ) q ( 见) 的边能被划分为六个子集： e l = 扣。v f + 4 ：0 f 4 n 一4a n df 兰0m o d4 e 2 = 扣，v i + 3 ：0 f 4 n 一4a n df 暑0m o d4 e 3 = 扣，+ i ，+ 3 ：0 f 4 n 一4a n df 三0m o d4 e j = v ；，：0 f 一4a n df 兰044n 4a n d0m o d4 4 2 p f + 2 h + 3 ： sis j 兰 e 5 = ，i + l v i + 5 ：0 f 4 n 一4a n d f 兰0m o d4 e = ，；：0 i 4 n 一4a n df 暑0 d44n4a n d0r o o d4 也62 川+ 2 匕“： ss l 暑 情况1 ：n - 三- 0 ( m o d3 ) 当o i _ 4 n 一1 ，石( 一) = 厂( _ ) 很容易证明石是一个从 y ( q ( 风) ) 至t j l ，2 ，4 n 的一一映射。 表2 1 是五( g ( 以) ) ，当n - 0 ( m o d3 ) 当i = 0 ( r o o d1 2 ) ，因为i f 0 ( v f ) - f o ( v “4 ) i = 2x3 ，f 0 ( v ，) 0 ( r o o d3 ) 和l ( v f ) 是奇 数，通过观察2 1 ，我们有厶( u 1 ，m ) = 1 当f - 4 ( r o o d1 2 ) ，因为l f o ( v , ) - f o ( v 州) l = 2 ，并且厶( ，) 是奇数，我们有f o o , , v m ) = 1 当i = 8 ( r o o d1 2 ) ，并且y c - 4 n - 4 ，因为i f o ( v ，) - f o ( v m ) i = 2 2 并r f 0 ( v , ) 是奇数，我们有 厶( 1 ，f + 4 ) = 1 当i = 4 n - 4 ，因为厶( v 。) = l ，我们有l o 4 ，o ) = 1 因此，在e 有疗条边标号为1 一9 一 f l o w e rs n a r k 图与k n s d e l 图的亲切素标号 当卢o ，4 ( m o d1 2 ) ，因为i 厶( u ) - a ( v f + 3 ) l = 2 2 并且厶( v j ) 是奇数，我们有 兀( ，1 ，m ) = 1 当i = 8 ( r o o d1 2 ) ，因为g c d ( f o o ，l 厶m ) ) 3 ，我们有厶( 匕1 ，m ) = o 因此，在e 2 有2 n 3 条边标号为1 和有刀3 条边标号为0 表2 1 f o ( q ( 见) ) ，当n 兰( m o d3 ) t a b 2 1 f o ( q ( 风) ) ，f o rn 三( m o d3 ) 当i = o ，4 ( m o d1 2 ) ，因为i 厶( ，州) - f o ( v m ) i = 3 并且厶( 咋) 0 ( r o o d3 ) ，通过观察2 1 ， 我们有f o ( v f + l ，m ) = 1 当卢8 ( m o d1 2 ) ， 为g c d ( f o 州l 厶m ”3 ，我们有厶( 一+ i + ，) = 0 因此，在毛有2 n 3 条边标号为1 和有n 3 条边标号为0 当i = o ，4 ( r o o d1 2 ) ，因为l 厶( v + 2 ) 一厶( ，“3 ) | = 1 ，我们有厶( h + 2 u + ，) = 1 大连理工大学硕士学位论文 当i = 8 ( m o d1 2 ) ，因为g c d ( f o m ) ；五m ) ) 3 ，我们有兀( v m ，m ) = 0 因此，在e 。有2 n 3 条边标号为1 和有刀3 条边标号为0 当i = 0 ，4 ，8 ( r o o d1 2 ) i ：4 n 4 ，因为g c d ( f o o f + 1 ) ，兀”2 ，我们有兀( v 川v m ) = 0 当i = 4 n 4 ，因为巩的g e d ( f o 。一，l y 0 6 , ：”2 ( 或g 。 g c d ( f o o 。一，l 兀“) ) 2 ) ， 我们有对于h 。，f o ( v 4 问1 ，2 ) = o ( 或对于瓯，f o ( v 4 帕v 1 ) = 0 ) 因此，在e ，有1 1 条边标号为0 当i = 0 ，4 ，8 ( r o o d1 2 ) i # - 4 n - 4 ，因为g c d ( f o o j + 2 ) ，兀( v j + 6 ) ) 2 ，我们有f o ( v + 2 ，f + 6 ) = 0 当i = 4 n - 4 ，因为以的g c d ( f o o 。二，) ，兀o ：”2 ( 或g 。的g c d ( f o ( v 4 n - 2 ) ，兀o 。) ) 2 ) ，我 们有对于日。，f o ( v 4 帕 ，1 ) = o ( 或对于瓯，f o ( 1 ，4 川，2 ) = 0 ) 因此，在尾有一条边标号为0 因此，在表2 1 定义的厶中，总共有3 刀条边标号为0 和3 疗条边标号为l ，即，兀是 当r r - 0r o o d3 时g 。( 日。) 的亲切素标号。 情况2 ：r r m l ( r o o d3 ) 。我们定义函数石如下： z ( ，。) = f ( v f ) ， 4 n 一1 ， 4 n 一2 ， 4 n ， 4 n 一3 ， 0 i 4 n 一5 ； i = 4 n 一4 ； i = 4 n 一3 ； i = 4 n 一2 ； f = 4 n 一1 当o i _ 4 n 一5 ，f o ( v , ) = f ( m ) ，f ( 4 n - 4 ) = 4 n - 1 ，f ( 4 n - 3 ) = 4 n - 2 ，f ( 4 n - 2 ) = 4 n ， f ( 4 n 一1 ) = 4 n 一3 很容易证明是一个从y ( q ( 风) ) 到 1 ，2 ，4 ”) 一一映射。 表2 2 是z ( g ( 日。) ) ，当n - 兰l ( m o d3 ) 当i = 0 ( m o d1 2 ) ，i 4 n - 4 因为( ，) 一石( ，f + 4 ) i = 2x3 ， 石( q ) 是奇数，通过观察2 1 ，我们有石( 一 ，m ) = 1 当i = 4 n - 4 ，因为a ( v o ) = 1 ，我f 门有a ( v 4 。一。) = 1 当= 4 ( m o d1 2 ) ，因为i 石( v ，) - a 0 j + 4 ) i = 2 并且石( _ ) 是奇数， 石( v f ) 0 ( r o o d3 ) 和 我们有a ( v ，) = 1 f l o w e rs n a r k 图与k n s d e l 图的亲切素标号 当i = 8 ( m o d1 2 ) ，因为i 石( ，。) - a ( v m ) i = 2 2 并且z ( v ，) 是奇数，我们有z ( q v ) = 1 因此，在巨有刀条边标号为1 表2 2 z ( g 。( 日。) ) ，当n - u = l ( m o d 3 ) t a b 2 2 石( g 。( h n ) ) ，f o r ，l 三1 ( r o o d 3 ) 当i = o ，4 ( m o d1 2 ) ，i 4 n - 4 ，因为阮( ，) 一石( ，帕) l = 2 2 ，并r l ( v ，) 是奇数，我们有 z ( v j ，m ) = 1 当i = 4 n - 4 ，因为( ，。) - a ( v m ) l = 2 ，并- r a ( v ，) 是奇数，我们有石( 1 ，m ) = 1 当i = 8 ( r o o d1 2 ) ，因为g c d ( 9 l o a z o m ) ) 3 ，我们有石( q 1 ，m ) = o 因此，在e ：有2 n 3 条边标号为1 和有n 3 条边标号为0 当i = o ，4 ( m o d1 2 ) ，i 4 n - 4 ，因为阮( + i ) - a ( v j + 3 ) l = 3 ，并且石( m ) 0 ( r o o d3 ) ， 通过观察2 1 ，我们有z ( 1 ，川_ + ，) = 1 大连理工大学硕士学位论文 当i = 4 n 一4 ，因为i 石( v 川) - zc v m ) l = 1 ，通过观察2 1 ，我们有石( v 川v m ) = 1 当i = 8 ( m o d1 2 ) ，因为g c d ( f i 0 ，+ 。) ；z o m ) ) 3 ，我们有z ( ，川1 ，m ) = 0 因此，在e 3 有2 n 3 条边标号为1 和有彬3 条边标号为0 当卢o ，4 ( m o d1 2 ) ，i 4 刀一4 ，因为i z ( v f + 2 ) 一z ( 1 ，h 。) i = 1 ，我们有石( ，+ 2 1 ，f + 3 ) = 1 当i = 4 n - 4 ，因为l z ( 1 ，m ) - z c v m ) i = 3 ，并且z ( 1 ，) 0 ( m o d3 ) ，通过观察2 1 ，我们 有z ( v 川1 ，f + 3 ) = 1 当i = 8 ( m o d1 2 ) ，因为g c d ( f 0 m ) 石o m ) ) 3 ，我f 门有z ( ，件：1 ，m ) = 0 因此，在e 。有2 n 3 条边标号为1 和有玎3 条边标号为0 当i = 0 ，4 ，8 ( r o o d1 2 ) i 4 n - 4 ，因为g c d ( f 。o 川x 石( v ) ) 2 ，我f 门有i ( ，m v ) = 0 当i = 4 n 一4 ，因为h 。的g c d ( f 。d 。一，) ，z 0 ：) ) 2 ( p s 戈g 的g c d “o 。一，) ，z ( v ，) ) 2 ) ，我们 有对于h 。，z ( ，4 棚1 ，2 ) = o ( 或对于g 。，石( ，4 棚 ，1 ) = 0 ) 因此，在e ，有甩条边标号为0 当i = 0 ，4 ，8 ( m o d1 2 ) i v 邑4 n - 4 ，因为g c d “o i + 2 l 石o m