離散數(shù)學(xué)中的閉包概念及應(yīng)用

吳明芬，瞿赟昀

（五邑大學(xué) 計(jì)算機(jī)學(xué)院 廣東江門529020）

0 引言

離散數(shù)學(xué)以研究離散量的結(jié)構(gòu)和相互關(guān)系為主要目標(biāo)，其研究對(duì)象一般是有限或可數(shù)個(gè)元素組成的集合，所以它很好地描述了計(jì)算機(jī)科學(xué)離散性的特點(diǎn)［1－5］.離散數(shù)學(xué)作為計(jì)算機(jī)科學(xué)領(lǐng)域最有效的一種數(shù)學(xué)工具，從70年代初，國外就已經(jīng)作為一門課程正式列入計(jì)算機(jī)科學(xué)和一些工程學(xué)系的教學(xué)計(jì)劃中.

數(shù)學(xué)是揭示事物數(shù)量與形體本質(zhì)聯(lián)系的學(xué)科，教學(xué)中可以挖掘出的幽默元素是很多的，一個(gè)形象巧妙的比喻，一個(gè)十分貼切的類比，既能反映數(shù)學(xué)概念方法的簡單直觀，又將生活中形象的現(xiàn)象與枯燥抽象的數(shù)學(xué)聯(lián)系起來，其中的含義回味悠長，產(chǎn)生出雅致的數(shù)學(xué)幽默［6－14］.作者主要探討離散數(shù)學(xué)中一些顯性閉包概念、隱性閉包概念及針對(duì)它們的教學(xué)方法設(shè)計(jì).最后介紹了傳遞閉包的算法及相關(guān)應(yīng)用.

1 離散數(shù)學(xué)中顯性的閉包概念

1.1 二元關(guān)系的閉包

在離散數(shù)學(xué)中，關(guān)系理論是其一個(gè)重要的組成部分，它的知識(shí)點(diǎn)主要包括關(guān)系的性質(zhì)、關(guān)系的復(fù)合、逆運(yùn)算和閉包運(yùn)算、關(guān)系的劃分和覆蓋，以及等價(jià)關(guān)系、相容關(guān)系、序關(guān)系幾種特殊的關(guān)系.可以通過求關(guān)系的傳遞閉包來實(shí)現(xiàn)傳遞性的判斷，而傳遞閉包本身在圖論中有很好的應(yīng)用價(jià)值.所以二元關(guān)系閉包是一個(gè)重要的概念，在計(jì)算機(jī)科學(xué)中有著廣泛的應(yīng)用.

關(guān)系的閉包是計(jì)算機(jī)專業(yè)本科生第一次正式接觸閉包的概念，幾乎所有的教材資料都是這樣定義的［1－4］.

定義1：設(shè)R是集合A上二元關(guān)系，稱R′為R的自反閉包（對(duì)稱閉包，傳遞閉包），如果R′滿足：

（1）R′是自反的（對(duì)稱的，傳遞的）；

（3）對(duì)A上任意關(guān)系R″，若R″滿足上面的條件（1）和（2），則

一個(gè)關(guān)系R的自反閉包、對(duì)稱閉包和傳遞閉包分別記作r（R）、s（R）、t（R），也稱r，s，t為閉包運(yùn)算（算子），它們作用于關(guān)系R后，分別產(chǎn)生包含R的最小的自反關(guān)系、對(duì)稱關(guān)系和傳遞關(guān)系.

首先介紹凸平面區(qū)域及凸幾何體的概念.通過畫幾個(gè)圖，舉幾個(gè)生活中的例子，學(xué)生就可以判斷一個(gè)平面區(qū)域或幾何體是不是凸的，但是它們的數(shù)學(xué)定義又是怎樣的呢？

定義2：任意選取區(qū)域內(nèi)的兩個(gè)點(diǎn)，它們的連線也在區(qū)域內(nèi)，則該區(qū)域就是一個(gè)凸的區(qū)域.

