“離散數(shù)學(xué)”求解關(guān)系的傳遞閉包方法,離散數(shù)學(xué)論文

“離散數(shù)學(xué)〞求解關(guān)系的傳遞閉包方法,離散數(shù)學(xué)論文摘要：“離散數(shù)學(xué)〞是計(jì)算機(jī)相關(guān)專業(yè)的核心課程，而關(guān)系是“離散數(shù)學(xué)〞中刻畫事物間內(nèi)在規(guī)律性的數(shù)學(xué)模型，是數(shù)據(jù)構(gòu)造及數(shù)據(jù)庫等很多后續(xù)課程的基礎(chǔ)。由于在關(guān)系中，求解關(guān)系的傳遞閉包，是學(xué)生普遍比擬難把握的內(nèi)容，也是出錯最多的地方，本文基于此背景介紹了求解關(guān)系的傳遞閉包的四種方式方法，并對同一個關(guān)系閉包問題的四種方式方法進(jìn)行比擬，這些方式方法固然都能用來很好地求解關(guān)系的傳遞閉包，但是關(guān)系圖法最為適用，學(xué)生比擬容易把握，進(jìn)而有效提高了教學(xué)質(zhì)量。本文關(guān)鍵詞語:離散數(shù)學(xué),關(guān)系;傳遞閉包:Abstract：Discretemathematicsisthecorecourseofcomputer-relatedmajors,andrelationshipisamathematicalmodelthatdepictstheinherentregularitybetweenthingsindiscretemathematicsandisthebasisofmanysubsequentcoursessuchasdatastructuresanddatabases.Becauseintherelationship,solvingthetransitiveclosureoftherelationshipisgenerallymoredifficultforstudentstomaster,anditisalsotheplacewiththemostmistakes.Basedonthisbackground,thisarticleintroducesseveralmethodsforsolvingthetransitiveclosureoftherelationshipandcomparesthefourmethodsofthepackageproblemofthesamerelationship.Althoughthesemethodscanbeusedtosolvethetransitiveclosureoftherelationship,theyaremostsuitablefortherelationshipgraphmethod.Thestudentsareparticularlyeasytomaster,whicheffectivelyimprovesthequalityofteaching.Keyword：discretemathematics;relations;transitiveclosures;sets;1、引言“離散數(shù)學(xué)〞是計(jì)算機(jī)相關(guān)專業(yè)的一門專業(yè)基礎(chǔ)課，其教學(xué)內(nèi)容與高校數(shù)學(xué)專業(yè)課程極為密切，但學(xué)習(xí)該課程的大多為計(jì)算機(jī)相關(guān)專業(yè)學(xué)生，該門課程也是很多課程必不可少的先行課程，如操作系統(tǒng)、數(shù)據(jù)構(gòu)造、程序設(shè)計(jì)、數(shù)據(jù)庫、人工智能、算法設(shè)計(jì)與分析等[1]。學(xué)生通過學(xué)習(xí)“離散數(shù)學(xué)〞課程，能夠把握處理離散構(gòu)造的描繪敘述工具和方式方法，提高邏輯推理能力和抽象思維能力[2]。眾所周知，關(guān)系是“離散數(shù)學(xué)〞中刻畫事物間內(nèi)在規(guī)律性的數(shù)學(xué)表示，“離散數(shù)學(xué)〞中所有的內(nèi)容都能夠用關(guān)系進(jìn)行描繪敘述，關(guān)系在數(shù)學(xué)領(lǐng)域有重要作用，廣泛應(yīng)用于計(jì)算機(jī)科學(xué)技術(shù)中，而且關(guān)系也是數(shù)據(jù)構(gòu)造及數(shù)據(jù)庫等很多后續(xù)課程的基礎(chǔ)[3]。在數(shù)學(xué)中，表示兩個元素間的關(guān)系稱為“二元關(guān)系〞,簡稱“關(guān)系〞。設(shè)A,B為集合，A×B的任意子集叫做A到B的二元關(guān)系，它是一個二元組的集合，即R={(x,y)/x∈A,且y∈B}。十分當(dāng)A=B時稱為集合A(或B)上的二元關(guān)系[4]。學(xué)生在初學(xué)關(guān)系時，會感到十分困難，主要是關(guān)系中的定義和定理太多，而且定義比擬抽象，由于“離散數(shù)學(xué)〞課時本來就不是很多，那么分配到關(guān)系上的課時就更少了，對關(guān)系的閉包的學(xué)習(xí)是很粗略的，求關(guān)系的傳遞閉包是學(xué)生普遍難把握的，也是出錯最多的。所以本文介紹幾種求定義在有限集合上的關(guān)系的傳遞閉包的方式方法[5]。給定一個二元關(guān)系R,它不一定具有某種性質(zhì)(比方自反性、對稱性、傳遞性),而我們又想讓它具有這些性質(zhì)，就需要在關(guān)系R中添加一些二元組構(gòu)成一個新的關(guān)系，使它具有我們需要的性質(zhì)，但是又希望添加最少的二元組，即添加的二元組盡可能得少[6]。通過這樣的方式方法產(chǎn)生新的關(guān)系，就是關(guān)系的閉包運(yùn)算，主要有三種閉包：自反閉包r(R)、對稱閉包s(R)、傳遞閉包t(R)。學(xué)生對自反閉包和對稱閉包的求法把握很好，基本都能正確求出，而對傳遞閉包的計(jì)算，大多數(shù)同學(xué)感覺很難，假如是關(guān)系R比擬簡單，牽涉到的二元組比擬少，大部分同學(xué)還是能夠求出來的，但是對于略微復(fù)雜點(diǎn)的關(guān)系，學(xué)生求傳遞閉包的時候，不是少添加了一些二元組，就是添加了一些不必要的二元組[7]。2、求解關(guān)系的傳遞閉包方式方法2.1、定理法定理1設(shè)關(guān)系R是集合A上的二元關(guān)系，|A|=n≥1,則R的傳遞閉包[8]t(R)=∪i=1nRi=R1∪R2∪R3∪...∪Rn,例如，集合A={a,b,c,d},A上的二元關(guān)系R={(a,a),(a,b),(b,a),(b,c),(c,d)},利用定理1求關(guān)系的傳遞閉包，R2={(a,a),(a,b),(a,c),(b,a),(b,b),(b,d)},R3=R2。R={(a,a),(a,b),(a,c),(b,b),(b,c),(a,d)},R4=R3。R={(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d)},t(R)=R∪R2∪R3∪R4={(a,a),(a,b),(b,a),(b,c),(c,d),(a,c),(b,b),(b,d),(a,d)},以上用到了關(guān)系的復(fù)合運(yùn)算：定義1[8]設(shè)A,B,C是集合，若R?A×B,S?B×C,則關(guān)系R與關(guān)系S的復(fù)合R。S定義為：R。S={(x,z)|x∈A,z∈C,?y∈B,使得(x,y)∈R,(y,z)∈S}[4]。以上利用定理1求關(guān)系的傳遞閉包的方式繁瑣，假如集合A中元素個數(shù)過多，則計(jì)算量過于大了。2.2、觀察驗(yàn)證法在關(guān)系R中觀察，假如存在類似(x,y),(y,z)的二元組，則在R中添加二元組(x,z)然后驗(yàn)證關(guān)系R是不是具有傳遞性，假如具有傳遞性，則添加二元組后的關(guān)系R就是傳遞閉包t(R),否則，繼續(xù)在R中添加二元組，再進(jìn)行驗(yàn)證，直到R具有傳遞性為止。例如集合A={a,b,c,d},A上的二元關(guān)系：R={(a,a),(a,b),(b,a),(b,c),(c,d)},如今利用方式方法二求關(guān)系的傳遞閉包。通過觀察，我們能夠發(fā)現(xiàn)(b,a)∈R,(a,b)∈R,(a,b)∈R,(b,c)∈R,(b,c)∈R,(c,d)∈R所以能夠在R中添加二元組(b,b),(a,c),(b,d)。此時，關(guān)系R={(a,a),(a,b),(b,a),(b,c),(c,d),(b,b),(a,c),(b,d)},如今利用下面的定理2驗(yàn)證R是不是具有傳遞性，由于R。R={(a,a),(a.b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d)}?R,所以此時R不具有傳遞性，再觀察此時的關(guān)系R,能夠發(fā)現(xiàn)(a,b)∈R,(b,d)∈R,或者(a,c)∈R,(c,d)∈R,所以需要再添加二元組(a,d),此時R={(a,a),(a,b),(b,a),(b,c),(c,d),(b,b),(a,c),(b,d),(a,d)},如今再次利用定理2驗(yàn)證R是不是具有傳遞性R。R={(a,a),(a.b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d)}?R,所以此時R具有傳遞性。定理2[8]設(shè)R?A×A,則R在A上傳遞的充要條件是R。R?R。2.3、關(guān)系圖法利用關(guān)系圖的方式方法來求傳遞閉包，就不會漏掉一些二元組，介紹該方式方法之前，先介紹與之相關(guān)的兩個概念：(1)假如頂點(diǎn)vi到頂點(diǎn)vj沒有直接的有向邊連接，但是卻能夠通過其他有向邊相通，即頂點(diǎn)vi頂點(diǎn)vj之間存在通路，則稱頂點(diǎn)vi與頂點(diǎn)vj是可達(dá)但不是可直達(dá)的；(2)假如頂點(diǎn)vi與頂點(diǎn)vj存在有向邊vi,vj,則稱頂點(diǎn)vi與頂點(diǎn)vj是可直達(dá)的。顯然，兩個頂點(diǎn)之間可直達(dá)必可達(dá)，但是可達(dá)不一定可直達(dá)[4]。該方式方法的算法如下：設(shè)關(guān)系R是集合A上的關(guān)系，|A|=n,在關(guān)系R的關(guān)系圖中，判定任意兩個頂點(diǎn)vi到vj能否可達(dá)?(1)若頂點(diǎn)v1到任意頂點(diǎn)vi(i=1,2,3,...,n)能否可達(dá)，假如可達(dá)，再斷定能否可直達(dá)，假如可達(dá)但不可直達(dá)，則添加一條直達(dá)的邊v1,vi。類似的，對于A中所有的頂點(diǎn)，都斷定與所有頂點(diǎn)的關(guān)系。(2)其他情況(可直達(dá)與不可達(dá)),都不需要再添加邊。即若兩個任意頂點(diǎn)vi、vj不可達(dá)，則不需要添加邊，若兩個任意頂點(diǎn)vi、vj可直達(dá)，也不需要添加邊[4]。舉例講明如下：設(shè)集合A={a,b,c,d},A上的二元關(guān)系R={(a,a),(a,b),(b,a),(b,c),(c,d)},R的關(guān)系圖如此圖1所示，求關(guān)系R的傳遞閉包t(R)。圖1二元關(guān)系R的關(guān)系圖分析如下：(1)檢查頂點(diǎn)aa點(diǎn)可達(dá)a點(diǎn)，并且可直達(dá)a點(diǎn)(由于存在邊(a,a)),所以不需要添加邊；同理，a點(diǎn)可達(dá)b點(diǎn)，并且可直達(dá)b點(diǎn)，所以不需要添加邊；a點(diǎn)可達(dá)c點(diǎn)，但是不可直達(dá)c點(diǎn)(由于不存在邊(a,c)),所以添加一條直達(dá)的邊(a,c);a點(diǎn)可達(dá)d點(diǎn)，但是不可直達(dá)d點(diǎn)，所以添加一條直達(dá)的邊(a,d);(2)檢查頂點(diǎn)bb點(diǎn)可達(dá)a點(diǎn)，并且可直達(dá)a點(diǎn)，所以不需要添加邊；b點(diǎn)可達(dá)b點(diǎn)，但是不可直達(dá)b點(diǎn)，所以添加一條可直達(dá)的邊(b,b);b點(diǎn)可達(dá)c點(diǎn)，并且可直達(dá)c點(diǎn)，所以不需要添加邊；b點(diǎn)可達(dá)d點(diǎn)，但是不可直達(dá)d點(diǎn)，所以添加一條可直達(dá)的邊(b,d);(3)檢查頂點(diǎn)cc點(diǎn)不可達(dá)a點(diǎn)，所以不需要添加邊；c點(diǎn)不可達(dá)b點(diǎn)，所以不需要添加邊；c點(diǎn)不可達(dá)c點(diǎn)，所以不需要添加邊；c點(diǎn)可達(dá)d點(diǎn)，并且可直達(dá)d點(diǎn)，所以不需要添加邊；(4)檢查頂點(diǎn)dd點(diǎn)不可達(dá)a點(diǎn)，所以不需要添加邊；d點(diǎn)不可達(dá)b點(diǎn)，所以不需要添加邊；d點(diǎn)不可達(dá)c點(diǎn)，所以不需要添加邊；d點(diǎn)不可達(dá)d點(diǎn)，所以不需要添加邊；綜上所述，可得t(R)={(a,a),(a.b),(b,a),(b,c),(c,d),(a,c),(a,d),(b,b),(b,d)}。2.4、矩陣法根據(jù)關(guān)系的矩陣可以以求出關(guān)系的傳遞閉包，給定有限集合A上的關(guān)系R,R的傳遞閉包的關(guān)系矩陣等于：MR∞=MR∨MR2∨MR3∨...,華而不實(shí)MR表示關(guān)系R的關(guān)系矩陣[6]。設(shè)集合A={a,b,c,d},A上的二元關(guān)系R={(a,a),(a,b),(b,a),(b,c),(c,d)},則MR而這里?表示布爾矩陣的布爾積，因而有MR∞=MR∨MR2∨MR3∨MR4假如寫成關(guān)系的集合形式如下t(R)=R∞={(a,a),(a.b),(b,a),(b,c),(c,d),(a,c),(a,d),(b,b),(b,d)}。3、比擬分析將以上四種求解關(guān)系傳遞閉包的方式方法應(yīng)用于實(shí)際教學(xué)中，通過對學(xué)生發(fā)放問卷和分析往年考試題目了解以上四種求解關(guān)系的傳遞閉包的方式方法在實(shí)際教學(xué)中的情況。(1)計(jì)算機(jī)與信息工程學(xué)院2022級物聯(lián)網(wǎng)工程專業(yè)和計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)共199名同學(xué)進(jìn)行問卷調(diào)查情況如下：表1學(xué)生運(yùn)用求解關(guān)系傳遞閉包的方式方法的調(diào)查問卷結(jié)果通過調(diào)查問卷分析表示清楚，有41.2%的學(xué)生覺得求解關(guān)系的傳遞閉包很難，29.1%的學(xué)生覺得比擬難，只要12.1%的學(xué)生覺得很容易。而在求解關(guān)系的傳遞閉包方式方法上，使用關(guān)系圖法的學(xué)生有47.7%,采用觀察驗(yàn)證法的學(xué)生有32.2%,運(yùn)用定理法的學(xué)生有16.1%,利用矩陣法的學(xué)生有4.0%,由此能夠看出，使用關(guān)系圖法來求解關(guān)系的傳遞閉包的學(xué)生最多。有45.2%的學(xué)生覺得關(guān)系圖法最方便且正確率最高，35.2%的學(xué)生覺得觀察驗(yàn)證法最方便，13.1%的學(xué)生覺得定理法最方便，6.5%的學(xué)生覺得矩陣法最合適，由此表示清楚，關(guān)系圖法是在求解關(guān)系的傳遞閉包中最受學(xué)生喜歡的一種方式方法。(2)近兩年計(jì)算機(jī)與信息工程學(xué)院開設(shè)“離散數(shù)學(xué)〞課程的四個專業(yè)共523人的期末考試試卷中求解關(guān)系的傳遞閉包的考試題目統(tǒng)計(jì)分析情況。表2近兩個學(xué)年期末考試卷中求解關(guān)系的傳遞閉包的考試題目統(tǒng)計(jì)分析表由表2講明，學(xué)生在求解關(guān)系的傳遞閉包時使用關(guān)系圖法的人數(shù)到達(dá)52.2%,正確率為69.6%,采用觀察驗(yàn)證法的學(xué)生占29.6%,正確率為32.2%,運(yùn)用定理法的學(xué)生占16.2%,正確率為47.0%,利用矩陣法的學(xué)生占2.0%,正確率為40.0%,這表示清楚關(guān)系圖法是在求解關(guān)系的傳遞閉包中最受學(xué)生喜歡的一種方式方法，并且正確率也是最高的。4、結(jié)束語本文介紹了求關(guān)系的傳遞閉包的幾種方式方法，從這些方式方法的介紹和應(yīng)用中，能夠看出：定理法比擬繁瑣，需要對關(guān)系的復(fù)合運(yùn)算把握十分熟練，并且假如集合A中元素個數(shù)過多，則計(jì)算量過于大了。而觀察驗(yàn)證法的優(yōu)點(diǎn)在于比擬直觀，但是其缺點(diǎn)是最容易漏掉一些二元組。相對于觀察驗(yàn)證法而言，關(guān)系圖法固然不容易漏掉二元組，但是卻需要學(xué)