相容关系及其应用

SN10093044E-mail:xsl@cccc.net.cnComputer Knowledge and Technology电藺知识技术Vol5, No 8, March 2009, pp 1931-1933Tel+86-551-56909635690964相容关系及其应用刘大利,杜成龙(湖北国土资源职业学院湖北荆州434002)摘要:该文从相容关系的概念及冲突关系的形式描述入手,研究了冲突关系与相客的的数学原理,构造了集合的划分算法,并运用划分算法设计程序解决了补考安排问题。关键词:冲突关系;相容关系;集合的划分;算法中图分类号:TP312文献标识码:A文章编号:10093044200908-1931-03Compatible Relation and its ApplicationLIU Da-li, DU Cheng-longnal CollegeAbstract: In this paper, starting from Compatible relation is introduced and formal description on collision relations is presented, the math-ematical fundamentals of collision relations and compatible relations is studied, algorithm of set division based on collision relations is con-tructed, arrangement for re-examination is solved with this algorithm.Key words: collision relation; compatible relation; set division; algorithm1相容关系首先给出相容关系的定义。定义1:给定集合A上的关系r,若r是自反的,对称的则称r是相容关系。定义2:设r是集合A上的相容关系,若CA,如果对于C中任意两个元素a1,a2有alra2,称C是相容关系r产生的相容类。定义3:设r是集合A上的相容关系,不能包含在任何其它相容类中的相容类称作最大相容类。记作Cr定义4:在集合A上给定相容关系r,其最大相容类的集合称作集合A上的完全覆盖。记作C(A)下面进行冲突关系的形式化描述。2形式化描述定义1:由n个元素构成集合S,S=s,2,…snl定义2:由m个元素构成集合C,C=(C1,C2,…Cm],其中Ci是集合S上的集合。定义3:在集合C上,若CnCj≠φ(1≤i≤m,则Ci和冲突,构成冲突关系R。问题:根据冲突关系R要求将集合C划分成互不相交的子集A1A2…Akk≤m),使得任何子集中的元素均无冲突关系,同时要求分子集个数尽可能少例1设C=(CC2C3C4c5,C6C7,C8C9,S=s1,s2,s3,4,s5,s6,s7,s8.59.510,Cl=sl,C2={sl,2,s5s8s9}C3=1s3,s6,04=s4,s5C5=5,7s10,C6=|3s5,s7,C7={s6,s7}C8={58C9=s9,10要求对集合C求出满足前述条件的一个集合划分。由定义3可得冲突关系R=C2CI)C2C5)C2,C8)C2,C9)4C3,C7),(C5,C4(C5.C6)C5C9C6C2),C6C3C7,C5C7,C6C9c4相应的逆关系RC=A2-R是一个关系。由相容关系可能得到有重复元素的称为最大相容类的子集所构成的完全复盖但不是要求的解。通过计算可得如下多个解1)Al=(C1, C3, C4, C8),A2=(C2, C7), A3=(C5),2)Al=(ClC3,C4C81,A2=C2C7C9),A3=(C5,A4={C6;3)Al=ICI,C6C8,C9). A2=(C2, C4, C7 ).A3=(C3, C54)Al={Cl,C3,CC8,A2={C2,C4C71,A3=C6,C9}5)Al=|ClC4C6C8}A2={C2C7,C9,A3=C3,C5;6)Al=(C1, C3, C5,C8).A2=(C2, C7, C9),A3=(C4. C61其中4)、5)、6)是所含子集最少的解。由此发现,冲突关系求集合的划分是与相容关系有关的问题。由冲突关系求集合的划分实际上是在对相应的RC的完全复盖中进一步寻找一个集合划分。中国煤化工CNMHG收稿日期:2009-01-19作者简介:刘大利(1%3-),男,高蜓讲师,主要从事应用数学方面的研究;杜威龙(1973-),男,讲师,高级程序员软件开发方本栏目贾任编短:剖媛Computer Knowledge and Technology电脑知识与技术第5卷第8期2009年3月3数学原理对于冲突关系、相关关系可得如下结果定理1:若R是C上的一个冲突关系,则R是C上的一个对称关系。根据定义3可得R在C上是对称定理2:若R是C上的一个冲突关系,则RC=A2-R是C上的一个相容关系A2是对角线为1的对称矩阵,R是一个对角线为0的对称矩阵,可得A2-R是一个对角线为1的对称矩阵因此A2-R是一个相容关系。定理3:若R是C上的一个冲突关系,则RC=A2-R也是一个冲突关系。由定理2可得A2-R是一个相容关系,是一个自反的的冲突关系。定理4:设C为一个非空有限集,对相容关系R,若S=C1,C2,…Cm]≌C为A的相对于R的一个相容类,FCS.HCS、F∩H= FUHcS.C∈SC,与F中的每个元素相容,则F∪CJ、HUC分别为相容类,且F∪HUC也构成相容类, FUICICFUHU{C, HUICICFUHUIC按相容类的定义FU(C}、HU{C构成相容类明显的。 FUHCS在 FUHUICI中任取两个元素ab,是一相容类,所以这两个元素都相容。故 FUUHUIC是一个相容类对于给定的集合C及C上的冲突关系RRC=A2-R的完全覆盖C=|B1,B2,…,Bn(n≤m,则按冲突关系R求集合划分的问题+U…=A4∩4on=,l-.Jn对743B,定理4保证所设计的算法的正确性。4算法41设计思想从某个元素开始凡与这个元素无冲突的元素都划归这个组;再将剩余的元素重新找出互不相冲突的划归第2组;直到所有元素划分完毕42文字描述关系R用矩阵mm]表示数组 group(m)存放每个元素的分组号,初始值为0表示未被分组;数组 mark(m记元素是否分组0表示未定组,1表示已定组; collision(m表示当前组的冲突关系判断待定元素i是否属于当前组。1)将某个元素的冲突关系放入数组 collision中,该元素为第一组;2)从第一个元素起依次扫描数组 collision,若为0表示无冲突,划归该组,置对应mak数组元素为1,把该元素的冲突关系与collision数组对应的各元素分别做或运算,直至最后一个元素;这个组完成,置数组 collision为0;3)从mrk数组中找出一个未定组的元素,将该元素的冲突关系放入 collision组,重复2)步,直至所有元素都被分组算法结43C语言描述void division(int HIIM]intM, int m, int group(MD*m表示第m个元素,1≤m≤Mint j, k. m granum, s gc, collision M). mark(M):fork=0;k=l)if(collision[]==0& &mark[j-1F=O)groupij-lFgrpnum;g+-mark-1}=1;for(k=0 kSQL->Add(sql1);Queryl->Active=true;while(! Query l->Eof(forint i=O; KItems->Count: i++)if(Query l->Fields->Fields[l1->AsString==Tree View1->Items->Item[i]->Text)I TTreeNode'pNodelpNodel=Tree Viewl->Items->Item[:Tree viewl->ltems->AddChild(pNodel,QueryI->-Fields->Fields(OH->Value); J}以上代码通过两重循环,从数据库读取数据,实现树状结构的根节点和相应子节点通过上述源代码,从Accs数据库中读取树状结构如图2所3.2树状层次结构节点的操作为了实现点击点击 Tree view的节点,能从数据库中读取相应的文字、图象、动画等资源需要在 Tree View中添加如下代码void_fastcall Tseeform: Tree ViewlChange(TObject*Sender, TTreeNodeNodeAnsiString sql="select*from xiangmu";Query l->Active=falsyl->SQL-→> Clear0ry l->SQL->Add(sq4);for(int i=O iltems->Count; i ++)if (Tree Viewl->ltems->Item[i]->Selected)TLocateOptions Opts;Opts<Locate("II B"Tree viewl->ltems->ltem[i]->Text, Opts)DBMemol->TextQuery1->Fields->Fields[3]->value:M以上代码实现鼠标点击树状结构子节点后执行读取对应子节点数据库中的文字内容图2树状结构4结论利用C+ Builder中的 Tree View组件,结合数据库编程,是进行树状层次结构导航的理想工具。作者利用该方法,在《机械制造基础》课程的CA软件开发中,顺利实现了对章、节、知识点的多层次复杂结构的导航使用户能方便地进行课程的学习参考文献[王晟C++ Builder数据库开发经典案例解析M]2版北京:清华大学出版社200590-1022]张波朱新华基于C++ Builde.0数据库查询方法M]北京科学技术与工程2007:326-32713]刘超唐彬C++ Builder案例开发集邰M]北京电子工业出版社,200:88-90中国煤化工CNMHG本芳号数撸