在定義2的基礎(chǔ)上再引出一個(gè)區(qū)域的凸閉包的概念：如果一個(gè)區(qū)域D不是凸的，適當(dāng)放大后的區(qū)域D’是凸的，且少放大一點(diǎn)都不是凸的，即D’是包含D的最小凸區(qū)域，稱之為原來區(qū)域D的凸閉包.

關(guān)系閉包的基本思想：假設(shè)關(guān)系R不具有性質(zhì)P，可以在R中添加一些二元序?qū)?，使之具有性質(zhì)P，并希望添加的二元序?qū)ΡM可能的少.舉例如下：

例1：設(shè)R＝ ｛（a，a），（a，c），（c，b）｝是集合A＝ ｛a，b，c｝上的一個(gè)二元關(guān)系，且不是自反、對(duì)稱、傳遞的.將R適當(dāng)放大，添加最少的序?qū)?，使之分別滿足自反、對(duì)稱、傳遞性.

和同學(xué)一起尋找到以下結(jié)果：

之后再介紹二元關(guān)系的閉包定義1.

1.2 無向圖的閉包

圖論中關(guān)于一個(gè)圖的閉包概念［1］描述如下：

定義3：給定無向圖G＝＜V，E＞，｜V｜＝n，圖G的閉包是由G通過相繼地用邊連接兩個(gè)其度數(shù)之和至少為n的不鄰接的結(jié)點(diǎn)，直到不能如此進(jìn)行為止而得到的圖，稱為圖G的閉包C（G）.

在這個(gè)定義中，是在不增加點(diǎn)的前提下，將圖G適當(dāng)放大，對(duì)u，v∈V，u與v間沒有邊關(guān)聯(lián)，依據(jù)條件deg（u）＋deg（v）≥n，就將邊（u，v）添加進(jìn)去，直至沒有邊可以加入為止.即是在滿足條件下可以加入G的最多的邊后得到閉包C（G）.課堂上給同學(xué)們舉個(gè)例子示范一下，如下圖1，以幫助理解.

圖1 圖的閉包生成過程Fig.1 The closure of graph gener ating process

2 離散數(shù)學(xué)中隱式的閉包概念

所謂隱式的閉包概念，我們指的是那些沒有直接說明是什么的閉包，但是這些概念具有閉包特性.閉包的特性是適當(dāng)放大，且是滿足某性質(zhì)（條件）的最小的對(duì)象集合.

2.1 線性代數(shù)中的隱性閉包概念

在線性代數(shù)中有關(guān)于和空間和生成子空間的概念［6］，并有以下的結(jié)論.

其實(shí)結(jié)論1中兩個(gè)子空間的和空間，本質(zhì)上就是包含U和W的最小子空間，即具有閉包的特性：集合U∪W 一般情況下不是Rn的子空間，將U∪W 適當(dāng)放大，使之成為Rn的子空間，且是最小的（添加元素最少的）.課堂上可以給個(gè)這樣的例子：在二維平面R2上，U，W分別是過原點(diǎn)的兩條直線，那么它們都是R2的子空間，但是U∪W不是R2的子空間，除非U，W 是同一條直線.此時(shí)U＋W 又是什么呢？可以通過向量的加法運(yùn)算，即同學(xué)們?cè)谥袑W(xué)就熟悉的平行四邊形的對(duì)角線法，說明這樣的向量可以是R2中的任意一個(gè)向量，從而得到U＋W ＝R2.

結(jié) 論 2：設(shè) α1，α2，…，αs∈ Rn，則 集 合2，…，s｝是Rn的子空間，并稱為是由向量α1，α2，…，αs生成的子空間.

其實(shí)結(jié)論2中的span（α1，α2，…，αs）就相當(dāng)于集合 ｛α1，α2，…，αs｝關(guān)于子空間這個(gè)性質(zhì)的閉包，因?yàn)閟pan（α1，α2，…，αs）就是包含 ｛α1，α2，…，αs｝的最小子空間。例如R2中的兩個(gè)向量e1＝（1，0）T，e2＝ （0，1）T，則由它們兩個(gè)向量生成的子空間span（e1，e2）＝R2.

2.2 圖論中的隱性閉包概念

