相容關(guān)系及其應用

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