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

完全二部多重图的，g 一因子分解 摘要 摘要 a 五岛n 是完全二部多重图，它的两个部分点集x 和y 分别具有m 和n 个点入的口- 因子是a 甬，仇n 的生成子图，它的每一个分支是完全二 部图如果a j 乙，。的所有边可以被划分成若干个旷因子，就称a j o ，n 有，r 因子分解若完全二部多重图a j o ，n 存在饰旷因子分解，就称a 靠n 是可砗矿因子分解的在文章【1 4 】中，a ，n 的，r 因子分解称为可分解 的( m ，n ，p + g ，a ) ，口- 设计 众多学者已经对完全二部多重图入。，。的，r 因子分解作了研究，并 得到了若干应用特别是，y a m a m o t o 等 1 8 】用其建立了计算机数据存储的 h u b m f s 2 方案当a = 1 时，n m a r t i j l 在文章【6 】6 中，给出了 口因子分解 存在的必要条件，并猜想这些必要条件也是充分的从这以后，m a r t i n 猜想 就引起许多学者的注意m = n 的平衡情形m a r t i n 在他的系列文章( 6 ，7 ，8 ， 9 】中证明了其猜想为真但对于m 竹的不平衡情形，问题就变复杂了文 章d u 和w a n g 【5 】5 和m a r t i n 【1 1 ，分别解决了( p ，q ) = p ，p + 1 ) 的情形在文章 【1 1 1 中，m 吼i n 同时证明了当9 c d ( 口一p ，z + y ) = 1 时猜想是正确的本文给 出了a ，n 存在。因子分解的必要条件，并证明了当夕冽( g p ，z + y ) = 1 时，必要条件也是充分的特别地，对a 。，。的凰口- 因子分解，我们对它的 不平衡情形做了进一步工作，证明了当y 充分大时，必要条件也是充分的 关键词：完全二部多重图；因子分解；h u b m f s ：方案 作者：施静 指导教师：杜北梁( 教授) o n k p , q - f 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 em u l t i g r a p h s - a b s t r a c t o nk p , q - f a c t o r i z a t i o n so fc o m p l e t e b i p a r t i t en m l t i g r a p h s a b s t r a c t l e ta k i n mb eac o m p l e t eb i p a r t i t em u l t i g 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 dn v e r t i c e s ，r e s p e c t i v e l y ak p , q - f a c t o ri na j 岛，ni sas p a n n i n gs u b g r a p ho fa j o 一， e a c hc o m p o n e n to fw h i c hi sac o m p l e t eb i p a r t i t eg r a p hj g i ft h ee d g e so fa ，nc a n b ep a r t i o n e di n t ok p , q - f a c t o r s ，t h e nw es a y 入k n 。nh a sak p , q - f a c t o r i z a t i o n t h eg r a p h a ，ni sc a l l e dk p , q - f a c t o r i z a b l ew h e n e v e ri t h a sak p , 一- f a c t o r i z a t i o n i np a p e rf 1 4 a k p , q - f a c t o r i z a t i o no fa k n ，ni sd e f i n e da sar e s o l v a b l e ( 仇，n ，p + q ，入) k p , q - d e s i g n t h e j 0 ，q - f a c t o r i z a t i o no fac o m p l e t eb i p a r t i t em u l t i g r a p h 入，nh a sb e e ns t u d i e d b ym a n yr e s e a r c h e r sa n df o u n dan u m b e ro f 印p l i c a t i o n e s p e c i a l l y , y a m a m o t oa n d u s h i oe c t 【1 8 1h a v eg i v e ns o m ea p p l i c a t i o n si nh u b m f s 2s c h e m e so fd a t a b a s es y s t e m s w h e na = 1 ，n m a r t i n ，i np a p e r 【6 l ，g a v es i m p l en e c e s s a l 了c o n d i t i o n sf o rs u c ha f a c t o r i z a t i o nt oe x i s t 。a n dc o n j e c t u r e dt h o s ec o n d i t i o n sa r ea l w a y ss u 伍c i e n t m a r t i n c o n j e c t u r e ，f r o mt h e no n ，h a sd r a w nf o c u sf r o mm a n yr e s e a r c h e r s m a r t i nc o n j e c t u r e h a sb e e np r o v e di nm a n y 渊t h eb a l a n c e dc a s e ( m = n ) w 豳p r o v e di nas e r i e so f p a p e r s 6 ，7 ，8 ，9 】b u tf o ru n b a l a n c ec a s e ( m n ) ，t h ep r o b l e mb e c a m ec o m p l i c a t e d t h ec a s ef o r0 ，q ) = ( p ，p + 1 ) w a ss o l v e di n 【1 1 ，5 】a l s om a r t i n 【i i 】s h o w e dt h a t t h ec o n j e c t u r ei st r u ew h e ng c d ( q p ，z + y ) = 1 i nt h i sp a p e r ，w ew i l lg i v es i m i l a r n e c e s s a r yc o n d i t i o n sf o r 入一t oh a v eak p , q - f a c t o r i z a t i o n ，a n dp r o v et h en e c e s s a r y c o n d i t i o n sa r ea l w a y ss u f f i c i e n tw h e ng c d ( q p ，z + y ) = t e s p e c i a l l y , f o ra 岛nt o h a v eak l , q - f a c t o r i z a t i o n ，w ec o n t i n u et h es t u d yo ft h eu n b a l a n c e dc a s et os h o wt h e n e c e s a r r yc o n d i t i o n sa r es u f f i c i e n tw h e n e v e r 可i ss u f f i c i e n t l yl a r g e k e y w o r d s ：c o m p l e t eb i p a r t i t em u l t i g r a p h ；f a c t o r i z a t i o n ；h u b m f s 2s c h e m e s i i w r i t t e nb ys h ij i n g s u p e r v i s e db yd ub e i l i a n g 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本 声明的法律责任。 研究生签名：j 纽盔晕日期：班垒垡 j 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：刀趄酶一日 期：丝z ：生型 导师签名： 盔i 监日期：垃 完全二部多重图的，口一因子分解 一引言 一引言 记j 厶n 是完全二部图，其两个部分别具有m 和死个点完全二部多重 图a j 是互不相交的入个图的并，且其中每个图都同构于j o a 五，n 的 个子图f 若包含了a 一的所有点，则称f 是a ，n 的生成子图设p 和 q 是正整数a ，n 的，叮- 因子是它的满足下述条件的生成子图f ：f 的每 个分支都同构于，口且任何两个，。都没有公共点如果入j o ，n 的所有边 可以被划分成若干个口因子，我们就说入，n 有矿因子分解若完全 二部多重图a j 一存在g - 因子分解，就称a ，n 是可巧，口- 因子分解的 在文章【1 4 】中，入，n 的，口- 因子分解称为可分解的( m ，仃，p + q ，a ) ，r 设 计本文用到的图论方面的名词术语，均参考著作 1 】 众多学者已经对完全二部多重图入j o ，n 的，口- 因子分解作了研究当 a = 1 时，m a r t i n 在文章【6 1 中，给出了k 叩存在，口- 因子分解的必要条件 并猜想这些必要条件也是充分的从这以后，m a r t i n 猜想就引起许多学者 的注意p = 1 ，q = 2 的情形早在文章u s h i i o 【1 3 1 中得到证实p = 2 ，q = 3 和 p = 1 ，q = 3 的情形分别在文章w 抽g 和d u 【1 7 】和m a r t i nf 1 0 中得到证明 m = n 的平衡情形m a r t i n 在他的系列文章【6 ，7 ，8 ，9 】中证明了其猜想为真 对于一般情形q = p + 1 ，则在文章d u 和w 吣g 【5 l ，m 疵i n 【1 1 】中得到解决最 近，在文章【1 1 】中，m a r 恤证明了当9 c d ( q p ，z + ! ，) = 1 时猜想是正确的 本文，我们研究完全二部多重图入，n 的，r 因子分解的存在性假 设a j 岛，。可，。因子分解，定义如下一些参数： t ：任一因子中的二部图。的个数 z ：，口因子中的p 个点的部落在x 中的二部图，口的个数 ：饰矿因子中的p 个点的部落在y 中的二部图，。的个数 ，：因子分解中的。口- 因子的个数 对应x 中的点 有p 条边与之关联的二部图，。的个数 8 1 ：对应x 中的点u 有q 条边与之关联的二部图，。的个数 您：对应y 中的点u 有p 条边与之关联的二部图，。的个数 8 2 ：对应y 中的点u 有q 条边与之关联的二部图丹的个数 完全二部多重图的坼，g 一因子分解 一 引言 我们可得到a 。，。存在巧，口因子分解的必要条件 定理1 1 设入，p ，q ，仇和n 是正整数且p q 1 若a 甬岛，n 存在g - 因子分 解，则以下表达式都是整数： 孟2 等舻篱舻篱扣嬲n = 矿a n ( t 而i n - q 两m ) ， s - = 虱a 歹n = o 面n 丽- q n ) ，您= 夏a 歹m 二q i r r 丽n - q n ) ，s 2 = j 端 证明： 由两种方法计算完全二部多重图a j m 的点数，有 t o , + q ) = m + n 由z ，y 的定义 z + y - - - - t , 嚣 得 悟= 伽( r , n 一- q n ) a m ) 菩二苏 ( 2 ) l 矽= ( 即一( 矿一9 2 ) l 二 每个坞，口- 因子有t p q 条边，从而由两种方法计算完全二部多重图a j n 的边数，有 a m n = f t p q ， 得 ，= a m m t p q = x m n p q c m + n ) 】 由s 1 的定义 jr l + 8 1 = ， ip r l + q s l = a n 得 j7 1 = ( a n q f ) ( p q ) = a n o n q m ) p ( p 一口) ( m + 礼) 】， 、8 1 = ( 入n p f ) ( q - p ) = a 7 1 0 玎n q n ) q ( p g ) ( m + n ) 】 同理可得 jr 2 = a m 0 - 玎l g 几) 囟p g ) ( m + n ) 】， i8 2 = a m o n q m ) q ( p 一口) ( m + 礼) 】 2 ( 3 ) ( 4 ) ( 5 ) 完全二部多重图的，口一因子分解 一引言 所以，定理1 1 中的表达式都是整数d 在文章【1 6 】中，w 眦g 和d u 已经证明了当p = 1 ，q = 2 时，这些条件 都是充分的进一步的工作见文章【2 ，3 ，4 1 本文将证明当9 c d ( g p ，z + y ) = 1 时，这些必要条件都是充分的特别地，对a 珞，n 的墨。因子分解，当 9 c d ( 口一1 ，z + y ) = d l ，z 可时，我们证明了对于充分大的可，必要条件也是 充分的 3 完全二部多重图的。q - 因子分解 二 预奋知识 二预备知识 这一节，我们将给出一些预备知识首先，需要以下的几个引理 引理2 1 若入j ，n 是可 口- 因子分解的，则对任一正整数8 ，s a ，n 也是可 j 口一因子分解的 证明：令 且：1 i ，) 是a ，n 的，口- 因子分解重复s 次得到s a 。n 的旷因子分解 口 引理2 2 若a 石，n 是可口因子分解的，则对任一正整数s ，a ，肿是可 ，。因子分解的 证明。令 只：1 i s ) 是一的i 一因子分解对任一i 1 ，2 ，s ) ， 用a j o ，。替代只中的每一条边，得到a ，w 的g t 一因子入j _ ，n 是可，口 因子分解，所以g 也可砗，。一因子分解因而，入，册是可，。一因子分解 的口 结合引理2 1 和引理2 2 ，我们有以下推论： 推论2 3 对任一正整数8 ，a 甬棚可，。一因子分解 引理2 4 若入，n 是可 口- 因子分解的，则对任一正整数s ，a 彻可，驴 因子分解 证明：令 b i ：1 i f ) 是入一的略，口因子分解对任一i 1 ，2 ，s ) ， 用8 个点替代最中的每一个点，且用k 一替代b 中每条边，得到a j m 彻 的g t 一因子分解显然，g 可甬g | - 因子分解所以a j ，舯可甬因子 分解 口 对a ，n 的，。因子分解中给定的p ，q ，m 和n ，总存在最小的整数知 满足必要条件，称知为基本重数 引理2 5 对a n 的埠，。- 因子分解中给定的p ，q ，m 和n ，任意满足必要条 4 完全二部多重图的，g - 因子分解 二 预备知识 件的a 都是基本重数知的整数倍 证明：知是基本重数若a 是另一个满足必要条件的整数，则存在有理数k 使得a = k a o 下证k 必是整数若k 不是整数，则令a l = a l k j x o ，0 入1 知 注意到 f = a m n p + q ) 胁( l + 佗) 】 是整数而且 如= 知m n + q ) 由q ( m + n ) 】 也是整数令k = 例+ q ，0 口 1 则 f = a 仇n 0 + q ) 咖( m + n ) 】- = ( a 1 + 【叫知) m n 白+ q ) 囟q ( m + ，1 ) 】 = a x m n ( p + q 胁q ( m + n ) 】+ 【副m n ( p + q ) 【p q ( m + n ) 】 = a x m n ( p + q ) 囟q ( m + n ) 】+ 睛j ，o 因此，a x m n 白+ q ) 加q ( m + n ) 】也是整数由类似讨论可知，a 1 也满足其它 必要条件因0 a 。 知，此与知的最小性矛盾 口 假设p q 由定理1 1 中的z 和可的表达式，我们可以假设n n q n 和 册唧但由推论2 3 及当肌= q n 和册= q m 时a ，n 是可旷因子分 解，故我们只需研究p r a q n 和肼 q m 的情形对于这种情形，我们运用 比值z ：可= 口：卢来对满足必要条件的m 和n 进行分类在因子分解中， 尽管坼，。因子中有p 个点的部落在x 中和p 个点的部落在y 中的二部图 ，。，但它们的比值是固定的，我们称作平衡比事实上，我们可以假设z ，! ， 互素对固定的比值a ：p ，总是存在最小的整数咖，珊满足必要条件称这 对咖，伽为对应比值0 f ：p 的基本对 引理2 6 对比值。：可，任意满足必要条件的m 和佗都是对应该比值的基本对 的整数倍 证明：设m o ，伽是对应比值z ：的基本对，则m = 七m o ，n = 七咖下证k 是 整数若k 不是整数，令m l = m 一例咖，竹l = m 一例伽，这里0 m 1 咖， 0 n 1 伽注意到 r l = a n 伽一口m ) 囟p 一口) ( m + 礼) 】 5 完全二部多重图的，口- 因子分解 二 预备知识 和 r i o = a 伽p 伽一q m ) 一g ) ( 讹+ n o ) 】 是整数令k = 【纠+ 口，i f q 1 则 r l = a 七伽0 七伽一口后咖) 囟( p g ) ( 七伽+ 后伽) 】 = a k 伽o m o q m ) 蛐一g ) ( 砜+ 伽) 】 = 【纠入礼0 0 _ n o q m o ) 囟白一q ) ( 棚1 0 + 伽) 】+ a 入m ( p n o q m o ) 囟( p q ) ( 啪+ 珊) 1 = l k j r l o + a 概( a p n o 一口g m 0 ) 囟p 一口) ( q 7 n 0 + q n 0 ) 】 = 【k j r i o + a n l ( p n l g m l ) 防( p g ) ( a m 士+ 口n 1 ) 】 因此，m 。，n l 满足必要条件，这与伽，伽的最小性矛盾 口 引理2 7 设k ，p 和q 是正整数且p ，口互茉若咖，伽是a ，。的口因子 分解中对应某一比值z ：y 的基本对，则凫啪，缸锄是入，n 的j ，婶因子分 解中的对应比值z ：y 的基本对 证明：设m 。，n 是a 一的，k q - 因子分解的基本对由引理2 4 ，若入m 可 ，口一因子分解，则入讯，。，概可j ，七口因子分解所以七仇0 = g m l 且七伽= 卵1 又入j 。，n ，可j ，k r 因子分解，而j ，k 口可 口- 因子分解进而a j o 。一。可 玛- 口因子分解因而m 1 = 嘞且n 1 = 伽得k = g h 设，0 是入j ，。，加的口因子分解的因子个数 是入甬，m 。，n ，的，七r 因子分解的因子个数 = 入m l 死1 ( 切+ 七g ) 【坳k q ( m l + n 1 ) 1 = a 九玎 他o ( p + g ) 专p 口( m o + ，l 咖) 】 = 入 m o 伽0 + g ) 【却g ( m 0 + 伽) 】 = h 矧k = 蚰g 因此，g 整除，o 类似讨论可知，g 整除所有必要条件给出的整数所以 夕= 1 否贝0 ，伽9 ，伽夕也满足必要条件，与仇0 ，咖的最小性矛盾 口 引理2 5 2 7 表明我们只需考虑p ，口互素，基本重数知和基本对咖，伽 的情形现在讨论如何计算伽，n 。和知 6 完全二部多重图的饰，口一因子分解 二预备知识 入五，m ，n 存在，g 因子分解的必要条件可以用z ，y ，p 和q 写成如下形式： t = z + y f = 地+ a y + a 0 一g ) 2 z 囟g ( 。+ 分) 】， r 1 = a y 一入白一口) z 可囟0 + ) 】， 8 1 = 妇+ a ( p q ) x y l q c x + 3 ，) 】， i f 2 = a 。一a 0 一q ) x y l 囟( x + 剪) 】， 8 2 = a y + a 白一口) 叼【g ( z + 可) 】 则可以直接得到以下引理： 引理2 8 设p q ，毛y 是互素的正整数对，则a 甬 n 的缉旷因子分解中，对 应平衡比z ：y 的基本对可以如下给出：m = 6 ( q x + 刀) 和n = 占+ q y ) ，其 中j 是最简分式a 0 一p ) 铡咖扛+ 可) 】的分母 令p 1 = 夕以( p ，z ) ，仡= 夕以白，可) ，q t = 9 缸( g ，z ) 和口2 = 夕c d ( g ，y ) ，则有p = 卿1 耽，q = 9 0 口l q 2 ，z = p m q 跏和y = 仡啦珈由假设夕谢0 ，q ) = 夕以( z ，y ) = 1 ，可以 直接知道数n ，仡，q 1 ，口2 ，勋，珈，册，口0 除了可能序对1 ，知) ，( 吼，x o ) ，( p 2 ，珈) ， 池，珈) ，慨，伽) 和( 依，q b ) g = 1 ，2 ) 外都是两两互素的通过简单计算，有最小 整数 知= 夕c d ( 入，p o q o ( x + 可) ) 则最简分式a ( g p ) z y 咖扛+ 秒) 】的分母是j = q 0 0 + 3 ) 】知因而基本序对 m 0 ，伽为： 1 m o = 伽9 0 ( z + 可) ( 口z + p 可) ， 0 1 伽= p o q o ( z + 可) + g v ) 0 本文主要的构造方法是建立在因子阵列的基础上 引理2 9 有，个因子数的a ，n 的 g - 因子分解等价于一个m n 阵列f ， 满足： ( 1 ) 每行每列的每个位置包含 1 ，2 ，n 中的a 个不同的数值， ( 2 ) _ 【1 ，2 ，n 中的每个数值在每行每列中都要出现，且 7 完全二部多重图的，g - 因子分解 二 预备知识 ( 3 ) 标有数值i 的元素，对应了第i 个，口- 因子中的边 证明：阵列f 的行对应完全二部多重图a ，n 的仇个点的部x 中的点， 列对应它的n 个点的部y 中的点，f 的每个位置则对应了连接行标和列标 所对应点的边 口 我们称这样的阵列为口- 因子分解的因子阵列以下是一个因子阵列 的例子 1 ，4 ，8 ，9 2 , 5 ，7 ，93 , 6 ，7 ，8 1 , 5 ，6 ，72 ，4 ，6 ，83 ，4 ，5 ，9 2 , 3 ，4 ，71 , 3 ，5 ，81 , 2 ，6 ，9 表1 ：4 硒。3 的j “2 - 因子分解 8 完全二部多重图的，口- 因子分解 三 主要结果 三主要结果 - _ i - = 工= - = ； _ _ l i - 一u ，- 、 定理3 1 已知互素的点对0 ，q ) 和( z ，) 当9 以( g p ，z + y ) = 1 时定理1 1 中 的必要条件也是充分的 证明：不失一般性，假设p q ，且有夕以，口) = 夕以( z ，可) = 1 令p = 伽p 1 仡，q = g 0 9 1 口2 ，z = p l q l x o 和! ，= 仡9 2 珈，其中p z = 9 c d 0 ，z ) ，现= 9 以p ，剪) ，q l = 夕c d ( g ，z ) 和q 2 = 夕c d ( g ，) 则有最小的知= 夕c d ( a ，伽9 0 0 + 可) ) ，且有基本对 11 伽= 亡伽9 0 0 + y ) ( g z + 刀) = 亡伽9 0 ( z + y ) p l q 2 9 ， “u“0 其中p = 9 0 9 知+ 舶建珈和 11 伽= 亡如9 0 0 + 掣) + 盼) = 亡伽q b 0 + 矽) 沈9 1 其中| ，= 碱知+ q i d 谚珈因子数为，= p a n 的边自然地对应了m n 的因子阵列f 中的元素我们的目标是 用1 ，p y 中的数值对f 中的元素进行标号，使得标有相同数值i 的元素 对应着第i 个因子中的边 每个j 口因子都是一些完全二部图，。的集合那些q 个点的部落在 入坍的m 个点的部的，。称为是垂直的，那些q 个点的部落在a n 的n 个点的部的。称之为水平的 垂直的，。块的定义 设t ，是口2 px 仇l ，矩阵，它的元素为五口对每一组a ，b ，c ，d 可以唯一确 定q = ( a 1 ) q 2 + c 和卢= ( b 一1 ) p 2 + d ，其中1 口p ，1 b | ，1 c 9 2 和1 d 化令如= ( a 一1 ) y + b ，然后将，划分成由9 2xp 2 的矩形块( 称为 r n j c r o 块) 组成的pxz ，阵列此处，每个m i c r o 块有相同的因子标号且这些 标号在，中按从左往右，从上往下的自然秩序排列 j 是旋转变量j ( i ，j ) ( 称为m i n i 块) 的原型j ( i ，j ) 可以通过将，的行顺 次向下平移嘞个位置和列顺次向右平移锄个位置而得到即将m i c r o 块 向下平移i 个位置和向右平移j 个位置从而有j = 4 0 ，o ) 9 完全二部多重图的，口一因子分解 三主要结果 用j ( i ，歹) 构造p l 口2 p 耽口1 z ，矩阵日日是由m i n i 块j 组成的p 1 q l 阵 列具体地，若1 ，y p l 且1 j q l ，则日的第，y 行第j 列的m i n i 块定义 为j = ，( j 一1 ，y 一1 ) 由于p 。 | ，且q l p ，所以组成日的所有l i n i 块都是互不相同的这就 使得了日有如下的性质： ( 1 ) 日的m i n i 块的每行每列中，因子标号最多出现在一个l i c r o 块内 ( 2 ) h 的l i n i 块组成的列( 徇内( 以下简称l i n i 块列( 行) ) ，因子标号出 现在连续的相邻的肌( q 1 ) 个m i c r o 块组成的列( 行) 中( 简称面c r o 块列( 行) ) 日也有旋转变量日( i ，j ) 对0 i q l g o x o 和0s 歹 触z o ，日( t ，j ) 是由 m i n i 块组成的阵列，此处1 q p 1 ，1 p q 1 对应第q 行第p 列的血n i 块是h ( i ，j ) 叩= j ( i q l + p 一1 ，觑+ 口一1 ) 注意到锄+ 卢一1 p 且m + a 一1 因而，若 矿，则在m i c r 0 块 行中，出现在日( i ，歹) 中的因子标号集合与日( i 7 ，歹) 中的不重复类似的，若 j j ，则在血c r o 块列中，出现在h ( i ，j ) 中的因子标号集合与h ( i ，歹7 ) 中的不 重复 现在，将垂直的。块填入到f 中此处，所有的计算都是模去伽9 0 扛+ 剪) 后在1 ，2 ，击p 0 9 0 0 + ) 之间首先，将矩阵f 划分成由大小为p 。9 2 p 仇口1 | ， 的矩形( 等于h 的大小) 构成的去伽口o ( z + ) 击伽9 0 p + ! ，) 阵列g 先将 g 的第一行的部分g 1 ，l ，g 1 栅相霉进行赋值这里p 0 9 0 z = 珈g o p l q l z o 对 1 j 砌q i d z ，有唯一的8 ，r ，使得歹一1 = 叩1 伽+ s 且0 3 p 1 伽，0 7 口1 9 0 跏， 再对唯一的u ，t 有r = t 9 1 卯+ 缸且0 让 9 1 口0 ，0 t z o 然后，定义 g 1 j = 日( r ，s + 印1 如) 最后，对2 i 击伽9 0 伍+ 可) 和1 u 伽9 0 z ，定义 g i d = g l 埘，这里j = i + 一1 下面，以1 为例来说明这样的定义确定了f 中的垂直的驴由h 的构 造，1 出现在每个n f i n i 块列中的第1 ，p 。m i c r o 块列和每个m i n i 块行中的 第1 ，口1n l i c r 0 块行经变量日( i ，j ) 后，官们各自变为却l + 1 ，0 + 1 切1 和t 9 1 + 1 ，“+ 1 ) 口1 事实上，在构造第一行时，我们已有日( r ，s + 功。伽) 块，其中1 出现在第 ( 8 + 纫1 加) p l + 1 ，( 8 + 切1 伽+ 1 ) p 1 的m i c r o 块列上和第r 口1 + 1 ，( r + 1 ) 口l 的m i c r 0 块行上 从左往右，n l i c r o 行中只有当r 不变时才有重复的数值而对每个r ，恰 1 0 完全二部多重图的，口- 因子分解 三主要结果 有p 1 伽个但每个l i c r o 块又有f 中的仇列，因此在血c r o 行中，有觚c r o 块一行子阵，出现在f 中的肌姚= p 列 固定r ，因为8 + 印，伽在变，则标有1 的m i c r o 块列在变，出现在相邻的 但不重复的i n j c r o 块列中另一方面，如果r 变，而8 + 印。册不变，同样符 厶 口 整个延伸上，沿着d 结构中的行，从左往右，皿块都是以长度p ，砌的 组出现g 上的对角线重复使得蚵c r o 块行一子阵出现在每行中且他们的 l i c r o 块列或者不重复或者是同一个也只有s + 饥册不变时，后者才会出 现对任意这样的值，恰有g l 口0 次因而，结合起来得到子阵，且出现在f 中的9 1 9 0 口2 = q 行这样，我们得到了一些互不相交的垂直的矿 因此，我们有如下的性质： ( 3 ) 上面的定义确定了垂直的，。的分配，且对相同的因子标号，没有 两个。会重复出现在一行或一列中 此外，我们还需知道m i n i 块间的垂直的和水平的因子标号的覆盖在 中有p 1 个l i c r o 块列覆盖和q 。个血c r o 块行覆盖沿着g 的行，已经有 蝴q l x o 个覆盖，其中有口1 口o z o 个组而每一次实施使得进入另一组的循环 后，又覆盖了另外的q l 行，这q l 行与前面的是相邻的因为共有q l x o 次， 得到所需的行覆盖 类似可得列覆盖因此， ( 4 ) g 的m i n i 块列( 行) 内，因子标号出现在连续的相邻的伽衍知( 9 0 9 z o ) 个n l i c r 0 块列( 行) ( 5 ) 硝知 l ，且9 0 爵z o p ，因此，相邻的行和列的集合不会再循环回 来 水平的，。块的定义 水平，g 块的构造方法与垂直的类似，只不过我们需要一个新的m i n i 块的构造 构造9 2 p 仇l ，的阵列m 如下：对1 8 p 和1 t ，将数值 l ，( s 一1 ) + t 标在元素的位置上，其中对1 口仇口2 ，有i = 9 2 ( s 一1 ) + 口和 j = 沈 一1 ) + a 此处的下标是分别模q 2 p 和p 2 y 后的余数这是我们标准的 m i n i 块的原型注意到这个构造其实是这样的：元素出现在m 的对角线上 完全二部多重图的，口- 因子分解 三主要结果 连续p 2 0 个位置，且从左往右每隔砌个元素因子标号增加1 ，从上往下每他 个元素增加z ， 构造膨的旋转变量m ( i ，歹) 将m 的列向右平移硝z o p 2 + 锄口2 且行向 下平移9 0 口 铂口2 + 觑q 2 个位置这里的被加项p 印；z 吡和g o g 勋口2 确保了不与 前面一部分定义的因子标号重复，另外两个被加项确保了i 和歹变化时不与 对角线上的重复： 由n l i n i 块m ( i ，j ) ，构造大的矩阵块( i ，歹) l ( d ，j i ) 是由面n i 块组成的p 1x q l 阵列，且每个l i l l i 块都等于m ( i ，j ) 则以下性质自然满足 ( 1 ) l ( i ，歹) 中每个m i n i 块列( 行) 内，因子标号出现在连续的仡口2 列( 行) 中 ( 2 ) 标有因子标号的元素形成了总数沈钇个p 。xq t 的行和列都不重复 的子阵，覆盖的相邻集合的个数如前所述 现用l ( i ，歹) 填入到f 的剩下的g - 块中，从而定义出所需的水平的 其方法是先完成g 的第一行，然后沿着对角线重复到其它各行 因此，对1 j 册口。可= 伽g 吡仍珈，定义g 1 ，加相霉卅给定j ，定义唯一的 r 8 ，t 使得歹一1 = r 啦9 0 + s ，r = 慨+ u ，0 8 口2 口0 ；0 牡 p 咖和 0 t 珈然后令g 1 棚和。卅= l ( s + 地q ；d ，7 ) 最后，对2 口击册9 0 + y ) 和 伽9 0 z + 1 p a + 1 伽q 0 0 + 可) ，定义g 筇= g 1 ，卢一时1 此处，所有的计算都 是模击伽q 0 扛+ y ) 后在1 ，2 ，击伽9 0 + y ) 之间 类似垂直块的部分的分析，有如下一些性质： ( 3 ) 这个定义确定了水平的印且相同因子标号的，。在行或列中都 不重复 ( 4 ) 这部分定义的g 中i n j n i 块列( 行) 内，因子标号出现在连续的相邻 的9 0 酲珈白胡珈) m i c r o 块列( 行) 的集合中 ( 5 ) g o 谚珈 1 且整除g 一1 ，整除g 和 0 1 ，我们的目标是对平衡比z ：y 找出基本情 形知，n 的所矿因子分解此时m = 6 ( q x + 3 ) ，n = 6 + 口y ) ，其中占是最简 分式a ( q 一1 ) z y 9 0 + y ) 的分母，知是基本重数 令g c d ( q ，z ) = ，g c d ( q ，y ) = 劬，因此z = q z x o ，可= q y y o ，g = 缸g o 又因d = g c d ( q - 1 ，z + 可) ，我们可得最小的整数知= 夕以( a ， g o p + 可) ) ，则j = 击q o c z + y ) ， 进而可得基本序对： m = 击g o 扛+ 3 ，) 娅掣= - k q o q , ( z + y ) 等，此处p = 昵2 口0 z o + y o ， n = 击g o 0 + 暑，) 蛔学= 击9 0 0 + 秒) 盖，此处王，= q ；q o x o + 知 因子的大小为q b + ) 2 q ( a o d ) ，因而因子个数为f = 学 引理3 4 ( 【1 2 1 ) d 整除p 和l ， 由此我们可得基本情形的因子个数为f = d ( ) ( ：) 构造因子阵列 f 是击g o 劬扛+ 掣) 等石1 们姒互- r y ，i v 阵列，令知= c b 使得ciq o 且6i 0 + 3 ，) 因为bi + 可) ，首先将f 划分成兰軎| 三铲的阵列g ，其中每块为j g o 锄等 ：g o 詈的矩阵g 的元素是f 的m a i n 块将m a i n 块再划分：9 0 锄：9 0 的 子阵，其中每块为学吾矩阵( 称为m i n i 块) 这里，我们将f 原来的元素， 行和列分别称为简单元素，简单行和简单列 将因子标号集合分成d 个互不相交的子集合五= g 一1 ) 告詈+ j ii1 歹 等： ，1 l d 下标i 表示因子标号集合的型 每个m i n i 块的元素将被给定型的因子标号集合里的所有元素标号，而 每个型也正好填满它因而，这样的m i n i 块通常是某个标准m i n i 块m ( t ) 的 旋转变量，t 是型因为五的大小正好等于m ( t ) 中元素的个数，所以我们 可将五中的因子标号按从左至右，从上而下的自然顺序对m ( t ) 中的元素标 号 构造旋转变量m ( t ；i ，j ) ，将m ( t ) 的行顺次向下平移i 和列向右平移歹个 1 3 完全二部多重图的缉，g 一因子分解 三主要结果 位置m ( t ) = m ( t ；0 ，o ) 注意这里每个觚n i 块的格也应填入知个不同的因子标号但在这个构 造中我们先填c 个不同的因子标号( 知= b c ) 用m ( t ) ，可将每格有c 个因子标号的标准的n l i n i 块s ( t ) 的元素依次标为 m ( t ；0 ，o ) ，m ( t ；1 ，o ) ，m ( 幺c 一1 ，0 ) 和a ( t ) 的元素依次标为m ( t ；0 ，o ) ，m ( 厶0 ，1 ) ， ，m ( t ；0 ，c 一1 ) 然后构造旋转变量j e 7 ( t ；i ，珐将b ( t ) 的行顺次向下平移i c 个 位置且列向右平移歹个位置；和旋转变量a ( t ；i ，歹) ，将a ( t ) 的行向下平移i 个 位置且列向右平移巧个位置 通过血i l i 块b ( t ) 和a ( t ) ，构造基本的m 咖块的样本，分别称作水平的 和垂直的，它们都是由相同型的因子标号集合的m i n i 块组成的 水平样本h ( t ) 和垂直样本v ( t ) 是由m i n i 块组成的：9 0 劬：g o 缸阵列， 记作h ( t ) o 和y ( t ) 巧，1 i ：9 0 和1 j 口0 定义h ( t ) o = a 0 ；0 ， 一1 ) 和v ( t ) o = b ( t ；一1 ，o ) 若西是集合五中的因子标号，则以下结论显然： 一在h ( t ) 中，包含标号的每行都形成子星k ，。苎和缸= 凰，和和且相应在 h ( t ) 中另外行中的子星都是点互不相交的；每个n f l f f l 块的列内，含的简 单列形成了连续的相邻的9 0 个简单列的集合 一在v ( t ) 中，包含标号的每列形成子星甄驰知，相应地在h ( t ) 中另外列 中的子星都是点互不相交的；每个m i n i 块的行内，含的简单行形成了连 续的相邻的q b 个简单行的集合 同样可以从h ( t ) 和v ( t ) 得到旋转变量日( t ；k ，1 ) 和y ( t ；k ，z ) 令日( t ；七，z ) 材= a ( 句k ，i 一1 + z ) 和y ( 句k ，z ) 巧= s ( t ；j 一1 + 七，f ) 显然，以上两个结论依然成立 构造该因子阵列的主要方法是将 0 + 可) 仕+ 可) 的阵列g 中的块用 水平的和垂直的，。块填入然而，不同于前一种方法在此过程中我们还需 要一些混合的水平块 垂直块的放置 首先，放置一系列垂直m m n 块以下，g 的m a l i n 块的下标都是模 + ! ，) 在1 ， ( z + ) 之间且因子标号集合五的下标t 是模d 在1 ，d 之间 给定因子标号集合的型t 因为di ( x + y ) 且9 c d ( z ，y ) = 1 ，就有9 谢( z ，回= 1 ，可将z o 改写成黝= s d + r ，s ，r 是唯一的且0 7 s d q ，令7 ( t ) 卢= 归+ t 一1 】，r ( t ) 卢是