圖論［1－4］中這樣的概念比較多，我們?cè)谶@里只是介紹幾個(gè)比較難理解的概念，針對(duì)這些概念，我們用閉包的思想和構(gòu)造操作，以“相對(duì)直觀”的意義，用深入淺出的方法講授，達(dá)到幫助同學(xué)們對(duì)概念的歸類掌握和理解.

連通分支：設(shè)G＝＜V，E＞是一個(gè)無向圖，稱G的子圖G1是G的一個(gè)連通分支，如果G1是連通的，且是滿足連通性的最大子圖.

事實(shí)上這個(gè)概念就是將G的連通子圖放大，放大到一個(gè)臨界狀態(tài)，當(dāng)前的子圖是連通的，再放大就不連通了.這個(gè)就是包含初始連通子圖的最大連通子圖，即為一個(gè)連通分支.顯然連通分支的概念是具有閉包特性的，這樣解釋后就很容易通過例子幫助學(xué)生掌握連通分支的概念及怎么找一個(gè)無向圖的連通分支.

強(qiáng)分圖（單向分圖、弱分圖）：設(shè)G＝＜V，E＞ 是一個(gè)有向圖，G1＝ （V1，E1）是G的子圖，如果G1是強(qiáng)連通圖（單向連通圖、弱連通圖），且沒有包含G1的更大的子圖是強(qiáng)連通圖（單向連通圖、弱連通圖），則稱G1是G的強(qiáng)分圖（單向分圖、弱分圖）.

這3個(gè)概念都具有閉包的特性，就是要將G的強(qiáng)連通（單向連通、弱連通）子圖進(jìn)行放大，放大到一個(gè)臨界狀態(tài)，當(dāng)前的子圖是強(qiáng)連通（單向連通、弱連通）的，再放大就不是強(qiáng)連通（單向連通、弱連通）了.找到的這個(gè)子圖就是包含初始強(qiáng)連通（單向連通、弱連通）子圖的最大強(qiáng)連通（單向連通、弱連通）子圖.如此分析了概念，然后再構(gòu)造三個(gè)有向圖：1）一個(gè)不是強(qiáng)連通但是單向連通的；2）一個(gè)不是單向連通但是弱連通的；3）一個(gè)不是弱連通的.和同學(xué)們一起按照上面閉包的特性去尋找強(qiáng)分圖（單向分圖、弱分圖）.

點(diǎn)（邊）割集：設(shè)G＝＜V，E＞是一個(gè)無向連通圖，對(duì)V1?V（E1?E），G－V1（G－E1）是不連通的圖，且對(duì)任意的V2?V1（E2?E1），GV2（G－E2）是連通的圖，則稱V1（E1）是圖G的一個(gè)點(diǎn)（邊）割集.

在這兩個(gè)概念里，點(diǎn)割集就是使連通圖G變成不連通圖需要?jiǎng)h除的極大點(diǎn)集，少一個(gè)點(diǎn)還是連通的；邊割集就是使連通圖G變成不連通圖需要?jiǎng)h除的極大邊集，少一條邊還是連通的.按照這個(gè)思想，通過實(shí)例圖形與同學(xué)一起尋找點(diǎn)割集、邊割集，并且自然會(huì)發(fā)現(xiàn)一個(gè)圖的點(diǎn)割集、邊割集不是唯一的，所含的點(diǎn)（邊）數(shù)也可以不同，從而很自然地就可以引出一個(gè)連通圖的點(diǎn)連通度及邊連通度的概念.

我們發(fā)現(xiàn)用閉包的特性來分析、講解這些概念，就為同學(xué)們理解這一類的概念找到一個(gè)幾乎統(tǒng)一的格式，不僅使概念變得容易理解，且找到了可以實(shí)現(xiàn)的操作方法和途徑.

2.3 代數(shù)系統(tǒng)中的隱性閉包概念

代數(shù)系統(tǒng)及其子系統(tǒng)都有生成的概念，群、環(huán)、域、模和格等都一樣［8］.通過一些對(duì)象元素生成滿足相關(guān)條件的子系統(tǒng)，這些概念的教學(xué)都可以借助閉包的特性來類比.下面以群和域中的幾個(gè)概念的處理為例.

