（应用数学专业论文）some+factorizations+of+complete+bipartite+graphs.pdf

s o m ef a c t o r i z a t i o n so fc o m p l e t eb i p a r t i t eg r a p h s 孙霓刚 摘要 “表示完全二部图，其两个点集分别具有m 和n 个点。 凡。表示 完全二部多重图，它是由丘的每条边重复a 次得到的设f 是 k 。 的一个生成于图，如果f 的每个分支均是k i , k ，我们称f 是a k m 。的一个 z t 一因子如果a k 。的边集可以划分为 ，。的k l f 因子，则称a f 。 存在 f 。k 因子分解以k 1 , k 中唯一的度为k 的点为尾，以其他点为头，对 硒t 进行定向，则得到有向图k ：k 将, k k 。，。的一个k 1 k 一园子中的每一个 分支均替换为耳；，我们就得到了 。的一个；b 一因子同样的，我们 可以定义a ，。的一个研 一因子分解 本文主要研究 k 。的因子分解问题首先，我们给出了 ，f m ，。存 在硒 因子分解的个必要条件，其中是任意正整数其次，当a 一 1 ，p ，p e 的时候。我们给出了 。存在两一目子分解的一个充分条件， 这里p 是任意素数，e 是任意正整数然后，我们讨论了 。的k ，。一圈 子分解问题，这里p 和是任意两个不同的素数并当a = l ，p p q 时给 出了a k 。存在k l 。一因子分解的一个充分条件。最后，当p 是素数时，我 们研究了，。的一种受限制的k f ，因子分解问题，并对有一个点受限制 的情况给出了一个充分条件 关键词完全二部多重图，k 1 一因子分解，k 1 。因子分解，受限制的凡：。一 因子分解 s o m ef a c t o r i z a t i o n so fc o m p l e t eb i p a r t i t eg r a p h s 孙霓刚 a b s t r a c t l e t mnb eac o m p l e t eb i p a r t i t eg r a p hw i t ht w op a r t i t es e t sh a v i n gm a n dnv e r t i c e sr e s p e c t i v e l y , k m ，ni st h em u l t i g r a p ho b t a i n e df r o m lb y r e p l a c i n ge a c he d g eeo f nb yas e to f e d g e sa l lh a v i n gt h es a l i ee n d v e r t i c e sa se ak 1 k 一 a c t o ro fa ni sas p a n n i n g s u b g r a p hf o fa k m s u c h t h a te v e r yc o m p o n e n to ffi sa k i k a 1 k 一 a c t o r i z a t i o no fa 叫i sas e to f e d g e - d i s j o i n tk i ，k 一 a c t o r so f ，nw h i c hp a r t i t i o nt h es e to fe d g e so f k m w ec a l lt h eu n i q u ev e r t e xw h i c hh a sd e g r e eki n 耳l ，a st h er o o to fk 1 i w ed i r e c te a c he d g eo fk 1 f r o mt h er o o tt ot h eo t h e rv e r t e x ，t h e nw eg e ta n o r i e n t a t i o no fk i ，k ，d e n o t e db yk ；k i fw e r e p l a c ee v e r yc o m p o n e n to fak l 一 f a c t o ro f ，柚y 耳；，t h e nw e g e ta 蜓, - f a c t o ro fa m 。a st h es a l l e ，w e c a nd e f i n ea ；k f a c t o r i z a t i o no fa ” i nt h i sp a p e rw ef o c u so ns o m e s p e c i a lf a c t o r i z a t i o n so fa nf i r s t ，w e g i v ean e c e s s a r yc o n d i t i o nf o rt h ee x i s t e n c eo ft h ek 1 ，k f a c t o r i z a t i o no fa k m n ，w h e r e i sa n yp o s i t i v ei n t e g e r s e c o n d ，w h e na = 1 ，p ，p 。，w eg i v ea s u f f i c i e n tc o n d i t i o nf o rt h ek 1 p c f a c t o r i z a t i o no fa k m ，nt oe x i s t ，w h e r ee i sa p o s i t i v ei n t e g e ra n dpi s8p r i m en u m b e r a f t e r w a r d s w ed i s c u s st h ek i 口。 f a c t o r i z a t i o no f w h e r e pa n dqm t w od i s t i n c tp r i m en u m b e r s a n d w eg i v eas u 币c i e n tc o n d i t i o nf o rs u c haf a c t o r i z a t i o nt oe x i s ti nt h ec a s eo f a = 】，n 吼wf i n a i i y , w ef o c u so nak i n do fr e s t r i c t e d 影j 。蠡c t o r i z a t i o n so f k 舢，w h e r epi s ap r i m en u m b e r 。a n dg i v eas u m c i e n tc o n d i t i o nf o rs u c ha f a c t o r i z a t i o nt oe x i s tw h e no n ev e r t e xi sr e s t r j c t e d 。 k e y w o r d s ：c o m p l e t e b i p a r t i t e m u l t i g r a p h ，k 1 r f a c t o r i z a t i o n ，矗】m 一 a e t o r i z a t i o n r e s t r i c t e d 耳；, p - f a c t o r i z a t i o n s n t l 】h c i o li z a t i o n so fc o m p l e t eb i p a r t i t eg r a p h s孙霓刚 1 i n t r o d u c t i o n l e t b e a c o m p l e t eb i p a r t i t eg r a p h w i t ht w op a r t i t es e t sh a v i n gi na l l d nv e r t i c e sr e s p e c t i v e l yl e t ，ib eap o s i t i v ei n t e g e r 0 疗二。i st h em u l t i g r a p h o b t a i n e df r o mk m nb yr e p l a c i n ge a c he d g eeo fk m nb yas e to fae d g e sa l l h a v i n gt h es a m ee n dv e r t i c e sa se a ne x a m p l eo fa ni s2 飓4 2 k 2 4 i ti sc l e a rt h a tag r a p hw i t hn oi s o l a t e dv e r t i c e si su n i q u e l yd e c i d e db yt h e s e to fi t se d g e ss oi nt h i sp a p e r ，w ec o n s i d e rag r a p hw i t hn oi s o l a t e dv e r t i c e s t ob eas e to f2 - e l e m e n ts e t so fi t sv e r t i c e s l e t b eap o s i t i v ei n t e g e ra k l 一 f a c t o ro fa 耳m ，ni sa s p a n n i n gs u b g r a p hf o fa k ms u c ht h a te v e r yc o m p o n e n t o ffi sak i ，a 1 ，k f a c t o r i z a t i o no fa ，ni sas e to fe d g e d o i n tk j e f a c t o r so f ”w h i c h p a r t i t i o nt h es e to fe d g e so fa nw e c a l lt h eu n i q u e v e r t e xw h i c hh a sd e g r e eki nk i ka st h er o o to fk 1 k i fw ed i r e c te & c he d g e o fk 1kf r o mt h er o o tt ot h eo t h e rv e r t e x ，t h e nw eg e ta no r i e n t a t i o no fk 1k d e n o t e db y 盯i 女i fw er e p l a c ee v e r yc o m p o n e n to ia k i 一i a c t o ro fa x m nb y ；k t h e n w eg e ta ；, k - f a c t o ro fa k m a st h es a m e ，w ec a nd e f i n ea 耳k f a c t o r i z a t i o no fa k a 12 f a c t o ro f2 k 24 1 1 卜 1 人 ak i 2 一f a c t o r i z a t i o no f2 k 2 ，1 s o m ef a c t o r i z a t i o n so fc o m p l e t eb i p a r t i t eg r a p h s孙霓刚 k i ，2 a o l 2 - f a c t o ro f2 恐4 耳；2 1 入n 1 入 a ；2 - f a c t o r i z a t i o no f2 k 2 4 f a c t o r i z a t i o n so fg r a p h sh a sb e e ns t u d i e db ys e v e r a lr e s e a r c h e r sb e c a u s e o fi t sg r e a tu s ea sw ek n o w ng i r l s k i r k m a ns c h o o lg i r l p r o b l e mi se q u i v a l e n tt or e s o l v a b l e ( n ，3 ，1 ) b i b d a n ds t u d y i n gf a c t o r i z a t i o n so fg r a p h sc a l l d og r e a tg o o dt ot h er e s e a r c ho nr e s o l v a b l e ( n ，a ) - b i b d f u r t h e r m o r e ，t h e 耳1 k f a c t o r i z a t i o no f nc a l lb ea p p l i e dt oc o m b i n a t o r i a lm u l t i p l e v e l u e d i n d e x f i l eo r g a n i z a t i o ns c h e m e so fo r d e rt w oi nd a t a b a s es y s t e m s ( s e e 【4 j ) t h e r ea r em a n yr e s u l t sa b o u t 所k f a c t o r i z a t i o no fa n w h e nk = 2 ， t h ee x i s t e n c eo f k i 2 一f a c t o r i z a t i o no f m nh a sb e e nc o m p l e t e l ys o l v e db yu s h i o t h e o r e m1 1 ( u s h l o ( 2 】) mh a sap 3 - i n c t o r i z a t i o ni fa n do n l y 矿( 1 ) m + n 三0 ( m o d3 ) ，( 2 ) m 2 n ，( 3 ) ns2 ma n d ( 4 ) 3 m n 2 ( m + n ) i sa ni n t e g e r w h e nk = 4 ，s u c hap r o b l e mh a sb e e np a r t l ys o l v e d i np a p e r 【5 1 ，u s b i o g i v eas u f f i c i e n tc o n d i t i o nf o rk 14 - f a c t o r i z a t i o no f n t oe x i s t t h e o r e m1 2 ( u s h i o 5 ) ，nh a s 。k 1 4 - i n c t o r i z a t i o n 玎( 1 ) m 茎4 n ( 2 ) n 4 m ( 3 ) 4 m n 兰4 n m 三0 ( r o o d1 5 ) a n d ( 4 ) ( 4 m 一凡) ( 4 n w t ) 三0 ( m o di s 0 ( m4 - n ) ) w h e n i sap r i m en u m b e rp h a sb e e np a r t l ys o l v e di np a p e r 6 f a c t o r i z a t i o nt oe x i s t t h ep r o b l e mo fk 1 p f a c t o r i z a t i o no f 凡，m ，。 w a n gg i v ea s u f f i c i e n tc o n d i t i o nf o rs u c ha t h e o r e m1 3 ( w a n g 【6 】) w h e npi sa p m m en u m b e rk m nh a s 。ip 一 ，。c t o r i z a t i o n 玎( 1 ) m p n ，( 2 ) n p m ，( 3 ) p m n 三p n m 三0 ( n z o d ( p 2 1 ) ) a n d ( 4 ) ( p r n n ) ( p n r n ) i0 ( r n o dp ( p 1 ) ( p 2 1 ) ( r n + n ) ) 2 s o m ef a c t o r i z a t i o n so fc o m p l e t eb i p a r t i t eg r a p h s孙霓刚 i np a p e r 【9 】a n d 【1 0 1 ，d uh a se x t e n d e dw a n g sr e s u l tt ot h ec a s e s = p 8 a n dk = p q ，w h e r epa n dqa r et w od i s t i n c tp r i m en u m b e r sa n dei sap o s i t i v e i n t e g e r h eg a v es u f f i c i e n tc o n d i t i o n sf o rs u c hf a c t o r i z a t i o n st oe x i s ta sf o o w s t h e o r e m1 4 ( d u 9 】) w h e n pi s op r i m en u m b e ra n dei sap o s i t i v ei n t e g e r k m 、。h a sdk 1 口c - ，0 e t o r i z a t i o ni l ( 1 ) m 兰p 8 n ，( 2 ) n 茎p 8 m ( 3 ) p e r n h 三 矿札一m 三0 ( m o d ( p h 1 ) ) a n d ( 4 ) 0 。m n ) 8 n m ) 三0 ( r o o dp 。( 矿一 l ) ( 矿8 一1 ) ( m + n ) ) t h e o r e m1 5 ( d u 【l o ) w h e n pa n d 口o ”t w od i s t i n c t p m m en u m b e r s ， h a s k l ，p 口q a c t o r i z a t i o n 矿( 1 ) m 兰p q n ，( 2 ) nsp q m ，( 3 ) p q m n 三p q n m 三 0 ( r o o d ( p 2 q 2 1 ) ) a n d ( 4 ) ( p q m n ) ( p q n r n ) 三0 ( m o d ；q ( p q 一1 ) ( p 2 q ! 一 u ( m + n 1 1 i “p a p e rm d ua l s og a v eas u f f i c i e n tc o n d i t i o nf o rk l ，p 2 - f a c t o r i z a t i o no f a mnt oe x i s tf o rt h ec a s e = 1 p ，p 2 ，w h e n e v e rp i sap r i m en u m b e r t h e o r e m1 6 ( d u 【8 ) w h e n p i sap r i m en u m b e r a n d = 1 ，po r p 2 a k 。 h a s 。k 1 , p 2 - f a c t o r i z a t i o n q ( 1 ) m p 2 m ( 2 ) n p 2 m ，( 3 ) p m n 兰p 2 n m 三 0 ( r o o d ( p 4 1 ) ) a n d ( 4 ) ( p 2 m n ) ( p 2 n m ) 兰0 ( r o o d p 2 ( p 2 1 ) 2 ( p 2 + 1 ) ( ”l + n ) ) i nt h i sp a p e r ，w ew i l lm a k ef u r t h e rs t u d yo ff a c t o r i z a t i o n so fa n f i r s t ， w ew i l l g i v e an e c e s s a r yc o n d i t i o nf o rt h ee x i s t e n c eo f 1k - f a c t o r i z a t i o no f mn ，w h e r eei sa n yp o s i t i v ei n t e g e r ，i e ，w ew i l lp r o v et h ef o l l o w i n gt h e o r e m t h e o r e m1 7 盯a k mh a so 耳1 k - f a c t o r i z a t i o n ，t h e n ( 1 ) m 曼k n ( 2 ) r l k m ( 3 ) k m n 三k n t n 兰0 ( r o o d ( 南2 1 ) ) a n d ( 4 ) a ( k m n ) ( 七n 一，n ) 三0 ( r o o d ( 驴一1 ) ( m 十n ) ) a f t e r w a r d s ，w ew i l le x t e n dt h er e s u l t so ft h e o r e m 14a n dl5 、iew ew i l l p r o v et h ef o l l o w i n gt w ot h e o r e m s t h e o r e m1 8w h e npi sop r i m en u m b e r , ei s 口p o s i t f l , ei n t e g e ra n da = 1 ，p ，p 2 ，p 。o r p 8 ， ，nh a sak 1 咖c t o r i z a t i o ni f ( i ) m 至矿n ( 2 ) n ! p 。m ( 3 ) p 8 m n 三矿n m 兰0 ( m e d ( p 她一1 ) ) a n d ( 4 ) a 扫。m n ) ( p e n m ) 三0 ( m o d 旷( 矿一1 ) 2 ( p 8 + i ) + n ) ) t h e o r e m1 9f o ra n yt w od i s t i n c tp r i m er z u m b e r spa n dqa n da = 1 p ，u o rp q ，nh a sa l 棚- 血c t o r i z a t i o n 矿( 1 ) msp q n ( 2 ) nsp q ( 3 ) p q m n5p q n mi0 ( r o o d ( p = q 2 1 ) ) a n d ( 4 ) a ( p q m n ) ( p q n 一，7l ) i0 ( * n o dp q ( p q t ) ( p 2 q 2 一1 ) ( m + n ) ) w ec a l lv e r t e x wo f “m nn sa v e r t e x w h i c h i sr e s t r i c t e d i na k i p - f a c t o r i z a t i o s o m ef a c t o r i z a t i o n so fc o m p l e t eb i p a r t i t eg r a p h s孙冕刚 。fk t n ，ni ft h eo u td e g r e eo fwi ne a c h ：，p f a c t o ro fk m ni spa n dw ec a l ls u c h a k i 。p f a e t o r i z a t i o no fk m ra so n e r e s t r i c t e dk 。p - f a c t a r i z a t i o n o fk nw h e j e ui s r e s t r i c t e d f i n a l l yw ew i l lg i v eas u f f i c i e n tc o n d i t i o nf o ra no n e - r e s t r i c t e d i 口一f a c t o r i z a t i o no f m ，mt oe x i s tw h e np i sap r i m e n u m b e r ，i ，e ，w ew i l lp l o r e t h ef o l l o w i n gt h e o r e m t h e o r e m1 t 0 w h e n p 站ap r i m en u m b e r a n d wi sa n yv e r i e z 一m n ，耳m h a sa n o n e l r e s t r i c t e d f ，p - f a c t o r i z a t i o nw h e r e i sr e s t r i c t e d 玎( 1 ) msp n ( 2 ) 他sp m ，( 3 ) p m n 三p n m 三0 ( m o d ( p 2 1 ) ) a n d ( 4 ) ( p m n ) ( p n m ) 兰0 ( r o o dp ( p 1 ) ( p 2 一1 ) ( m + n ) ) t h eo r g a n i z a t i o no ft h i s p a p e ri s a sf o l l o w si ns e c t i o n2i st h ep r o o fo f t h e o r e m1 7i ns e c t i o n3w ew i l lg i v es o m ep r e l i m i n a r yl e m m a si ns e c t i o l t4 i st h ep r o o fo ft h e o r e m1 8 i ns e c t i o n5i st h ep r o o fo ft h e o r e m1 9a n di n s e c t i o n6w ew i l lg i v et h ep r o o fo ft h e o r e ml1 0 4 ! ! 翌! 空! ! ! ! t ! ! ! ! ! 堕! ! 旦! 里! 堡塑! ! ! ! ! ! 塑鱼! ! ! 坠一! ! ! 型 2 p r o o fo ft h e o r e m1 7 n o ww ew i l lg i v et h ep r o o fo ft h e o r e m1 7 p m o fl e t xa n d yb e t h e t w o p a r t i t es e t so f nw i t h i x j = ma o d i y f = n l e t f r ，恳，b ) b ea 硒， 一f a c t o r i z a t i o no f t n av e r t e xzo f 丘i sc a l l e d ar o o to f r i f t h e d e g r e e o f x i n r i s 七l e t na n db b e t h en u m b e r so f r o o t s o f r c o n t a i n e di nxa n dyr e s p e c t i v e l y l e to = a ( k n m ) ( k m n ) ( ( k + 1 ) ( r - c ，) ) t h e n a + 七6 = m k a + b = n h e n c ew eh a v e 1 k n 研- * n ，b = 1 7 日：r m - o s i n c en ，bm u s tb en o n n e g a t i v ei n t e g e r s ) w eh a v e m s 是? ；扎sk m 。k n 一? n 三k m n 兰0 ( m o d ( k 2 1 ) ) w ea l s ok n o wt h a t r - 错= x m n ， t h e n r = 船= n + a b + c t h u sci sa ni n i ；e g e r l e t “ys u p p o s et h a tt h e r ea r eo n l yr 7 日s ，e a c ho fw h i c hc o n t a i n sum ar o o t t h e n r7 + ( r r ) = a m ，ie ( 一x ) r + c = ( k 一1 ) 6 t h e r e f o r e c i 0 ( m o d ( k 1 ) ) ，ie a ( k n m ) ( k m n ) ；0 ( r o o d 女( 2 0 ( m 十n ) ) t h t sd r o v e st h e o r e m1 7 - s o m ef a c t o r i z a t i o n so fc o m p l e t eb i p a r t i t eg r a p h s 孙霓刚 3 s o m ep r e l i m i n a r yl e m m n s i nt h i ss e c t i o nw ew i l l p r o v et h r e el e m m a sw h i c hc a nb eu s e dt op r o v e t h e o r e mt8a n d1 9f o ra n yt w oi n t e g e r sxa n dy ，w el l s eg c d ( x ，) t od e n o t e t h eg r e a t e s tc o n l m o nd i v i s o ro fza n d i l e m m a3 1 l e t 。，y ，：把p o s i t i v ei n t e g e r s f g e d ( z ，们= 1t h e n9 c d ( x v ，z x + y ) = g c d ( z ，v ) p r 0 0 1 o b y i o u s i l l l e m m a 3 2 盯 nh a * ak i ，k ，n c t o r i z a t i o n ，t h e na k s m m a l s oh a s 口k 1 ，k f a c t o r i z a t i o ni o ra n yp o s i t i v ei n t e g e rs p r o o f i ti so b v i o u st h a tt h eg r a p hk h a sak l ，f a c t o r i z a t i o n ( s e e 【1 1 ) l e t ( r 1 1sis3 ) b e & k 1 ，f a c t o r i z a t i o no f 虬一f o re a c hi l ，2 ，s ) ， r e p l a c ee v e r ye d g eo f 最b yaa nt og e taf a c t o rg to fa k 怵s ns u c ht h a t t h eg r a p hg l ( 1 墨i s ) a r ep a i r w i s ee d g e - d i s j o i n ta n dt h e i ru n i o ni sa k 。m s i n c e k m ，nh a s k 1 一f a c t o r i z a t i o n ，i ti sc l e a rt h a tt h eg r a p hg lh a sa 1 k f a c t o r i z a t i o na sw e l l c o n s e q u e n t l y , k ，m s n h a sak 1 一f a c t o r i z a t i o nt h i s p r o v e st h el e m m a i l e m m a3 3f o ra n y p o s i t i v ei n t e g e rt ，对x k m mh a sak 1 , k - j a c t o r i z a t i o n t h e n i a i , j “n a l s oh a sdk 1 k 一，n c t o r i z a t i o n p r o o i w eo n l yn e e dt om u l t i p l ee a c h k 1 ，k f a c t o r i z a t i o no ff a k 1 f a c t o ro fa k mnf t i m e st og e ta i ac o r o l l a r yo fl e m m a3 2a n d3 3 i sa sf o l l o w s c o r o l l a r y3 4a k 3 j k sh a sbk 1j k | q c t o r i z a t i o n | o ta n yp o s i t i v ei n t e g e rs 6 s o m ef a c t o r i z a t i o n so fc o m p l e t eb i p a r t i t eg r a p h s 孙霓刚 4 p r o o fo ft h e o r e m1 8 c o r o l l a r y3 4i m p l i e st h a tw eo n l yn e e dt ot r e a tt h ec a s em p 8 ns a d n 0 ，t h e ng e d ( v t ，p ) = 1a n d9 c d ( u ，p ) = 1f r o mg c d ( u ，u 1 ) g c d ( t t ，t - ) = la n d l e m m a 31 ，w ec a n g e t t h a t g e d ( u v i ，u + 矿v 1 ) = g e d ( u ，矿) = a n dg c d ( u v i ，p 2 e - u + 口1 ) = 9 c d ( 7 2 l ，p 2 。一) = 1 t h e nw eg e t g e d ( i t v l ，( “ 矿u 1 ) ( p 2 。一j u + 7 2 1 ) ) = 1 r = ( u + v ) “p u 2 + v l e =逝如甓猢z 1 t y l l t i fj20 t h e n i = 0 ，f = r = 虹堂唉! 业zf r 。“驴d ( 札p ) 9 c d ( c , ，p ) = 1a n dl e m m a31 ，w ec a ng e tt h a tg c d ( u ? 2 l ：u4 - p 1 ) = 1a 1 1 7 s o m ef a c t o r i z a t i o n so fc o m p l e t eb i p a r t i t eg r a p h s孙霓刚 g c d ( u v l p 2 2 “+ n 1 ) = g e d ( v 】，p 2 。) = l - t h e ng c d ( n v l ，( “+ u i ) ( p 2 t + l j l ) ) = 1 w ea l s oh a v et 。”ll t l e ts = 面t ，t h e nsi sap o s i t i v ei n t e g e ra n dt h ee q u a l i t i e sh o l dl l e r n m a4 2f o ra n yp o s i t i v e i n t e g e r su ，u ，ia n d ，w h e r e0si sea n d 0 j 2 e 矿0si j 兰e ，a n dl e tm = p 。一1 ( p 。一u + u ) ( u 十矿u ) ，n = 一一1 ( p 。一“+ u ) ( p 2 e - - ，4 - u ) ，t h e np i ，nh a snk x ，矿- f a c t o r i z a t i o n p r o 计l e ta = p e - i u ( p 卜j u 4 - v ) ，b = 训v ( p j u 4 - v ) ，r = ( u + ， ) ( p 2 e - - i n + v ) ， 7 , 1 = u + 矿ua n dr 2 = p 2 8 - j u + ”l e tx a n dyb et h et w op a r t i t es e t so f 矿k mn a n ds e t x = z k ，1 1 1 曼盘曼r l ，1s f 矿一( p 8 一j u4 - 口) ) ， 】，= 掣 ，fj ls 七! r 2 ，ls f 兰矿一。( p e j u + ) w ew i l lc o n s t r u c tak 1 ，p c f a c t o r i z a t i o no f p 。k m n w er e m a r ki na d v a n c et h a t t h ea d d i t i o n si nt h ef i r s t s u b s e t i p t so fo o sa n d 弧sa r et a k e nm o d u l ot 1 a n dr 2i n l ，2 ，n ) a n d ( 1 、2 ，r 2 ) ，r e s p e c t i v e l y , a n dt h ea d d i t i o n si nt l t e s e c o n ds u b s c r i p t so fz 。r s a n d _ k ，i s a r et a k e nm o d u l op h ( 矿一u + ) a n d 矿1 ( p e _ ，u + 口) i n 1 ，2 ，矿叫( p e 一，u + u ) ) a n d l ，2 ，矿叫( 矿一j u + u ) ) ， r e s p e c t i v e l y f o re a c h 七，ya n dz ，1 茎七u ，1 兰妄p ea n d0 茎z p 。一，l e t ，( z ) = 矿1 ( p 。一j u + v ) z 。g ( k ，y ，：) = p 砧一( k 一1 ) + p c - j ( y 1 ) 4 - z + 1a n d h ( k ，) = p e ( 一1 ) + y la n ds e t 鼠= 。k ，f + ，扛) y g f k 舢：) ，l + ( 。v ) l l c 矿一。( p 8 一u + u ) ，1 1y 曼p 。 0s ： p c - ) f o re a c h ，y ，1 七p ，1 ys 矿，l e tl p ( 七，y ) = + ，( 七一1 ) + ya n d 0 ( ，y ) = p e l t + 矿( 一1 ) + y 一1 a n ds e t e “+ = 。9 ( 们，f 鄄，一。+ 。廿忙们+ ? 1 1s l s 芦。一( p 8 一n + ) ，1 y ! 矿) l e tf = u l ( u + u e k 。t h e nt h eg r a p hf i sa k 1 ，矿一f a c t o ro f p 2 d e f i n e ab i j e c c i o no - f r o mx u y o n t ox u yi ns u c haw a yt h a t r ( z k ，f ) = o + 1 、 a n d a ( y k ，f ) = g k + l 小f o re a c hk l ，2 ，r 1 ) a n de a c hl 1 ，2 ，r 2 ) ，1 e t f = 盯( 。) 仃2 ( y ) l z x ，y ，x y f i ti se a s yt os h o wt h a tt h eg r a p h s 凡1 ( 1 k 7 , 1 ，1 fs ”2 ) a r ek i 一 f a c t o r so f p 。，na n dt h e i ru n i o ni s 矿，n t h u s r ，l f l 茎k 曼f 1 ，1 f 7 2 j i sak 1 ，一f a c t o r i z a t i o no f p n 1 f r o ml