SN10093044E-mail:xsl@cccc.net.cnComputer Knowledge and Technology電藺知識技術Vol5, No 8, March 2009, pp 1931-1933Tel+86-551-56909635690964相容關系及其應用劉大利,杜成龍(湖北國土資源職業(yè)學院湖北荊州434002)摘要:該文從相容關系的概念及沖突關系的形式描述入手,研究了沖突關系與相客的的數(shù)學原理,構造了集合的劃分算法,并運用劃分算法設計程序解決了補考安排問題。關鍵詞:沖突關系;相容關系;集合的劃分;算法中圖分類號: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產(chǎn)生的相容類。定義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。問題:根據(jù)沖突關系R要求將集合C劃分成互不相交的子集A1A2…Akk≤m),使得任何子集中的元素均無沖突關系,同時要求分子集個數(shù)盡可能少例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)是所含子集最少的解。由此發(fā)現(xiàn),沖突關系求集合的劃分是與相容關系有關的問題。由沖突關系求集合的劃分實際上是在對相應的RC的完全復蓋中進一步尋找一個集合劃分。中國煤化工CNMHG收稿日期:2009-01-19作者簡介:劉大利(1%3-),男,高蜓講師,主要從事應用數(shù)學方面的研究;杜威龍(1973-),男,講師,高級程序員軟件開發(fā)方本欄目賈任編短:剖媛Computer Knowledge and Technology電腦知識與技術第5卷第8期2009年3月3數(shù)學原理對于沖突關系、相關關系可得如下結果定理1:若R是C上的一個沖突關系,則R是C上的一個對稱關系。根據(jù)定義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]表示數(shù)組 group(m)存放每個元素的分組號,初始值為0表示未被分組;數(shù)組 mark(m記元素是否分組0表示未定組,1表示已定組; collision(m表示當前組的沖突關系判斷待定元素i是否屬于當前組。1)將某個元素的沖突關系放入數(shù)組 collision中,該元素為第一組;2)從第一個元素起依次掃描數(shù)組 collision,若為0表示無沖突,劃歸該組,置對應mak數(shù)組元素為1,把該元素的沖突關系與collision數(shù)組對應的各元素分別做或運算,直至最后一個元素;這個組完成,置數(shù)組 collision為0;3)從mrk數(shù)組中找出一個未定組的元素,將該元素的沖突關系放入 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}以上代碼通過兩重循環(huán),從數(shù)據(jù)庫讀取數(shù)據(jù),實現(xiàn)樹狀結構的根節(jié)點和相應子節(jié)點通過上述源代碼,從Accs數(shù)據(jù)庫中讀取樹狀結構如圖2所3.2樹狀層次結構節(jié)點的操作為了實現(xiàn)點擊點擊 Tree view的節(jié)點,能從數(shù)據(jù)庫中讀取相應的文字、圖象、動畫等資源需要在 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以上代碼實現(xiàn)鼠標點擊樹狀結構子節(jié)點后執(zhí)行讀取對應子節(jié)點數(shù)據(jù)庫中的文字內(nèi)容圖2樹狀結構4結論利用C+ Builder中的 Tree View組件,結合數(shù)據(jù)庫編程,是進行樹狀層次結構導航的理想工具。作者利用該方法,在《機械制造基礎》課程的CA軟件開發(fā)中,順利實現(xiàn)了對章、節(jié)、知識點的多層次復雜結構的導航使用戶能方便地進行課程的學習參考文獻[王晟C++ Builder數(shù)據(jù)庫開發(fā)經(jīng)典案例解析M]2版北京:清華大學出版社200590-1022]張波朱新華基于C++ Builde.0數(shù)據(jù)庫查詢方法M]北京科學技術與工程2007:326-32713]劉超唐彬C++ Builder案例開發(fā)集邰M]北京電子工業(yè)出版社,200:88-90中國煤化工CNMHG本芳號數(shù)擼