定義4 （生成子群）［2］：設(shè) （G，·）是一個(gè)群，B是群G的非空子集，將G的所有包含B的子群的交記作＜B＞，即：

從生成子群的定義可以看出，＜B＞是G中包含B的最小子群，顯然具有閉包的特性。其實(shí)我們可以證明，＜B＞中元素恰好為形式：其中ai是B 中的元素或其逆元，Z＋是正整數(shù)的集合.即對(duì)集合B添加所有這種形式的元素就可以得到閉包（生成子群）＜B＞.特別地，如果B只含一個(gè)元素b，那么＜B＞稱為是循環(huán)子群，由元素b生成的循環(huán)子群，并簡記為＜b＞.例如對(duì)于整數(shù)加群，由2生成的子群是＋6）中，由2生成的子群是 ＜2＞＝ ｛0，2，4｝.

利用生成子群的思想及拉格朗日定理，我們就可以與同學(xué)們一起求解一些熟悉的有限群的全部子群.如可以求得（?8，＋8）的非平凡子群有兩個(gè)，（?12，＋12）的非平凡子群有四個(gè)等等.

其他的生成子代數(shù)也同樣具有閉包特性的，如生成子半群、生成子環(huán)、生成理想、生成子域等等.比如我們講到域的定義之后，會(huì)與學(xué)生說有理數(shù)域Q、實(shí)數(shù)域R、復(fù)數(shù)域C都是符合這個(gè)定義的，并給出數(shù)域的定義.復(fù)數(shù)域C的子域稱為數(shù)域，讓同學(xué)們?cè)囋囌页銎渌麛?shù)域的例子，給學(xué)生一定的提示引導(dǎo)學(xué)生驗(yàn)證如都是數(shù)域.最后證明有理數(shù)域Q是最小的數(shù)域，這時(shí)要同學(xué)體會(huì)從集合｛0，1｝出發(fā)逐步生成數(shù)域的過程，｛0，1｝→N→Z→Q.

3 抽象數(shù)學(xué)中的閉包概念及閉包算子

在數(shù)學(xué)中，一個(gè)集合被稱為在某個(gè)運(yùn)算下閉合，如果在這個(gè)集合的成員上的運(yùn)算生成這個(gè)集合的成員.例如，實(shí)數(shù)在減法下閉合，但自然數(shù)不行，自然數(shù)3和7的減法3－7的結(jié)果不是自然數(shù).類似的，一個(gè)集合被稱為在某些運(yùn)算的下是閉合，如果它單獨(dú)的閉合在每個(gè)運(yùn)算之下.

當(dāng)一個(gè)集合S不閉合在某個(gè)（些）運(yùn)算下的時(shí)候，我們通?？梢哉业桨琒的最小的閉合集合.這個(gè)最小閉合集合被稱為S的關(guān)于這個(gè)（些）運(yùn)算的閉包.例如，在自然數(shù)集的減法下的閉包，被看作實(shí)數(shù)的子集，是整數(shù)集.

關(guān)于某個(gè)運(yùn)算的集合的閉包定義了在X的子集上的閉包算子.閉合集合可以確定自閉包算子；一個(gè)集合是閉合的，如果它等于自己的閉包.所有閉包算子的典型結(jié)構(gòu)性特征是：

（1）閉包是遞增的或擴(kuò)大的：一個(gè)對(duì)象的閉包包含這個(gè)對(duì)象.

（2）閉包是冪等的：閉包的閉包等于閉包.

（3）閉包是單調(diào)的：就是說，如果X包含在Y中，則C（X）也包含在C（Y）.這三個(gè)性質(zhì)可以看做抽象閉包算子的定義.

4 無向圖傳遞閉包的應(yīng)用

無向圖的傳遞閉包主要用于判斷圖的連通性和圖中滿足條件的連通分支，具有很高的實(shí)用價(jià)值［3，8］.借鑒無向圖的傳遞閉包的思想，可以計(jì)算圖中每一對(duì)頂點(diǎn)之間的最短路徑（實(shí)際上就是Fl oyd算法的思想）.

