吳明芬，瞿赟昀

（五邑大學 計算機學院 廣東江門529020）

0 引言

離散數學以研究離散量的結構和相互關系為主要目標，其研究對象一般是有限或可數個元素組成的集合，所以它很好地描述了計算機科學離散性的特點［1－5］.離散數學作為計算機科學領域最有效的一種數學工具，從70年代初，國外就已經作為一門課程正式列入計算機科學和一些工程學系的教學計劃中.

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

1 離散數學中顯性的閉包概念

1.1 二元關系的閉包

在離散數學中，關系理論是其一個重要的組成部分，它的知識點主要包括關系的性質、關系的復合、逆運算和閉包運算、關系的劃分和覆蓋，以及等價關系、相容關系、序關系幾種特殊的關系.可以通過求關系的傳遞閉包來實現傳遞性的判斷，而傳遞閉包本身在圖論中有很好的應用價值.所以二元關系閉包是一個重要的概念，在計算機科學中有著廣泛的應用.

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

定義1：設R是集合A上二元關系，稱R′為R的自反閉包（對稱閉包，傳遞閉包），如果R′滿足：

（1）R′是自反的（對稱的，傳遞的）；

（3）對A上任意關系R″，若R″滿足上面的條件（1）和（2），則

一個關系R的自反閉包、對稱閉包和傳遞閉包分別記作r（R）、s（R）、t（R），也稱r，s，t為閉包運算（算子），它們作用于關系R后，分別產生包含R的最小的自反關系、對稱關系和傳遞關系.

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

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

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

關系閉包的基本思想：假設關系R不具有性質P，可以在R中添加一些二元序對，使之具有性質P，并希望添加的二元序對盡可能的少.舉例如下：

例1：設R＝ ｛（a，a），（a，c），（c，b）｝是集合A＝ ｛a，b，c｝上的一個二元關系，且不是自反、對稱、傳遞的.將R適當放大，添加最少的序對，使之分別滿足自反、對稱、傳遞性.

和同學一起尋找到以下結果：

之后再介紹二元關系的閉包定義1.

1.2 無向圖的閉包

圖論中關于一個圖的閉包概念［1］描述如下：

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

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

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

2 離散數學中隱式的閉包概念

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

2.1 線性代數中的隱性閉包概念

在線性代數中有關于和空間和生成子空間的概念［6］，并有以下的結論.

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

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

其實結論2中的span（α1，α2，…，αs）就相當于集合 ｛α1，α2，…，αs｝關于子空間這個性質的閉包，因為span（α1，α2，…，αs）就是包含 ｛α1，α2，…，αs｝的最小子空間。例如R2中的兩個向量e1＝（1，0）T，e2＝ （0，1）T，則由它們兩個向量生成的子空間span（e1，e2）＝R2.

2.2 圖論中的隱性閉包概念

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

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

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

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

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

點（邊）割集：設G＝＜V，E＞是一個無向連通圖，對V1?V（E1?E），G－V1（G－E1）是不連通的圖，且對任意的V2?V1（E2?E1），GV2（G－E2）是連通的圖，則稱V1（E1）是圖G的一個點（邊）割集.

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

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

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

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

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

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

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

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

3 抽象數學中的閉包概念及閉包算子

在數學中，一個集合被稱為在某個運算下閉合，如果在這個集合的成員上的運算生成這個集合的成員.例如，實數在減法下閉合，但自然數不行，自然數3和7的減法3－7的結果不是自然數.類似的，一個集合被稱為在某些運算的下是閉合，如果它單獨的閉合在每個運算之下.

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

關于某個運算的集合的閉包定義了在X的子集上的閉包算子.閉合集合可以確定自閉包算子；一個集合是閉合的，如果它等于自己的閉包.所有閉包算子的典型結構性特征是：

（1）閉包是遞增的或擴大的：一個對象的閉包包含這個對象.

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

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

4 無向圖傳遞閉包的應用

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

4.1 計算一對頂點間的最短路徑（floyd算法）

現有一張城市地圖，圖中的頂點為城市，有向邊代表兩個城市間的連通關系，邊上的權即為距離.現在的問題是，為每一對可達的城市間設計一條公共汽車線路，要求線路的長度在所有可能的方案里是最短的.

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

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

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

4.2 應用舉例

問題一：判斷無向圖中任意兩個頂點之間是否有路.

例2：輸入一張無向圖，指出該圖中哪些頂點對之間有路.

以下e行，每行為有邊連接的一對頂點.

輸出：k行，每行兩個數，為存在路的頂點對序號i，j，要求i＜j.

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

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

例3：輸入一張頂點帶權的無向圖，分別計算含頂點數最多的一個連通分支和頂點的權之和最大的一個連通分支.

以下n行，依次表示頂點1到頂點n上的權；

以下e行，每行為有邊連接的一對頂點.

輸出：兩行，一行為含頂點數最多的一個連通分支，一行為頂點的權之和最大的一個連通分支，輸出時按頂點編號從小到大輸出.

例4：一筆畫問題

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

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

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

樣例輸入：

樣例輸出：

5 結束語

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

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

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

［3］ 傅彥.離散數學基礎及應用［M］.成都：電子科技大學出版社.2000.

［4］ 孫吉貴，楊風杰，歐陽丹彤，等.離散數學［M］.北京：高等教育出版社.2002.

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

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

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

［8］ 李梅霞.離散數學中關系性質的判定方法［J］.大學數學，2010，26（5）203－206.

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

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

［11］薛占熬，肖運花，杜浩翠，等.論 “雙主"在離散數學教學過程中的作用［J］.計算機教育，2011，18：37－40.

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

［13］吳明芬，張先勇.應用驅動激發(fā)離散數學課程的學習興趣和動力［C］.大學計算機課程報告論壇論文集.北京：高等教育出版社，2009：281－285.

［14］朱家義，苗國義，梁云娟.基于知識關系的離散數學教學內容設計［J］.計算機教育，2010（18）：98－100.