（基础数学专业论文）循环的和1rotational图设计.pdf

循环的和1 - r o t a t i o n a l 图设计 中文摘要 设凰为n 阶完全图，g 为有限简单图，g d ( v ，g ) 表示虬的d 设计( 或g 分解) ( x ，8 ) 的一个自同构群n 是一个x 上的双射构成的群，这些双 射将b 中的区组映成它自己中的区组设n 是( x ，目) 的一个自同构群 若存在一个”阶的自同构”兀，则称( x ，舀) 是一个循环的图设计如 果”是一个”一1 阶自同构且具有一个固定点，则称b ) 是1 r o t a t i o n a l 的 循环的和1 - r o t a t i o n a l 图分解比图分解的研究难度要大图设计问题 在试验设计和编码方面都有重要应用，因此受到人们的广泛 关注人们较早研究的是完全图分解为小阶数的完全图问题和 完全图分解为圈的问题，并且大多是研究特定的图的图分解 问题。我们在前面研究的基础上讨论循环的和1 - r o t a t i o n a l 的图分 解问题并且侧重于研究一类图的循环和1 r o t a t i o n a l 图分解问题和 一般的构造方法本文共有四节，第一节介绍了图设计，循环的 和1 一r o t a t i o n a l 图设计研究进展和应用背景，也给出了一些有用结论； 第二节给出了完全图分解为二部图的构造方法和一般循环图分 解的构造问题扩展了胁a 在文献1 1 8 】中的结果，得到更一般的定 理；第三节中用c g d d ，c b i b d 和标号法讨论了l - r o t a t i o n a l 图分解的构 造问题；第四节给出了以上结果的应用，研究了完全图循环分解 为单圈图问题 关键词：图设计；循环图设计；1 - r o t a t i o n a i 图设计；h g d ；i g d a b s t r a c t 风b et h ec o m p l e t eg r a p h 。a n dgaf i n i t es i m p l eg r a p h ，ag - d e s i g no fa 凰i s d e n o t e db yg d ，g ) ( o rg r a p hd e c o m p o s i t i o no fk j ) l e tnb e 趾a u t o m o r p h i s m g r o u po fag r a p hd e c o m p o s i t i o n 召) ，t h a ti s ，ag r o u po fp e r m u t a t i o n so nt h e s e ty o f p o i n t sl e a v i n gt h ec o l l e c t i o no fb l o c k s 移i n v a r i a n t i ft h e r ei sa na u t o m o r p h i s m o fo r d e r ，t h e nt h e 聊i ss a i dt ob ec y c l i c t h ed e c o m p o s i t i o n ( 磊，功h a sa n a u t o m o r p h i s m 盯= = ( o ，1 ，2 ，t ，一1 ) i f7 r hi s a na u t o m o r p h i s mo fo r d e rt ，一1 w i t ha 咄f i x e dp o i n t ，t h e nt h e ( x ，功i ss a i dt ob e1 - r o t a t i o n a l t h ec y c h ca n d 1 - r o t a t i o n a lg r a p hd e c o m p e s i t i o n si sm o r ea 1 1 c u l tt h a nt h eg r a p hd e c o m p o s i t i o n t h ea p p l i c a t i o no ft h eg r a p hd e s i g np l a y sa ni m p o r t a n tr o l ei nt h ee x p e r i m e n td e s i g n a n dt h ec o d i n g s oi th a sa r o u s e dg e n e r a la t t e n t i o n a tt h ee a r l ys t a g et h ep e o p l e s t u d i e dt h ep r o b l e ma b o u tt h ec o m p l e t eg r a p hd e c o m p o s i n gi n t ot h ec y c l e so rt h e c o m p l e t eg r a p h sw i t hs m a l lo r d e r a n dm o s to ft h eg r a p h sa 托s p e c i f i c o nt h e b a s i so ft h ef o r m e rr e s e a r c h ，w em a i n l yd i s c u s st h ec y c l i ca n dt h e1 - r o t a t i o n a lg r a p h d e c o m p o s i t i o n s ，a n dw ee m p h a s i z eo nt h eg e n e r a lc o n s t r u c t i o nm e t h o d s t h i sp a p e r h a sf o u rs e c t i o n s i nt h ef i r s ts e c t i o n ，w ei n t r o d u c et h eb a c k g r o u n da n dd e v e l o p m e n t a b o u tt h eg r a p hd e s i g n s ，c y c h ca n dl - r o t a t i o n a lg r a p hd e s i g n s a n dw eg i v es o m e c o n c l u s i o n s i nt h es e c o n ds e c t i o n ，w en o to n l yo b t a i nt h ec o n s t r u c t i o nm e t h o d so f t h ec o m p l e t eg r a p hc y c l i cd e c o m p o e i n gi n t ob i p a r t i t eg r a p h ，b u ta l s og i v et h ec o n - s t r u c t i o nm e t h o d sa b o u tt h eg r a p hw i t h7 - l a b e l i i n g i nt h et h i r ds e c t i o n ，w ed i s c u s s t h ec o n s t r u c t i o np r o b l e m so ft h e1 - r o t a t i o n a lg r a p hd e c o m p o s i t i o n s i nt h ef o u r t h s e c t i o n ，w e d ot h er e s e a r c ho nt h ep r o b l e mo ft h ec o m p l e t eg r a p hd e c o m p o s i n gi n t o t h eu n i c y c l i c 露a p h 8 ， k e yw o r d s ：g r a p hd e s i g n ；c y c l i cg r a p hd e s i g n ；l - r o t a t i o n a lg r a p hd e s i g n ；h g d ；i g d 1 引言 1 本文考虑的图g 是没有孤立点的简单图设”为正整数，g 为( p ，g ) 图， 凰表示 阶完全图图日的g 设计( 也称为图分解) 是日的子图的集合( 叫做 区组集) ，其中每个子图与g 同构，且它们构成日的边划分通常将日的g - 设 计表示为g i h 当日= k ，时，g i h 表示为g d 扣，g ) 当g = k 。时，一个g d ( v ，g ) 表 示为( 口，n ，1 ) 一b i b d 若x 和8 分别是凰的点集和g d 扣，g ) 的子图的集合，我 们也用僻，8 ) 表示g d ( v ，g ) ( x ，8 ) 的一个自同构群n 是一个x 上的双射构 成的群，这些双射将舀中的区组映成它自己中的区组设n 是( x ，t 3 ) 的一 个自同构群若存在一个u 阶的自同构，r ，则称( x ，召) 是一个循环的 图设计如果霄是一个t ，一l 阶自同构且具有一个固定点，则称( x ，召) 是1 - r o t a t i o n a l 的对于1 - r o t a t i o n a l 的g d ( v ，g ) 点集x 等于磊一lu o o ，此时 r 可以写 成( o o ) ( o ，1 ，2 ，钉一1 ) 设b 是具有l r o t a t i o n a l 的g d ( v ，g ) 的一个区组，那么b 的 区组轨道定义为 b + x l x 磊一l 一个区组轨道的基区组是其中任意一 个区组任意一个1 一r o t a t i o n a l ( 或循环) 的6 1 d ( v ，g ) 都可以由基区组生成在 设计理论中，一个重要问题是图设计的存在谱问题，也就是当t j 取什么值 时g d ( 甜，g ) 存在? 人们首先讨论了完全图分解为小完全图的图分解问题 如g 为小于6 个顶点的完全简单图( 见【1 】和【1 7 ) ，其它不超过9 个顶点的完全简 单图( 见【1 7 j ) 等对于些特殊的图，如g 为星图( 觅 2 1 ) 、路( 见【1 j ) 和圈这个闯 题已解决a l s p a c h ，g 删z 口s ( 见【1 0 】) 和锄帆( 见【2 2 】) 得到下面的圈设计定理： 定理1 1 设j 为一个j 一因子， ( 1 ) 对正偶数他，3 m n ，图k j r 可以分解成m 长圈当且仅当一，的 边数是m 的倍数 ( 2 ) 对正奇数他，3 s m 馆，图蚝可以分解成m 长圈当且仅当的边数 是m 的倍数 关于非完全图的g - 设计也已经研究，如当g 和曩均为完全二部图的设 计( 【3 】) 再如当日为一个带有n 长洞的完全图，即凰，d o y e n 和w i l s o n 首先 考虑了对g = 砥的情况( 【4 1 ) 当g 为m 圈，靠s6 ( ( 5 ，6 ，7 8 】) ，和g 为恐增加一条 悬边( 【9 】) 时，关于带洞的g - 设计已经得到 对于其它各种小阶数图的分解问题，如4 点及其以下的图分解已 经基本得到解决见文献【l ，2 】在【1 1 】中，b e r m o n 以等人解决了大部分5 点 图的g 一设计存在性的充要条件y i n 1 2 讨论了对允许的t ，g d ( v ，g ，1 ) 的 2 存在性，l i a n g ( 1 3 ，1 4 】) 讨论了对允许的口，当g 有六个顶点至多六条边时， g d ( v ，g ) 的存在性仅表示n 长圈，冠图q 。由n 长圈的每个顶点各连接一条 悬边而得到文献【1 5 】中给出了当n = 3 ，4 ，5 ，6 ，8 时g d ( v ，队) 存在的充要条件 循环的和1 r o t a t i o n a l 图分解闯题比图分解问题更难关于循环s t e i n e r 二设计问题的研究进展如下所述c h e n 和w e i 在【3 l 】中讨论了循环 ，4 ，1 ) 一 b i b d 的存在性( 其中郇= 1 搿+ 4 ，3 t 5 0 ) 并且给出了一些递归构造方法和 在光正交码方面的应用b u r a t t i 在f 3 2 l 中给出了循环( 勿，4 ，1 ) b i b d 的存在 谱m o r a l e s 在【3 3 】中给出了循环p b i b d ( 2 ) 的3 2 个设计其它区组尺寸是4 或大 于4 的循环参设计见文献f 删关于1 - r o t a t i o n a l 设计见文献f 4 1 4 3 】关于此类 问题比较好的结果是： 定理1 2 阻廖4 一毒刚御存在循环的s t s ( v ) 当且仅当移1 ，3 胁甜矽并 且t ，9 j 阳，1 - r o t a t i o n a lt , v ( v ，a ) 存在当且仅当 ( 1 ) 、= i 三3 。9 ( m o d 钵) ； 例a 三1 ，5m 甜砂，a l 且u 三1 ，3 细耐砂， 例a 耋2 ，4 删劬t ，兰0 ，1 细耐劬 俐a 暑3 阳甜砂，t ，兰1 阳耐砂， f 5 x 兰0 m o d6 ) 。v 2 3 循环的俑t 胁圈系问题引起很多学者的研究兴趣当m = 3 ，5 ，7 时，循 环胁圈系问题已解决( 见【2 3 】和f 2 4 】) 当m 为偶数并且t ，三1 ( m o d2 m ) 和m 兰0 ( r o o d4 ) 时，循环m 圈系在 2 5 1 中被构造当m 兰2 ( m o d4 ) 时，循环m - 圈系在文 献【2 4 1 中被构造关于循环僻圈系的构造，当m 为奇数并且甜暑1 ( r o o d2 m ) 时， 见文献 2 6 - 2 8 1 ；当t ，三m ( m o d2 m ) 时，见文献【2 9 】b r y a n t 等人( 见 3 0 1 ) 用差方法 得到了当t ，三1 ( r o o d2 m ) 并且 m 4 时循环t ，阶胁圈系的存在谱也解 决了当m 为奇数并且t ，兰2 ( r o o d2 m ) 时凰一f 的循环胁圈系的存在问题，这 里f 为凰的1 - 因子最近b l i n c o 等人( 见【1 9 】) 研究了完全图循环分解为几乎二 部图问题 我们很容易得到以下定理： 定理1 3 设g 为慨g ) 图，若存在g d ( v ，g ，a ) ，则 0 ) 口2p ； ( i ) a 材( t ，一1 ) e0 ( r o o d2 q ) ； ( i i i ) a 一1 ) e0 ( m o dd ) ，这里d 为g 的顶点度的最大公约数 循环设计在光正交码方面有重要应用( 见【1 6 】) 设和k 是正整数，一个 3 长度为 重量为k 的( 0 ，1 ) 序列( 也称为码字) 是一个恰有k - j 、。l 和t ，一詹们的序列 一个长度为 重量为k 的( 0 ，1 ) 序列的集合c 若满足 ( 1 ) ( 自相关性) 对任意。= ( 知，l ，一1 ) c 和对任意整数i 0 ( m o d ) 有 0 】二o t s 口一11 z t + 1 ； ( 2 ) ( 交叉相关性) 对任意满足$ 暑，的茁= ( 知，$ 1 ，1 ) c 和y = ( y o ，玑，蜘一1 ) c ，以及任意整数 有o t 。一l x t y t + is 1 则称c 为光正交码，记为扣，k ，1 ) - 0 0 c 通过计算可知一个( 移，奄，1 ) 一o o c 的大 小不超过【蒜南j 若一个( t ，k ，1 ) 一o o c 达到这个上界，则称之为最优的例 如一个循环的( 1 慰+ 4 ，4 ，1 ) 一b i b d 导出一个最优的( 1 盘+ 4 ，4 ，1 ) 一d d c 本文将在如上成果的基础上研究完全图( 循环或1 r o t a t i o n a l ) 分解为二 部图和单圈图问题 本文共有四节，第一节介绍了图设计，循环和1 r o t a t i o n a l 图设计进展和 应用背景，也给出了一些有用结论；第二节给出了完全图分解为二部图的 构造方法和一般循环图分解的构造问题；第三节讨论了1 r o t a t i o n a l 图分解 的构造问题；第四节研究了完全图循环分解为单圈图问题 为了方便起见，本文常常使用如下符号：猿示全体整数集，当口，b z 时， 陋，b l 表示 茁z la z 6 ，【口，b l k 表示 z i 茹互a z 6 ，茹i 口( 竹加l d 后) ) ，【叫 表示满足s ，2 的最大整数y 当s 是一个集合时，用，( s ) 表示集合 ，( 甸l 茹 毋，用( d ，b ，c ) + i 表示( 口+ ，b + i ，c 4 - t ) ，并且( 磊k = li 么1 2 循环图设计的构造 设g = 2 ) 是简单的函，q ) - 图，如果存在单射夕：v ，1 0 ，田，使得诱 导映射矿( 伽) = l g ( t ) 一g ( v ) l ，v u t ，e 是e 到【1 ，口】上的双射，则称g 是g 的优美 标号，g + 是g 的边标号，并称图g 是优美的设g 为g 的优美标号，若存在常 量b ，使得对每个伽e 都有9 ( t ) b b ，删e ) ，则( a 丑) 是g 的二分划，称之为g 的 平衡二分划如果存在单射g ：v 【o ，2 口】，使得 m l 住 i 夕( 一夕( t ，) i ，2 94 - 1 一i g ( t ) 一g ( ) i ) i 删e = 【1 ，讲，则称g 是g 的p 标号设七是正整数，如果存 在单射夕：v 一 o ，1 ，2 ，l e i + 七一1 ) ，使得导出映射g + ( t ) = 1 9 ( “) 一9 ( t ，) i 对删e 是f 一 知，七+ 1 ，k + 2 ，l e i + k 1 ) 的双射，则称夕是g 的肛优美标 号若g 对所有正整数七都是缸优美的，则称g 是任意优美的 下面我们用d g 表示将图g 中的每条边伽用弧( “， ) 和( t ，“) 代替后而得 循墨笃和l o r o t a t i o n a l 图设计 4 到的图设g = ( k e ) 是二部( p ，口) - 图，并且具有二分划( a ，口) 如果存在单 射9 ：v 【0 ，2 9 】，使得9 ( 妨一9 ( ( r o o d2 q + 1 ) 跑遍d g 中弧是不同的，并且 当a ，口b 且伽e 时有夕( u ) g ( 口) ，则称g 是g i 拘t 标号 由上面的定义容易得到平衡图是优美图；平衡图是任意b 优美的； 优美图有矿标号；有t 标号的二部图也有p 标号但优美图与有t 标号的图 不能互推 引理2 1 设( a ，b ) 是二部p ，口) 一图g = 似司的二分划如果存在满足条 件v ( 口) ，( 对于o a ，b b ”的单射，：v 【o ，矧，使得 ，( 6 ) 一，( d ) i ，d a ，6 b ，曲e ) = f 1 ，垡】，则，是g 的7 标号 证明：因为- - i ( r o o d2 , 1 + 1 ) 与2 q + 1 一i ( r o o d 幻+ 1 ) 是相同的，所以集 合 ，( 6 ) - f ( 口) ( r o o d2 9 + l ，( - f ( 6 ) ( m o d 幻+ 1 ) id a ，b b ，a b 刀= 1 1 ，2 q 故，是g 的t 标号 口 引理2 2 ( r o s a p s ) 设g = ( k 习是简单的函，d 一图则一个o g d ( 2 q - i - 1 ，g ) 存在当且仅当g _ 有p 一标号 定理2 1 若存在循环的g d ( v ，日) ，并- 臣g i h ，则存在循环的g d ( v ，g ) 证明：设循环的g d ( v ，日) 的基区组集合为日由于g i h ，所以8 中每个元 都可分解为若干个同构于g 的子图设一4 是将b 中所有元分解为同构于g 的 予图的集合，则以一4 为基区组可形成一个循环的g d g ) d 设( a ，b ) 是二部( p ，g ) 一图g 的二分划，( a ，b ) 是二部图g 的二分划，t 【l ，川 若岛同构于g ，我们可以构造一个具有二分划，唣1 鼠) 的图g 似一n b ) ，其 点集为a u ( u 鳌1 且) ，边集为u 叁l e ( g ) 定理2 2 设，b ) 是二部p ，g ) 一图g 的二分划并且供有7 标号，则图g 阻一 n b ) 也具有7 - 标号 证明：设，是g 的一个t 标号，a = a 1 ，a 2 ，吼) ，b # b l ，6 2 ，吣， 晟= 玩l ，b , 2 ， ，i 【1 ，川由定义可知s + t = p ，图g ( a n b ) 有5 + t l 个点 和n q 条边，下面我们构造图g ( a n b ) 的一个t 标号9 ：当z a 时9 ( z ) = ，( z ) ， 当且时夕( ) = ，( b ) + 2 q ( i 一1 ) 对于i 【1 ，叫可以验证夕是从图g ( a n b ) 的点集到集合1 0 ，2 删的一个单射 对于g ( a n b ) 的每条边n b ( 其中口锄显然有g ( n ) 9 ( b , d 下面我们验 证如果( t ，t ，) 和( z ，! ，) 是g ( a - - n b ) 的满足g ( u ) - g ( v ) 三g ( z ) 一夕( 暑，) ( r o o d2 q n + 1 ) 的 任意两条弧( 其中q ，茁a ) ，都有心口) - ( z ，彩下面我们分三种情况证明 情形( 1 ) 若u ，y 晟，则由g 的定义和条件g i 笪g 可知，只有( t ， ) = ( z ，! ，) 情形( 2 ) ( 反证) 假若t ，鼠，暑，最；且i m 设t ，= ，= 由已知得 循环的和l - r o t a t i o n a l 图设计 5 9 ( b ) 一9 ( 1 i ) 兰士0 ( 6 竹墙) 一g ( z ) ) ( r o o d2 r u + 1 ) 因此有 f ( b j ) + 2 q ( i 一1 ) 一，( t ) 兰士( ，( k ) + 2 q ( r n 一1 ) 一，0 ) ) ( r o o d2 n q 4 - 1 ) ( + ) 如果上式右边取”一”则有 ，( 幻) 一f ( t ) + ，( k ) 一，( 善) + 2 q ( i + m 一2 ) 暑0 ( r o o d2 n q + 1 ) 由午标号的定义可得 0 f ( b a 一，) + ，( “) 一，( 甸+ 2 q ( i + m 一2 ) 4 n q 2 ( 2 r 崦+ 1 ) 从而有，( 6 j ) 一，( t ) + ，( 6 ) 一，( ) + 2 q ( i + f n 一2 ) = 2 n q + 1 又因为2 q i ( f ( b j ) - f ( u ) + f ( b k ) - f ( x ) - z ) ，所以只有f ( b j ) - - f ( u ) l - f ( k ) - - f ( x ) - l = 2 q ， t 那f ( b j ) 一，( 兰f ( b k ) 一f ( x ) ( m o d2 q + 1 ) 这与，是g 的t 标号矛盾所以( 水) 右 边取”一”不行 若( + ) 右边取”+ ”则有 ( f ( b j ) 一，( 札) ) 一( ，( k ) 一，( 。) ) + 2 q ( i m ) 三0 ( r o o d2 n q + 1 ) ( + 4 ) 而i ( ，( ) ，( “) ) 一( f ( b k ) 一，( z ) ) + 2 q ( i m ) i 2 q n ，所以( 料) 意味着( f ( b j ) 一 ，( u ) ) 一( f ( b k ) 一，( z ) ) + 幻g m ) = 0 因此幻i ( ，( b ) 一，) 一f ( b k ) + ，( $ ) ) ，所以 只：有f f ( b j ) 一f ( u ) - = - f ( b k ) 一，扛) 从而有t = z 且口= 可，即l ；m ，矛盾因此( 宰) 右边不 能取 + ” 情形( 3 ) 如果( 让，口) = q ，) ，彩= ( b ，n ) ，此时的夕( 秽) 一譬( 让) 兰( 们一g ( z ) ) ( r o o d2 n q + 1 ) 变成2 ( f ( b j ) 一，( 口) ) + 4 9 0 1 ) 量0 ( r o o d2 n q + 1 ) 但是o ( f ( t , d 一，( o ) ) + 2 q ( i 一1 ) 2 q n ，所以上面同余式不可能成立综合上述可得 映射g 是图g ( a 一佗b ) 的一个t 标号 凸 定理2 3 如果二部( p ，q ) r g - 7 一标号，则对任意正整数佗，存在c g d ( 2 n q + 1 ，g ) 证明：由定理2 2 可得图g ( a - n b ) 也有t 标号再由引理2 2 ，存在c g d ( 2 n q + 1 ，g 似一r i b ) ) 又因为g g ( a r i b ) ，所以存在c g d ( 2 n q + 1 ，g ) 0 定理2 4 若g 是平衡图，则对所有的正整数n ，存在c g d ( 2 q n + 1 ，g ) 证明：因为一个平衡图是一个二部图，所以由平衡图和具有t 标号图 的定义可得此定理 口 由定理2 3 - f 知，只要知道一个二部( p ，口) 一图g 具有卜标号，则它就有 c g d ( 2 n q - 4 - 1 ，g ) 下面我们主要研究具有t 标号图的构造问题这样可以 得到很多图的循环分解 设( ，) 和( w 1 ，w 2 ) 分别是二部图g 1 和g 2 的二分划，g l 和g 2 的弱t e n s o r 积 是一个具有二分划( k w 1 ，k w 2 ) 的二部图，记为岛og 2 满足下面条件： 6 若两点( u l ，t t ，1 ) 和( t ，2 ，w 2 ) 相邻当且仅当t ，1 与t j 2 在g 1 中相邻并且叫l 与弛在g 2 中相 邻设图g 是一个( p ，口) 一图 定理2 5 阻胆j 若图g 1 和g 2 都有n 标号，m , j a l 圆g 2 也有口_ 标号 对任意满足1 t p 的整数t ，用g 表示给图g 的t 个点每点添加一条 悬边而得到的图 定理2 6 设k 。是完全二部图则图k 热有7 - 标号 证明：设。的二分划为似，固，这里a = 口l ，a 2 ， ，b 一 矗1 ，6 2 ，6 h ， 并且假设m ，1 设在啦处新增悬边的另一个端点为戤j ，所有这些有新增 悬边的点啦的下标为t 1 ， 2 ，主4 并且满足i l i 2 霜设在玩处新增悬 边的另一个端点为鼽j ，所有这些有新增悬边的点的下标为歹l ，如，矗并 且满足t l i 2 轨+ a + 2 b + 3 ，口一1 0 ，2 n + 口+ b 一1 2 n + 口+ b 和6 n + 口+ b 6 n + 口+ 2 b + 3 因此9 是一个单射且9 ( y ( g ) ) 【o ，2 ( 4 n + d + 6 + 2 ) j 设x = t 巧悼【1 ，s 】，歹 f 1 ，m 】) u b ，y = f t ，忙p + 1 ，8 + 吼j 【1 ，m i ) u a 则扫( ) 一9 0 ) 陋x 暑， y - - 1 ，4 n + 2 - t - o + 6 】这意味着g ( u ) 一9 ( 茁) ( r o o d2 ( 4 n + 2 + 口+ b ) + 1 ) 是不同 的当们跑遍e c d g ) 中的弧时故g 是g 的一个7 - 标号 口 定理2 1 0 阻廖铆以，设g 具有二分划( x ，y ) ，乃是一个从巧= 协l 协2 ，劬i y i ) 到k 歹一l ，2 ，n 的双射m g ( x u l g s 。巧) 表示点集为x u ( u l g 。巧) ，并且 您忽 1， 妣扛卜 一 + + +0 轨饥饥 = 吩八 循环的扣1 - r o t a t i o n a 2 图设计 9 两点x 乖哪巧0 = l ，2 ，n ) 有边当且仅当u 办( t ，) e ( g ) ( x 。y ) 是平衡 图g 的平衡二分划，则g ( x u 1 9 s 。巧) 是平衡的j 例当竹三0 细硝缈，t 4 时c 等。是平衡的；俐当m 2 时，篇“是平衡的j 似，龙 图g p m 是由路的一个端点与g 上一点相连而得到的图当n 兰0 细o d ，m 2 时，g 露和它的冠图是平衡的 定理2 1 1 设鲰是图g 的一个口标号，其临界值为c ，i = 1 ，2 ，n g 是 将q 中标0 的点与q 一1 中标q l 的点重合， = 2 ，3 ，n 而得到的图则g 有口一标 号 证明；当行= 2 时，设鳓是慨，茹一图g 的标号，( a ，鼠) 是g 的平衡二分划，则 下面函数9 是g 的一个标号当z a l 时夕( ) = 吼( 茁) ，当写a 2 u 3 2 时g ( z ) - - - - 9 2 ( = ) 4 - c l ，当$ 岛n c 9 0 ) 劫缸) + 啦由数学归纳法可得此定理 口 定理2 1 2 设g 是g 的a - 桶i 号， 是日的