4.1 計(jì)算一對(duì)頂點(diǎn)間的最短路徑（floyd算法）

現(xiàn)有一張城市地圖，圖中的頂點(diǎn)為城市，有向邊代表兩個(gè)城市間的連通關(guān)系，邊上的權(quán)即為距離.現(xiàn)在的問題是，為每一對(duì)可達(dá)的城市間設(shè)計(jì)一條公共汽車線路，要求線路的長度在所有可能的方案里是最短的.

以下e行，每行為邊（i，j）和該邊的距離wij

輸出：k行，每行為一條公共汽車線路.

在枚舉途徑某中間頂點(diǎn)k的任兩個(gè)頂點(diǎn)對(duì)i和j時(shí)，將頂點(diǎn)i和頂點(diǎn)j中間加入頂點(diǎn)k后是否連通的判斷，改為頂點(diǎn)i途徑頂點(diǎn)k至頂點(diǎn)j的路徑是否為頂點(diǎn)i至頂點(diǎn)j的最短路徑（1≤i，j，k≤n）.顯然三重循環(huán)即可計(jì)算出任一對(duì)頂點(diǎn)間的最短路徑.設(shè)n是有向圖的結(jié)點(diǎn)個(gè)數(shù)；path是最短路徑集合.其中path［i，j］為vi至vj的最短路上vj的前趨結(jié)點(diǎn)序號(hào)（1≤i，j≤n）；adj是最短路徑矩陣.初始時(shí)為有向圖的相鄰矩陣，用類似傳遞閉包的計(jì)算方法反復(fù)對(duì)adj矩陣進(jìn)行運(yùn)算，最后使得adj成為存儲(chǔ)每一對(duì)頂點(diǎn)間的最短路徑的矩陣.

4.2 應(yīng)用舉例

問題一：判斷無向圖中任意兩個(gè)頂點(diǎn)之間是否有路.

例2：輸入一張無向圖，指出該圖中哪些頂點(diǎn)對(duì)之間有路.

以下e行，每行為有邊連接的一對(duì)頂點(diǎn).

輸出：k行，每行兩個(gè)數(shù)，為存在路的頂點(diǎn)對(duì)序號(hào)i，j，要求i＜j.

一般采用寬度優(yōu)先或深度優(yōu)先遍歷來解決.因?yàn)閺娜我庖粋€(gè)頂點(diǎn)出發(fā)，進(jìn)行一次遍歷，就可以求出此頂點(diǎn)和其它各個(gè)頂點(diǎn)的連通狀況.所以只要把每個(gè)頂點(diǎn)作為出發(fā)點(diǎn)都進(jìn)行一次遍歷，就能知道任意兩個(gè)頂點(diǎn)之間是否有路存在.一次遍歷的時(shí)間復(fù)雜度為O（n），要窮舉每個(gè)頂點(diǎn)，所以總的時(shí)間復(fù)雜度為O（n＊n）.

問題二：尋找滿足條件的連通分支 .

例3：輸入一張頂點(diǎn)帶權(quán)的無向圖，分別計(jì)算含頂點(diǎn)數(shù)最多的一個(gè)連通分支和頂點(diǎn)的權(quán)之和最大的一個(gè)連通分支.

以下n行，依次表示頂點(diǎn)1到頂點(diǎn)n上的權(quán)；

以下e行，每行為有邊連接的一對(duì)頂點(diǎn).

輸出：兩行，一行為含頂點(diǎn)數(shù)最多的一個(gè)連通分支，一行為頂點(diǎn)的權(quán)之和最大的一個(gè)連通分支，輸出時(shí)按頂點(diǎn)編號(hào)從小到大輸出.

例4：一筆畫問題

問題描述：編程對(duì)給定的一個(gè)圖，判斷能否一筆畫出，若能請(qǐng)輸出一筆畫的先后順序，否則輸出“No Solution！”.

