（应用数学专业论文）乘积构形的超可解性及判定构形超可解性的算法.pdf

乘积构形的超可解性及判定构形超可解性的算法 摘要 超平面构形领域近年来受到国际上的广泛关注，其结果在代数，几何， 拓扑，组合，分析( 超几何函数) ，物理( k z 一方程) 等领域有广泛的应用。 中心构形是一类特殊的超平面构形，也是研究一般超平面构形的基础。超 可解构形则是存在模元极大链的特殊中心构形。 随着空问维数的增大，超平面个数的增加，超平面构形的结构会变得 非常复杂，此时判定构形是否为超可解构形也比较复杂。文中讨论了乘积 构形与超可解构形的关系，并得出了乘积构形是超可解构形的充要条件。 通过把超平面中心构形分解为若干因子构形的乘积，我们可以将复杂的中 心构形超可解性的研究归结为对它的因子构形的超可解性的研究，把判定 复杂构形是否为超可解构形的问题转化为判定较为简单的因子构形的是 否为超可解构形的问题。 本文分两部分，第一部分包括篇一章到第四章，讨论了中心超平面构 形乘积的超可解性，第二部分为第五章，给出了一个算法，利用计算机判 定中心超平面构形是否为超可解构形。通过这两部分的内容，理论上解决 了乘积构形是否为超可解构形的问题。 具体的，本文第一章简单介绍了超平面构形理论中的一些基本概念， 给出并证明了一个引理，把超平面构形格中元素的秩归结为了矩阵的秩。 第二章给出并证明了乘积构形格中的几个运算性质，为第三章和第四章的 定理提供理论依据。第三章中首先证明了乘积构形格中元素是模元的充要 1 条件是，每个分量元素均是相应因子构形格中的模元。进而证明了本文的 主要结果：乘积构形是超可解构形的充要条件是每个因子构形都是超可解 构形。第四章对第三章中得到的主要结果做了推广，证明了若各因子构形 均是良分划构形，则乘积构形也是良分划构形。其逆命题是否成立，还需 要做进一步的研究。 第五章利用已有的结论，用计算机语言编写了程序，用来判定给定超 平面中心构形是否为超可解构形。本章详细分析并给出了算法的具体步 骤，并且利用c 语言编写了程序代码，对程序的主要部分给出了必要的注 释，以利于理解。最后，列举了若干个超平面构形的实例，并利用此程序 判定了其超可解性，对与构形是超可解构形的情形，程序给出了一个模元 的极大链。 关键词：乘积构形，中心构形，超可解构形，模元，良分划 s u p e r s o l v a b f l i t yo fp r o d u c ta r r a n g e m e n ta n dap r o g r a m a b s t r a c t r e s e a r c ho fh y p e r p l a n e sd r a w sm o r ea n dm o r ei n t e r n a t i o n a la t t e n t i o n r e c e n t y e a r s t h e r e s u l t so fi th a v e b e e na p p l i e dt o a l g e b r a , g e o m e t r y , c o m b i n a t i o n ，a n a l y s i s ，p h y s i c s ( k z e q u a t i o n ) a n ds oo n c e n t e r e da r r a n g e m e n t i sal 【i n do fs p e c i a lh y p e r p l a n ea r r a n g e m e n t a n di st h eb a s eo fr e s e a r c hf o r c o m m o n l yh y p e r p l a n ea r r a n g e m e n t s u p e r s o l v a b l ea r r a n g e m e n ti ss p e c i a l c e n t e r e da r r a n g e m e n tw h i c he x i s t i n gm a x i m a lm o d u l a rc h a i n s a l o n gw i t ht h ei n c r e a s i n gd i m e n s i o no ft h ea m b i e n ts p a c ea n dt h e n u m b e ro fh y p e r p l a n e s ，t h ea r r a n g e m e mw i l lb e c o m em o r ea n dm o r e c o m p l i c a t e d , a n dd e t e r m i n i n gw h e t h e rt h ea r r a n g e m e n ti ss u p e r s o l v a b l ew i l l a l s ob e c o m ec o m p l i c a t e d t h et h e s i sh a sr e s e a r c h e do nt h er e l a t i o nb e t w e e n p r o d u c ta r r a n g e m e n ta n ds u p e r s o l v a b l ea r r a n g e m e n t ，a n de d u c e dt h ec o n d i t i o n o f p r o d u c ta r r a n g e m e n tb e i n gs u p e r s o l v a b l ea r r a n g e m e n t t h r o u g h d e c o m p o s i n g t h e c o m p l i c a t e da r r a n g e m e n t i n t ot h e p r o d u c t o f s u b a r r a n g e m e n t s ，w ec a na n a l y z et h es u p e r s o v a b i l i t yo fs u b a m n g 锄e n t s i n s t e a do f t h es u p e r s o v a b i l i t yo f t b ec o m p l i c a t e da r r a n g e m e n t t h et h e s i sc o n s i s t so ft w op a r t s t h ef i r s tp a r ti sd i v i d e di n t of o u r c h a p t e r sa n di sm a i n l ya b o u t b a s i ce l e m e n t so f h y p c r p l a n c s t h es e c o n dp a r ti s c h a p t e r5 ，ap r o g r a m ，f o rd e t e r m i n i n gw h e t h e rt h eg i v e na r r a n g e m e n ti s 1 i i s u p e r s o l v a b l e , i sg i v e nb yu s i n gcl a n g u a g e t h r o u g ht h et w op a r t s ，w es o l v e t h ep r o b l e mt h a tw h e t h e rt h ep r o d u c ta r r a n g e n m e n ti ss u p e r s o l v a b l e c o n c r e t e l y , i nc h a p t e r1 ，t h eb a s i c n o t i o na b o u t a r r a n g e m e n t s i s i n t r o d u c e db r i e f l y , a n dal e m m ai sg i v e n , w h i c he s t a b l i s hr e l a t i o n sb e 啊e e n t h er a n ko fm a t r i x sa n dt h er a n ko fa r r a n g e m e n t s i nc h a p t e r2 ，s e v e r a l o p e r a t i o nc h a r a c t e r si nt h el a t t i c eo fp r o d u c ta r r a n g e m e n th a v eb e e ne d u c e d i n c h a p t e r3a n dc h a p t e r4 ，i t i s p r o v e nt h a t ap r o d u c ta r r a n g e m e n ti s s u p e r s o l v a b l ei f , a n do n l yi f , e a c hf a c t o ra r r a n g e m e n ti sa l s os u p e r s o l v a b l e i t i sa l s op r o v e nt h a ti fe a c hf a c t o ra r r a n g e m e n th a san i c ep a r t i t i o n , t h e nt h e p r o d u c ta r r a n g e m e n th a sa l s oan i c ep a r t i t i o n i nc h a p t e r5 ，ap r o g r a m ，f o rd e t e r m i n i n gw h e t h e rt h eg i v e na r r a n g e m e n t i ss u p e r s o l v a b l e ，i sg i v e nb yu s i n gc l a n g u a g e ，i n c l u d i n gt h en e c e s s a r yn o t e s a n da n a l y s e s i nt h ee n d ，s o m ea p p l i c a t i o n so ft h ep r o g r a ma r eg i v e n f o r s u p e r s o l v a b l ea r r a n g e m e n t , am a x i m a lc h a i no fm o d u l a re l e m e n t si sc o m p u t e d k e y w o r d s ：p r o d u c ta r r a n g e m e n t ，c e n t e r e da r r a n g e m e n t ，s u p e r s o l v a b l e a r r a n g e m e n t ，m o d u l a rd e m e n t ，n i c ep a r t i t i o n 符号说明 k实数域或复数域 r 实数域 c复数域 矿 置上的向量空问 超平面 a 超平面构形 r超平面构形的中心 工( a ) 超平面构形a 中超平面的所有非空交的集合 万 超平面构形4 的一个分划 超平面构形 与 的乘积构形 v n 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者签名： ! 挝垒 日期：兰! ! z 生鱼豇亘 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北 京化工大学。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编 学位论文。 注释：本学位论文不属于保密范围，适用本授权书。 作者签名： 监墨堕 日期： 导师签名：生垒 日期： 订j 斗b 铽日 竺! 至4 生坚 第一章绪论 超平面构形是近3 0 年来受到国际上广泛关注的研究领域，其结果在代数、组合、 拓扑、分析( 超几何函数) 、物理( k z - 方程) 等领域有广泛的应用，有关这方面的研 究可以参阅 1 - 1 0 1 1 预备知识】【1 2 】 设矿是域足( 实数域r 或复数域c ) 上的n 维向量空问，矿的一一l 维仿射予空 间称为y 中的超平面。设a = 曷，只 是矿中有限个超平面的集合，称a 是矿中的 超平面构形，记为a = ( a ，矿) 若构形中所有超平面的交非空，则称a 是中心构形， 且称t = r 旧，( 日彳) 为一4 的中心；否则，即构形4 中所有超平面的交为空集时，称一4 是非中心构形。 设一4 = i - , ，皿 ，定义l ( 4 ) 为构形4 中超平面的所有非空交的集合，即有 三( 4 ) = 暇i 1 魄n n 瓯b n 乜i 1 n 吼a ，1 蔓 2 j ) 这里约定 v 三似) ，理解为零个超平面的交。对置y 三( ) ，规定x s y 营x 2 y ，则工似) 在 偏序“”下构成几何偏序集。特别地，当a 是中心构形时，l ( 4 1 构成几何格。对 x 三似) ，称z 的余维数，即行一d i m x 为x 的秩，记为r ( x ) 。约定对x e 三( 爿) ， 4 x = h e 爿i x h 设( ，k ) ，( ，吃) 是超平面构形，令y = 巧。匕，定义( x ， 为乘积构形， 其中 a = 喝。巧i i - i , e ) u k o 巩i 鸩 ) 。容易看出，三( 4 4 ) 兰以4 ) 三( 4 ) ，五。墨五o e 当且仅当五s 恐，誓茎艺 设( 4 ，矿) 是超平面构形，称( j ，】，) l ( a ) x l ( a ) 是一个模对，若对v z l ( a ) 且 z s y ，有z v ( x y ) = ( z v x ) y 。若对v y 工( a ) ，( x ，y ) ，x l ( a ) 都是模对， 则称石是模元。x l ( a ) 是模元当且仅当v y l ( a ) ，有r ( x ) + r o ) = r ( x y ) + r ( x v n 设( 一4 ，y ) 是超平面中心构形，秩r ( a ) = ，y = x o ，五，五= t 为构形格中 的元素，若满足下面两个条件：( 1 ) k ，墨，五均是模元，( 2 ) ，( 置) = f ，f = 1 ，2 ， 则称链矿= x o 五 五= t 是模元极大链。 令r ( a ) = ，若一是中心构形且j 已( 4 ) 有一个模元极大链矿= x o 五 - x a v 毛与y 乃v 咒所以有j o 】，( v 而) o ( 乃v 儿) “s ”，由于而v 而玉且玉v 而屯，咒v 儿咒且乃v 儿咒，所以有( 五v 恐) 0 v y 2 ) - x io 乃，( a i v 而) o o v 儿) 屯。乃由( 五。咒) v ( 而。咒) 的定义知， ( o 乃) v ( 艺。儿) s ( 五v 屯) o ( 弗v 儿) 综上，有等号成立。o 性质3 ( 五o y o ( x z 0 咒) = ( 五 乇) o 咒) 证明 “”，由于五 而s 五且玉“而毛，咒 兄s 咒且咒 咒s 咒，所以有 ( 五 而) 0 ( 舅 咒) 而。乃，( 毛 而) o ( 咒 咒) 而。乃由( 而。咒) ( 而0 儿) 的定 义知( 毛) 0 ( 乃 y o - 2 时也有结论成立，即 五o 0 l ( 4 a ) 是模元的充分必要条件是五是似，) 的模元，1 f 脚。 4 当七= m + l 时，设玉o o + l 1 4 4 a + i ) ，且工( ) ， ( ) 令 一4 = x o - x ，= o o ，由定理l 可知，0 + i 是模元的充分必要条件是， 是( 一4 ，) 的模元且。是“a + 。) 的模元。由归纳假设可知，= o o 靠是三似，) 的模 元的充分必要条件是玉l ( a 。) 的模元，l a i 埘因此，对七= 册+ l 时，也有结论成 立。 综上，有题设成立。0 3 2 乘积构形是超可解构形的充要条件 定理2 超平面构形以x b ，巧。匕) 是超可解构形的充要条件是构形似，k ) ， ( 日，屹) 均是超可解构形。 证明必要性 设o = x o o 玉。弗 e 3 y , = l 是超可解构形似召，巧ok ) 的一个模元极 大链，其中，= ，( 4 b ) ，o = k o 匕，l = t ( a x 3 ) ，玉e ( 一4 ) ，乃e 三( 功，i = o l ，r 由定理1 知毛，弗，i = o ，l ，是模元。 设= r ( a ) ，吒= r ( 聊，则r = 气+ 眨。由吒+ = ，( o y r ) = r ( ) + r ( y ，) ，可知 ，以) = ，i r ( 只) = 吒。由o = ) o ) = 慨) + 慨) ，可知r ( x o ) = 0 ，r ( y o ) = 0 由上可知链包含秩为0 与的元素，下证对v i ( 0 , q ) ，链o = 而茎玉s = 1 包 含秩为i 的元素。 用反证法，假设链o = 毛s 玉s s = l 中不包含秩为k ( 0 k ) 的元素，由于 在链0 = x o o 五。儿 o 只= l 中每一项的秩都比前一项增加l ，又因 r ( 儿，) r ) ，o i | 的元素矛盾。所以对v f 【0 ，】，链o = x o 五 - - 1 包含秩为f 的元素 同理，对v i e 【0 , 5 】，链0 = 3 o 咒s s 只= l 包含秩为i 的元素。 我们把秩相同的元素保留一项，就可以得到模元极大链0 = x o 屯= i 与 o = y o 咒 = 1 所以，k ) ，( 8 ，匕) 是超可解构形。 充分性 令o = x o = l ，o = y o 咒 = 1 分别是构形似，巧) 和( 8 ，) 的 模元极大链 构造构形 ( a x b ，k o 巧) 的一个链 o = x o o 蜘 x o o h 而。魏 而。赡 x i o 以 k 或而 匕。若五 巧，则以至少包含一单元素集，记为 日) ，h 一4 ，此 6 时有王日，故 o 毛而。匕h o k ，所以乃至少包含一个单元素集( h e 吒 若而 匕，则至少包含一个单元素集，记为 l ) ，工8 。，此时有而工，故 五e ) x 2 k o 而巧e l ，所以以至少包含一个单元素分量 k o 埘。 综上，似x 8 ，k o k ) 是良分划构形口 利用数学归纳法可以得到下面推论。 推论3 若，k ) ，l 玉f 七，七e n 是良分划构形，则( x - - - x ，k o o k ) 是 良分划构形。 证明用数学归纳法 由定理3 知，对k = 2 时已有结论。现假设对七= r t l ，坍 2 时也有结论成立，即 以，k ) ，l - i s 掰是良分划构形，则x - - - x 凡，巧o o ) 是良分划构形。 当七= m + l 时，令a = x - - - a ，v = k 0 o ，由定理3 可 知，x - - x 。，k o o 圪+ 。) = 似a 。v o k 。) 是良分划构形的充分条件是 ( a ，y ，) ，( a + 匕+ ，) 是良分划构形。由归纳假设可知( ，v 3 = ( x - - - a ，巧o o ) 是良分划构形，因此，对k = m + 1 时，也有结论成立。 综上，有题设成立。口 另外，若乘积构形( x - - o x a ，k o e v , ) 是良分划构形，那么子构形( 4 ，巧) ， l s i 七，j e n 是否也是良分划构形，还需要做进一步的研究。 第五章判定构形超可解性的算法 已有结论：设 是中心超平面构形，一4 是超可解构形的充分必要条件是存在链 o = a g 4 = ，= 睹( ) ，使得下面两个条件成立 阳，h 4 、 - i ，h 日，j 日e 一i 使日n 日c h 。( 5 1 ) 砖( ) = 砖( 4 一。) + l ( 5 2 ) 由第一章的引理可得，曰n h c 日r a n k ( t ，n 日r h ) = r a n k ( h n ) = 2 。 本章利用上述结论，用c 语言编写了一个算法，来判断构形是否为超可解构形， 并给出了几个具体例子。 5 1 算法综述 程序目的：判断给定中心构形是否为超可解构形 输入：超平面个数i ) u j b ) ；空间维数d i m ；超平面的系数c 【肌m 】【d i m 】 输出：构形的秩；若为超可解构形，输出：t h ea z t a n g c m c n ti ss u p c r s o l v a b l e ，并 输出一个模元极大链。若不是超可解构形，输出t h ea r r a n g e m e n ti ss u p c r s o l v a b l e 要判断构形a 是否为超可解构形，只需知道能否找到a 的一个模元极大链 7 a = a 妄 互4 = 一4 ，( ，= 砖似) ) 且满足条件( 5 1 ) 和( 5 2 ) - ) o f o = a ，只 需找到满足条件的 ， ，- a = 一4 即可。因 的秩为l ，所以 包含的超平面个 数为1 可以分以下几步来求构形的超可解链： 1 确定构形a 的秩，。 2 确定一( 只有n l n l l 种取值) ，执行第3 步；当取遍所有可能仍无解时，则构形不 是超可解构形，执行第6 步。 3 对给定 ，计算符合条件( 5 1 ) 和( 5 2 ) 的a ，符合条件的a 可能有多种，选取一种， 执行第4 步；若无符和条件的，则重复第2 步确定新的 ，直至 取遍所有可能。 4 对绘定的a ，计算符合条件( 5 1 ) 和( 5 2 ) 的 ，符合条件的 可能有多种，选取一 种，执行第5 步；若无符合条件的，则重复第3 步确定新的a ，直至 取遍所有 可能。 5 类似得，求出符合条件的a ，4 ，执行第6 步 6 输出结果 5 2 具体算法 用c 语言来编写此算法。主程序为m a i n o ，用来判定输入构形是否为超可解构形。 程序中调用了2 个子程序，分别是i n tr a n k ( i n tl l l i n tn ) ，i n t i n ti ) 。 为方便解释程序，每行代码前均标有编号，程序中严是注释部分，有关c 语言的概念，可参阅文献b 5 - 2 0 c 语言中数组标号是从0 开始的，为表示计算，记程序中第一个输入的超平面序 号为0 ，第二个输入的超平面序号为l ，第三个输入的超平面序号为2 ，依次类推 5 2 主程序部分 程序的主要部分，内容包括输入数据，计算构形的秩，判定构形是否超可解，结 果输出等。 1 撑i n c l u d e ”m a t h h ” 2 捍d e f i n e m o1 0 ，定义了超平面个数和维数的最大值， 3 i n td i m , h u m ；i r aa m 0 m 0 , j 3 , t f m 0 1 ； 4 n o 砒c m o i m o 丑【m 0 】【m o 】； 幸均为全局变量，各子程序都可以调用， 5 m a i n o 6 i n ti j , k , r , l , m , t r u e l ，t r u e 2 ，c o u n t m 0 ；i n tc l ，c 2 , x ；i n ta g a i n , f i n d , n ； s 7 a g ：p r m t 坟”i n p u t t h e m 瑚l b 盯o f h y p e r p l a n e s ：u ) ； 8 s c a n f ( ”d ”，n i 瑚) ；严输入超平面个数n u m * 9 p r i n t f ( ”i n p u tt h ed i m e n s i o no f v u “) ； 1 0 s c a n f ( ”d “，& d i m ) ；输入空间的维数d i m * 1 1 f o r ( i = 0 ；i n u m ；i 十n 1 2 p r i n t f ( ”i n p u th d a n ”，i + 1 ) ； 1 3 f o r 0 = 0 ；j d i m ；j + + ) 1 4 s c a n f ( ”f ，& c 【i 1 【j 】) ； ，输入每个超平面的系数，用数组c n u m d i m 表示 1 5 t = r a n k ( n m n , 1 ) ；* 调用子程序，计算构形的秩r 吖 1 6 f o r ( i = 0 ；i 雌i 抖) 1 7 c o u a t i = 0 ；计数器c o u n t i 初值设为0 ，标记是否初次计算模元 + i ， 1 8 c l = o ；计数器c l 标记模元a ( 仅含1 个超平面) 超平面序号，初值0 ， 即第一个输入的超平面， 1 9 f o r ( i = o ；( i r ) & & ( c i n u m ) ；i * ) ，第1 9 7 3 行是程序的主要部分，判断构形是否为超可解，并计 算 ，a ，4 2 0 f i n d = 0 ； 幸计数器f i n d 标记是否找到符合条件的模元 + ，初值为o + 2 1 i f 【i = o ) 2 2 a 【o 】【0 = c l ；t 0 = l ；c o u n t 0 = l ；) 计算模元 ，数组t 【i 】标记模元。中包含的超平面构形个数，数组 a 【i 】蜘标记模元a 。中第j 个超平面的序号 2 3 e l s e ，第2 3 7 2 行计算模元， 2 4 f o r ( k = 0 ；k t i - l 】；k 十+ ) 2 5 a 【i 】【k 】= a 【i - l 】【k 】； 2 6 。 i f ( c o u n t i = = o ) * 初次计算模元“，执行程序第2 6 - 弓7 行 2 7 c o u n t i = l ： 2 8 f o r ( 1 = 0 ，t r u e l = l ；( 1 d i m ) & & ( t r u e l 1 ) ；l + + ) + 第2 8 3 5 行计算符合条件2 的，叫 2 9 a 田f h i - l 】- l ； 3 0 t 脚。t 【i 1 】+ 1 ； 3 1 f o r 0 = 0 , t r u e 2 = l ；( i t i - 1 ) & & ( t r u e 2 一1 ) ；j h - ) ) 3 2 i f ( ( a i t i - 1 一a i j ) l l ( r a n k ( t ( i ) ，2 ) ! = i + 1 ) ) ) 调用函数m a k 0 ，计算模元4 l + 。的秩吖 3 3 t r u e 2 = 0 ；t r u e l = 1 ；) 9 e l s et r u e l 2 田： ) f i n d = l ； e l s e 不是初次计算模元a i ，执行程序第3 8 _ - 4 9 行+ ， f o r ( 1 = a i t i - l 】+ l ，t r u e l = 1 ；( 1 d i m ) & & o r u e l = 1 ) ；l + + ) 产第3 9 4 6 行计算符合条件2 的。吖 a 【i 】【t 【i - l 】_ l ； t 【i 】_ 1 - 【i 1 】+ l ； f o r ( j = o , t r u e 2 = 1 ；0 t i - l 】) ( 咖砣一1 ) j + 卜) i f 【( a 【i 】【t i - l 玎- a 【i 】d 】) 0 ( r a n k f r ( i ) 力! = i + l ” ，幸调用函数m k o ，计算模元4 h 1 的秩吖 t r u e 2 f f i 0 ；t r u e l = l ； e l s et r u e l = 0 ； i f ( 1 一- - - - - r ) f i n d = o ； e l s ef i n d = l ； 计数器f i n d - - - - 1 表示找到符合条件( 5 2 ) 的a ，f i n d = o 表 示没有找到附和条件( 5 2 ) 的。 i f ( f m d f f i l ) 若找到符合条件的。，执行程序第5 0 _ _ 6 6 行，扩充 “，并判断。是否符合条件1 ， c 2 f f i l ； x _ t 【i 】； f o r ( 1 = 0 ；l d i m ；l 十n 上述步骤得到的a 。仅为最小集，即a 。仅比 多一个超 平面，程序第5 3 6 3 行对做扩充，使得。不仅满足 条件( 5 2 ) ，而且包含最多的超平面个数 t i - - x + c 2 ； a 【i 】i t 【i 】- l 】= i ； f o r ( j - - ( ，廿u c 2 = l ；( j t 卧1 ) & & ( t m c 2 一1 ) ；i + + ) i ( a 【i 】【t 【i 】1 = a i j ) l l ( r a n k ( t i ( i ) ，2 ) ! = i + 1 ) ) ，调用函数r a n k o ，计算模元a 。的秩叫 t m e 2 = o ； i f ( t r u e 2 = = o ) t i 】= t 【i 】1 ； 1 0 强强孤孔孤拽 诎扎钇瓴 她住舐张锻蚀 孤 儿纪豇 舛鲐锸 孤觋观 6 1 6 2 6 3 6 4 6 5 6 6 6 7 e l s ec 2 = c 2 + 1 ； c o u n t i = l ； i f ( i n ( i ) ! = 1 ) ，调用子程序i n o ，判定模元a 。是否满足条件( 5 1 ) ，若 不满足条件( 5 1 ) ，则设置参数，返回第2 3 行，重新确 定 i ， i - - i - 1 ： e l s e 若没有找到符合条件的4 。，则设置参数，返回第1 9 行，重新确定a ， 6 8 c o u n t i = 0 ； 6 9 i - - i - 2 ； 7 0 i f ( i 一- 1 ) c l = c l + l ； 7 1 ) 7 2 ) 7 3 1 7 4 p r i n t f ( ”瑚呶a 产d 、n ”，r ) ； 7 5 i f f c l 一- - - - d i m ) p r i n t s t h ea r r a n g e m e n ti sn o ts u p e r s o i v a b l e 、n ”) ； ，若计数器c l - - d i m ，此时a 已取遍所有超平面，均无符合 条件的极大超可解链，构形不是超可解构形，输出结果 7 6 e l s e p r m t f ( t h ea x r a n g e m e n ti s 跚p 妁l v 曲l e n ) ； ，若计数器c 1 不等于d i m ，则找到符合条件的极大超可解链， 构形是超可解构形，执行程序第7 6 8 3 行，输出结果吖 7 7 p r i n t 坟“a ( 0 ) = n u l l 、】a ”) ； 7 8 6 呱i = 0 ；i f i + + ) 7 9 p d n 饵”a ( d 卜”，i + 1 ) ； 8 0 f o r ( j = 0 ；j t i l ；j 十n 8 1 p n n t f 【”h 【d 】，”a 【i 】d 】+ 1 ) ； 8 2 i f 0 - t i 】一1 ) p r i n t f ( 峋、n ”) ； ) 8 3 ) 8 4 p r i n t f ( 、n t r ya g a i - ? of o ry e s ，0f o r ) ”) ； 8 5 s e a , i f ( ”d ”，& a 鲥n ) ； 8 6 i f ( a g 舾1 ) g o t oa g ； 8 7 1 5 2 2 子程序r a n k 0 子程序r a n k ( ) 用来计算构形格中元素的秩，所用的方法是高斯消元法，当矩阵某 行的主对角元系数为零时，程序会自动寻找一个相应的系数不为零的行做互换但当 主对角元素不为零，却很小( 接近零) 时，由于计算机存储的位数有限，计算时会产 生误差，越接近零时，误差越大，因此在输入矩阵时，可以做适当的调整( 如交换某 几行的位置) ，尽量避免主对角元系数接近零。 8 8 i n tr a n k ( i n tm , i n tm i 参数m 标记构形的超平面个数，n 为标号，下面有说明+ ， 8 9 f l o a tx ；i n ti j 蚶闻，n 瑚 1 2 ； 9 0 i f f n = 1 ) * n = l 时，计算程序输入构形的秩r 9 1 f o r ( i = o ；i m ；i + + l 9 2 f o r 0 = 0 ；j d i m j + + ) 9 3 r 【i 】d 】= c 【i 】圃； 9 4 e l s ei f ( 庐2 ) * n = 2 时，计算子构形4 的秩， 9 5 f o v c i = o ；i m ；i + + ) 9 6 f o r ( i = 0 ；j d i m j + n 9 7 r 【i 】d 】= c 【a p 】 i 】【j 】； 9 8 e l s ei f ( n _ 3 ) * n = 3 时，计算子程序i n 0 中构形的秩叫 9 9 f o r ( i = o ；i 3 ；i + + ) 1 0 0 f o r o = o ；_ j d i m ：j + + ) 1 0 1 r 【i 】d 】= c 【j 【i 玎【j 1 ； 数组g i l f i l 标记构形中各超平面的系数吖 1 0 2 蜊i = o ；( i 0 o o o 0 0 1 ) 1 0 4 x _ r f i 】f r k 】； 1 0 5 旬坩砒0 d i m ；j + + ) 1 0 6 r 【i 】【j 】- r 【i 】【j 似； 1 0 7 f o r ( k = i + 1 ；k m ；b 斗) 1 0 8 x - r 【k 】【r k 】； 1 0 9 f o r ( 1 - - r k ；l d i m ；l 十n 11 0 r 【k 】【l 】= r 【k 】 1 - x + r 【i 】【l 】；) 1 1 1 r k - - - r k + l ； 1 2 1 1 2 1 1 3 d s e i f f r k ! - - d i m - 1 ) 11 4 n u m 2 - - 咄 1 1 5 d o n u m 2 - - u u m 2 + l ； 1 1 6 r t i r k = r i n u m 2 ； 1 1 7 ) 1 1 8 w h i l c ( ( f a b s ( r i r k ) = 0 0 0 0 0 0 1 ) & & ( n u m 2 b ) ) ； 1 1 9 i f ( n u m 21 - - d i m ) 1 2 0 f o r ( k = 0 ；k 1 2 8 ) 1 2 9 ) 1 3 0 ) 1 3 1 - 吐啪i l c 1 3 2 ) 5 2 3 子程序l n o 子程序i n 0 用来判定扩充后的模元k 是否满足条件( 5 i ) 1 3 3 i n ti n ( i r ai ) 1 3 4 i n t jk m n i , p , q ，s , n u m = 0 ，x ； 1 3 5 1 3 6 i f ( ( t i - t i - 1 】户1 ) 1 ； 幸若模元4 仅比模元多一个超平面，则已满足条件 ( 5 1 ) 。结束子程序，返回值l 吖 e l s e 严若模元凡。比模元。多2 个或多个超平面，则执行程序 第1 3 7 一1 5 0 行+ ， 1 3 7 f o r 0 = t i 1 】j i 【i 】一l j 抖) 1 3 8 f o r ( k = j + 1 ；k t i 玉* ) j 【o 】号a 【i 】d 】； j 1 f a i