SN10093044E-mail:xsl@cccc.net.cnComputer Knowledge and Technology電藺知識(shí)技術(shù)Vol5, No 8, March 2009, pp 1931-1933Tel+86-551-56909635690964相容關(guān)系及其應(yīng)用劉大利,杜成龍(湖北國土資源職業(yè)學(xué)院湖北荊州434002)摘要:該文從相容關(guān)系的概念及沖突關(guān)系的形式描述入手,研究了沖突關(guān)系與相客的的數(shù)學(xué)原理,構(gòu)造了集合的劃分算法,并運(yùn)用劃分算法設(shè)計(jì)程序解決了補(bǔ)考安排問題。關(guān)鍵詞:沖突關(guān)系;相容關(guān)系;集合的劃分;算法中圖分類號(hào):TP312文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):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相容關(guān)系首先給出相容關(guān)系的定義。定義1:給定集合A上的關(guān)系r,若r是自反的,對(duì)稱的則稱r是相容關(guān)系。定義2:設(shè)r是集合A上的相容關(guān)系,若CA,如果對(duì)于C中任意兩個(gè)元素a1,a2有alra2,稱C是相容關(guān)系r產(chǎn)生的相容類。定義3:設(shè)r是集合A上的相容關(guān)系,不能包含在任何其它相容類中的相容類稱作最大相容類。記作Cr定義4:在集合A上給定相容關(guān)系r,其最大相容類的集合稱作集合A上的完全覆蓋。記作C(A)下面進(jìn)行沖突關(guān)系的形式化描述。2形式化描述定義1:由n個(gè)元素構(gòu)成集合S,S=s,2,…snl定義2:由m個(gè)元素構(gòu)成集合C,C=(C1,C2,…Cm],其中Ci是集合S上的集合。定義3:在集合C上,若CnCj≠φ(1≤i≤m,則Ci和沖突,構(gòu)成沖突關(guān)系R。問題:根據(jù)沖突關(guān)系R要求將集合C劃分成互不相交的子集A1A2…Akk≤m),使得任何子集中的元素均無沖突關(guān)系,同時(shí)要求分子集個(gè)數(shù)盡可能少例1設(shè)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要求對(duì)集合C求出滿足前述條件的一個(gè)集合劃分。由定義3可得沖突關(guān)系R=C2CI)C2C5)C2,C8)C2,C9)4C3,C7),(C5,C4(C5.C6)C5C9C6C2),C6C3C7,C5C7,C6C9c4相應(yīng)的逆關(guān)系RC=A2-R是一個(gè)關(guān)系。由相容關(guān)系可能得到有重復(fù)元素的稱為最大相容類的子集所構(gòu)成的完全復(fù)蓋但不是要求的解。通過計(jì)算可得如下多個(gè)解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),沖突關(guān)系求集合的劃分是與相容關(guān)系有關(guān)的問題。由沖突關(guān)系求集合的劃分實(shí)際上是在對(duì)相應(yīng)的RC的完全復(fù)蓋中進(jìn)一步尋找一個(gè)集合劃分。中國煤化工CNMHG收稿日期:2009-01-19作者簡介:劉大利(1%3-),男,高蜓講師,主要從事應(yīng)用數(shù)學(xué)方面的研究;杜威龍(1973-),男,講師,高級(jí)程序員軟件開發(fā)方本欄目賈任編短:剖媛Computer Knowledge and Technology電腦知識(shí)與技術(shù)第5卷第8期2009年3月3數(shù)學(xué)原理對(duì)于沖突關(guān)系、相關(guān)關(guān)系可得如下結(jié)果定理1:若R是C上的一個(gè)沖突關(guān)系,則R是C上的一個(gè)對(duì)稱關(guān)系。根據(jù)定義3可得R在C上是對(duì)稱定理2:若R是C上的一個(gè)沖突關(guān)系,則RC=A2-R是C上的一個(gè)相容關(guān)系A(chǔ)2是對(duì)角線為1的對(duì)稱矩陣,R是一個(gè)對(duì)角線為0的對(duì)稱矩陣,可得A2-R是一個(gè)對(duì)角線為1的對(duì)稱矩陣因此A2-R是一個(gè)相容關(guān)系。定理3:若R是C上的一個(gè)沖突關(guān)系,則RC=A2-R也是一個(gè)沖突關(guān)系。由定理2可得A2-R是一個(gè)相容關(guān)系,是一個(gè)自反的的沖突關(guān)系。定理4:設(shè)C為一個(gè)非空有限集,對(duì)相容關(guān)系R,若S=C1,C2,…Cm]≌C為A的相對(duì)于R的一個(gè)相容類,FCS.HCS、F∩H= FUHcS.C∈SC,與F中的每個(gè)元素相容,則F∪CJ、HUC分別為相容類,且F∪HUC也構(gòu)成相容類, FUICICFUHU{C, HUICICFUHUIC按相容類的定義FU(C}、HU{C構(gòu)成相容類明顯的。 FUHCS在 FUHUICI中任取兩個(gè)元素ab,是一相容類,所以這兩個(gè)元素都相容。故 FUUHUIC是一個(gè)相容類對(duì)于給定的集合C及C上的沖突關(guān)系RRC=A2-R的完全覆蓋C=|B1,B2,…,Bn(n≤m,則按沖突關(guān)系R求集合劃分的問題+U…=A4∩4on=,l-.Jn對(duì)743B,定理4保證所設(shè)計(jì)的算法的正確性。4算法41設(shè)計(jì)思想從某個(gè)元素開始凡與這個(gè)元素?zé)o沖突的元素都劃歸這個(gè)組;再將剩余的元素重新找出互不相沖突的劃歸第2組;直到所有元素劃分完畢42文字描述關(guān)系R用矩陣mm]表示數(shù)組 group(m)存放每個(gè)元素的分組號(hào),初始值為0表示未被分組;數(shù)組 mark(m記元素是否分組0表示未定組,1表示已定組; collision(m表示當(dāng)前組的沖突關(guān)系判斷待定元素i是否屬于當(dāng)前組。1)將某個(gè)元素的沖突關(guān)系放入數(shù)組 collision中,該元素為第一組;2)從第一個(gè)元素起依次掃描數(shù)組 collision,若為0表示無沖突,劃歸該組,置對(duì)應(yīng)mak數(shù)組元素為1,把該元素的沖突關(guān)系與collision數(shù)組對(duì)應(yīng)的各元素分別做或運(yùn)算,直至最后一個(gè)元素;這個(gè)組完成,置數(shù)組 collision為0;3)從mrk數(shù)組中找出一個(gè)未定組的元素,將該元素的沖突關(guān)系放入 collision組,重復(fù)2)步,直至所有元素都被分組算法結(jié)43C語言描述void division(int HIIM]intM, int m, int group(MD*m表示第m個(gè)元素,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ù),實(shí)現(xiàn)樹狀結(jié)構(gòu)的根節(jié)點(diǎn)和相應(yīng)子節(jié)點(diǎn)通過上述源代碼,從Accs數(shù)據(jù)庫中讀取樹狀結(jié)構(gòu)如圖2所3.2樹狀層次結(jié)構(gòu)節(jié)點(diǎn)的操作為了實(shí)現(xiàn)點(diǎn)擊點(diǎn)擊 Tree view的節(jié)點(diǎn),能從數(shù)據(jù)庫中讀取相應(yīng)的文字、圖象、動(dòng)畫等資源需要在 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以上代碼實(shí)現(xiàn)鼠標(biāo)點(diǎn)擊樹狀結(jié)構(gòu)子節(jié)點(diǎn)后執(zhí)行讀取對(duì)應(yīng)子節(jié)點(diǎn)數(shù)據(jù)庫中的文字內(nèi)容圖2樹狀結(jié)構(gòu)4結(jié)論利用C+ Builder中的 Tree View組件,結(jié)合數(shù)據(jù)庫編程,是進(jìn)行樹狀層次結(jié)構(gòu)導(dǎo)航的理想工具。作者利用該方法,在《機(jī)械制造基礎(chǔ)》課程的CA軟件開發(fā)中,順利實(shí)現(xiàn)了對(duì)章、節(jié)、知識(shí)點(diǎn)的多層次復(fù)雜結(jié)構(gòu)的導(dǎo)航使用戶能方便地進(jìn)行課程的學(xué)習(xí)參考文獻(xiàn)[王晟C++ Builder數(shù)據(jù)庫開發(fā)經(jīng)典案例解析M]2版北京:清華大學(xué)出版社200590-1022]張波朱新華基于C++ Builde.0數(shù)據(jù)庫查詢方法M]北京科學(xué)技術(shù)與工程2007:326-32713]劉超唐彬C++ Builder案例開發(fā)集邰M]北京電子工業(yè)出版社,200:88-90中國煤化工CNMHG本芳號(hào)數(shù)擼