輸入：輸入文件共n＋1行，第1行為圖的頂點(diǎn)數(shù)n，接下來的n行（每行n個(gè)數(shù)據(jù)）為圖的鄰接矩陣，G［i，j］＝1表示頂點(diǎn)i和頂點(diǎn)j有邊相連，G［i，j］＝0表示頂點(diǎn)i和頂點(diǎn)j無邊相連.

輸出：若能一筆畫出，則輸出一筆畫出的頂點(diǎn)先后順序，否則輸出“No Sol ution！”.

樣例輸入：

樣例輸出：

5 結(jié)束語

作者從閉包的特性出發(fā)，整理了一組離散數(shù)學(xué)中具有閉包特性的概念，引導(dǎo)學(xué)生有效的進(jìn)行歸類學(xué)習(xí)，理解所學(xué)知識(shí)的思路、方法和技巧，并通過應(yīng)用實(shí)例提高同學(xué)們應(yīng)用知識(shí)的能力.在教學(xué)中要重視概念教學(xué)，從概念的產(chǎn)生、發(fā)展、內(nèi)涵和與其它相關(guān)知識(shí)的聯(lián)系，整個(gè)來龍去脈，用學(xué)生淺顯易懂的方式講授，循序漸進(jìn)地讓學(xué)生接受這些難以理解的概念及思想方法.

［1］ 左孝凌，李為監(jiān)，劉永才.離散數(shù)學(xué)［M］.上海：上海科技文獻(xiàn)出版社，2001.

［2］ 耿素云，屈婉玲，張立昂.離散數(shù)學(xué)［M］.北京：高等教育出版社，2008.

［3］ 傅彥.離散數(shù)學(xué)基礎(chǔ)及應(yīng)用［M］.成都：電子科技大學(xué)出版社.2000.

［4］ 孫吉貴，楊風(fēng)杰，歐陽丹彤，等.離散數(shù)學(xué)［M］.北京：高等教育出版社.2002.

［5］ KENNET H A R，CHARLES R B.Discrete Mathematics（Fifth Edition）［M］.北京：清華大學(xué)出版社，2003.

［6］ 吳明芬，汪立民.代數(shù)系統(tǒng)中的數(shù)學(xué)思想及同構(gòu)（同態(tài)）的初等詮釋［J］.計(jì)算機(jī)科學(xué)，2010，37（7），15－19.

［7］ 許蔓苓.離散數(shù)學(xué)的方法與挑戰(zhàn)［J］.計(jì)算機(jī)研究與發(fā)展.2002，39（12）：1771－1772.

［8］ 李梅霞.離散數(shù)學(xué)中關(guān)系性質(zhì)的判定方法［J］.大學(xué)數(shù)學(xué)，2010，26（5）203－206.

［9］ 李小梅.“離散數(shù)學(xué)”中代數(shù)理論教學(xué)的處置［J］.贛南師范學(xué)院學(xué)報(bào).2000（3）：75－76.

［10］崔艷榮，陳勇，黃艷娟.離散數(shù)學(xué)教學(xué)方法與手段探［J］.長江大學(xué)學(xué)報(bào)，2009，6（2）：373－374.

［11］薛占熬，肖運(yùn)花，杜浩翠，等.論 “雙主"在離散數(shù)學(xué)教學(xué)過程中的作用［J］.計(jì)算機(jī)教育，2011，18：37－40.

［12］劉衛(wèi)鋒，劉 林，王東曉，等.數(shù)學(xué)文化融入離散數(shù)學(xué)的教學(xué)研究［J］.計(jì)算機(jī)教育，2011（6）：52－55.

［13］吳明芬，張先勇.應(yīng)用驅(qū)動(dòng)激發(fā)離散數(shù)學(xué)課程的學(xué)習(xí)興趣和動(dòng)力［C］.大學(xué)計(jì)算機(jī)課程報(bào)告論壇論文集.北京：高等教育出版社，2009：281－285.

［14］朱家義，苗國義，梁云娟.基于知識(shí)關(guān)系的離散數(shù)學(xué)教學(xué)內(nèi)容設(shè)計(jì)［J］.計(jì)算機(jī)教育，2010（18）：98－100.