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

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