呂洪升

（巢湖學(xué)院，安徽 巢湖 238000）

1 引言

在離散數(shù)學(xué)教學(xué)中，含n個元素集合S上的二元關(guān)系R的傳遞閉包t（R）的計(jì)算是一個比較麻煩的過程，課堂上如何清晰、簡單地講述顯得至關(guān)重要，所謂簡單，就是不用程序語言編程，也不明顯使用專門軟件，而在教學(xué)常用的電子教案PowerPoint或Word平臺上得到所需的計(jì)算結(jié)果，并能如意控制其顯示與隱藏。

1.1 Warshajj算法

設(shè)M為關(guān)系R的關(guān)系矩陣或關(guān)系圖的鄰接矩陣，Warshajj算法[1]：

（1）A：=M；

（2）i：=1；

（3）對所有j，如果 A[j，i]=1，則對 k=1，2，……，n，A[j，k]：=A[j，k]+A[i，k]；

（4）i=：i+1；

（5）i<=n，轉(zhuǎn)步驟 3，否則停止。

這是一個計(jì)算二元關(guān)系R的傳遞閉包t（R）的有效算法[2]，該算法包含兩重循環(huán)，無論用哪種程序設(shè)計(jì)語言去實(shí)現(xiàn)，n較大時計(jì)算都耗時、費(fèi)力，如果借助矩陣實(shí)驗(yàn)室軟件Matlab的矩陣計(jì)算功能，可輕易得出關(guān)系矩陣M的1——n冪，再相加，轉(zhuǎn)成邏輯矩陣即是傳遞閉包t（R）的關(guān)系矩陣——關(guān)系圖的可達(dá)矩陣，t（R）隨之可得。

1.2 理論依據(jù)

依據(jù)二元關(guān)系理論及其與關(guān)系矩陣的對應(yīng)規(guī)律，關(guān)系矩陣A的1——n冪的和矩陣，邏輯化后（記為）R2就是關(guān)系R的傳遞閉包t（R）的關(guān)系矩陣。因?yàn)殛P(guān)系矩陣A的m（m是任意自然數(shù)）次冪矩陣 （記為）Am 的每個元素 Am[j，k]（j=1，2，……，n，k=1，2，……，n）是對應(yīng)關(guān)系R中結(jié)點(diǎn)j到結(jié)點(diǎn)k長為m的路的數(shù)量，按傳遞閉包的定義，只要有一個 m，使 Am[j，k]非 0時，j到 k應(yīng)該有且僅需一條邊連接，而對所有m，都有Am[j，k]=0時，j到k不連接；或者說，結(jié)點(diǎn)j可達(dá)結(jié)點(diǎn)k（只要有某個 m 使 Am[j，k]非 0），傳遞閉包 t（R）中就應(yīng)連接；否則（對所有 m，都有 Am[j，k]=0），傳遞閉包t（R）中就不應(yīng)連接，這些信息恰好包含在所得的邏輯矩陣R2中，而且R2也只包含傳遞閉包 t（R）的連接關(guān)系[3]。 另外，長于結(jié)點(diǎn)數(shù)（n）的路一定有長度小于結(jié)點(diǎn)n的路（m）替代，所以，只需要計(jì)算關(guān)系矩陣1——n次冪就可以了。

1.3 Matlab 為后臺工具

更進(jìn)一步，如果引入工程軟件Matlab作為后臺工具，在Word界面（或 PowerPoint）可無縫隙鏈接或調(diào)用Matlab的強(qiáng)大矩陣計(jì)算功能[4]，而不用考慮學(xué)生是否具備Matlab程序設(shè)計(jì)語言的基礎(chǔ)，也不用刻意補(bǔ)充講授該語言的各種規(guī)定和程序設(shè)計(jì)的語法體系，更不用其它程序設(shè)計(jì)語言的基礎(chǔ)，由Word本身即能完成許多復(fù)雜計(jì)算。這對數(shù)學(xué)教師求之不得，計(jì)算完全在后臺進(jìn)行，計(jì)算結(jié)果需要時可以前臺顯示，既避免了用Microsoft Word（或PowerPoint）設(shè)計(jì)數(shù)學(xué)教案時，所插入的數(shù)學(xué)公式不能與其它文字統(tǒng)一編輯的無奈，也不需專門調(diào)用數(shù)學(xué)軟件實(shí)現(xiàn)計(jì)算，可謂一舉兩得。

2 配置Word運(yùn)行環(huán)境

我們僅對常用的微軟文字處理軟件Word進(jìn)行配置，使其在正常進(jìn)行文字處理的同時還具有數(shù)據(jù)計(jì)算、繪圖等其它功能，更進(jìn)一步還能直接調(diào)用集Fortran、Pascal、C語言等于一體的第四代程序設(shè)計(jì)語言[5]，處理許多智能操作，并能自如控制計(jì)算結(jié)果的顯示和隱藏，而人機(jī)交互的界面就是普通的Microsoft Word。

2.1 Matlab 的安裝和運(yùn)行

早期的Matlab，由于容量大，安裝費(fèi)時費(fèi)力，很不容易，現(xiàn)在有綠色便攜版或云軟件系統(tǒng)（百度一下就有許多資源），只要下載到U盤中，在任一部裝有Windows XP或Windows 7操作系統(tǒng)的PC機(jī)上就能即插即用，不用安裝，非常方便，當(dāng)然在Unix平臺上使用也簡單[6]，不需贅述。

2.2 notebook 安裝

本機(jī)使用的操作系統(tǒng)是Windows 7，且假定已安裝了Microsoft Word2007（Windows和 Word其它版本操作類似）。首先運(yùn)行Matlab軟件，在其命令窗口輸入notebook-setup回車 （這里要注意notebook與后面“-setup”的減號之間要空一格，否則系統(tǒng)報錯，安裝失?。?，在歡迎界面中鍵入Microsoft Word2007前面的數(shù)字5（圖略），就完成了安裝。

2.3 notebook 啟動

無論在Matlab還是在Word2007環(huán)境下，都有多種啟動方法。

2.3.1 在 Matlab 窗口啟動

在Matlab命令窗口，鍵入notebook，回車，新M-book模板（notebook的核心模塊）文檔即可供編輯。操作的窗口就是我們常見的Word2007界面，直觀區(qū)別就是在菜單欄多了一個notebook選項(xiàng)（如果您的Word2007使用過VBA或其它宏指令，notebook選項(xiàng)將會是“加載項(xiàng)”菜單的二級菜單，如圖1，使用完全一樣）。

圖1

M-book模板定義了Word與Matlab進(jìn)行通訊的宏指令、文檔格式和工具欄，初次使用，要進(jìn)行初始化設(shè)置，就是將宏安全性設(shè)置為“中”（不同版本操作系統(tǒng)的windows設(shè)置稍有不同），允許Matlab使用notebook中的宏。

2.3.2 在 Word 窗口啟動

若先打開Word（Matlab必須先打開），擊“新建/我的模板/M-book.dot”文檔（見圖2），擊“確定”按鍵即進(jìn)入空文檔編輯狀態(tài)，后面的操作就是普通Word。

圖2

2.3.3 編輯或打開已有文檔

這與Word通常操作完全一樣，不用重復(fù)。

3 Word界面上實(shí)現(xiàn)Warshajj算法

我們結(jié)合實(shí)例詳細(xì)介紹Warshajj算法實(shí)現(xiàn)的方法步驟，在操作過程中，為避免篇幅太長，將隱藏中間計(jì)算結(jié)果，隱藏或顯示方法只是菜單選擇的區(qū)別，文中將具體說明。

3.1 計(jì)算關(guān)系R的傳遞閉包t（R）

例題 1 設(shè) S＝{a，b，c，d}，S 上的關(guān)系 R={（a，b），（b，a），（b，c），（c，d）}（圖3），計(jì)算 R 的傳遞閉包 t（R）。

3.1.1 解題一般步驟

第一步 輸入關(guān)系矩陣A并讀入內(nèi)存（注意本例集合S的元素個數(shù)n為4）。

a 輸入 A=[0，1，0，0；1，0，1，0；0，0，0，1；0，0，0，0]

b選中（點(diǎn)亮）A

c設(shè)為輸入細(xì)胞[7]。 擊 Define Input cell（圖4），計(jì)算但不顯示結(jié)果（結(jié)果保存在Matlab工作內(nèi)存中，供后繼調(diào)用。如果同時打開多個M-book文檔且變量相互調(diào)用時，要注意不同窗口、文件變量交換時的影響）；擊Evaluate cell，計(jì)算并顯示結(jié)果。

第二步 計(jì)算A的2-n次冪（其中n為集合S的元素個數(shù)或?qū)?yīng)關(guān)系圖的結(jié)點(diǎn)數(shù)，方法與第一步完全一樣）。

a輸入公式A2=A*A

b選中（點(diǎn)亮）

c設(shè)為輸入細(xì)胞[A2=A*A]（同第一步，計(jì)算但不顯示結(jié)果，擊Define Input cell菜單）。

完全一樣依次計(jì)算出A3=A2*A，A4=A3*A。

A3=A2*A;A4=A3*A

A的更高次冪完全一樣依次算出。

第三步 將第二步中計(jì)算的結(jié)果A、A2、A3、A4、……An（A的各次冪）相加并記為R1。

R1=A+A2+A3+A4

第四步 邏輯化R1,并顯示所得邏輯矩陣，記為R2。

R2=logical（R1） （logical為邏輯轉(zhuǎn)換命令，顯示這一步的結(jié)果，只要在圖4中擊Evaluate cell菜單）

邏輯矩陣R2就是我們所求的關(guān)系R的傳遞閉包t（R）所對應(yīng)的關(guān)系矩陣。

從R2很輕易地得到我們所求的R的傳遞閉包 t （R）＝{（a，b），（b，a），（b，c），（c，d），（a，c），（a，d），（b，d）}，

圖4

對應(yīng)的關(guān)系圖也容易得到（圖5）。

解答完畢。

3.2 例題 2

求無向簡單圖 （圖6）的可達(dá)矩陣或傳遞閉包。

顯 然 S＝{1，2，3，4，5，6，7}，S 上 的 關(guān) 系 R={（1，2），（1，5），（2，3）， （3，4）， （3，5），（6，7），（2，1），（5，1），（3，2），（4，3），（5，3），（7，6）}，現(xiàn)在計(jì)算R 的傳遞閉包 t（R）。

解 我們只給出計(jì)算R的傳遞閉包t（R）關(guān)系矩陣的詳細(xì)步驟。

第一步 輸入R的關(guān)系矩陣 （圖的鄰接矩陣）A并讀入內(nèi)存（設(shè)為不顯示結(jié)果的輸入細(xì)胞，供后繼計(jì)算調(diào)用）。

a 輸入 A=[0，1，0，0，1，0，0；1，0，1，0，0，0，0；0，1，0，1，1，0，0；0，0，1，0，0，0，0；1，0，1，0，0，0，0；0，0，0，0，0，0，1；0，0，0，0，0，1，0]

b選中（點(diǎn)亮）

c設(shè)為輸入細(xì)胞 擊圖4中Define Input cell菜單（計(jì)算但不顯示結(jié)果并保存在Matlab工作內(nèi)存中，供后繼調(diào)用）。

第二步 計(jì)算A的2-7次冪。

a 輸入公式 A2=A*A，A3=A2*A，A4=A3*A，A5=A4*A，A6=A5*A，A7=A6*A

b選中（點(diǎn)亮）

c設(shè)為輸入細(xì)胞（不顯示結(jié)果，圖4中擊Define Input cell菜單）。

第三步 將計(jì)算結(jié)果 A、A2、A3、A4、A5、A6、A7（A的各次冪）相加并記為R1（不顯示結(jié)果,擊Define Input cell菜單）。

R1=A+A2+A3+A4+A5+A6+A7

第四步 邏輯化R1,所得邏輯矩陣記為R2。R2=logical（R1）（顯示這一步的結(jié)果：點(diǎn)亮并在圖4中擊Evaluate cell菜單）

這就是關(guān)系R的傳遞閉包t（R）對應(yīng)的關(guān)系矩陣或可達(dá)矩陣。

4 小結(jié)

教學(xué)要依據(jù)已有的條件、學(xué)生的基礎(chǔ)，想辦法化繁為簡、化難為易，循序漸進(jìn)地將新知識傳授給學(xué)生，我們實(shí)現(xiàn)Warshajj算法似乎只做了加減法，同時學(xué)生根本看不見Matlab的后臺調(diào)用，不增加學(xué)生負(fù)擔(dān)，容易被接受，還能啟迪有興趣的學(xué)生深入鉆研，逐步學(xué)會Matlab的其它許多功能。

[1]左孝凌，李為鑑，劉永才.離散數(shù)學(xué)[M].上海：上海科學(xué)技術(shù)文獻(xiàn)出版社，1982，124.

[2]耿素云.集合論與圖論（離散數(shù)學(xué)第二分冊）[M].北京：北京大學(xué)出版社，1998，61.

[3]殷劍宏，吳開亞.圖論及其算法[M].合肥：中國科學(xué)技術(shù)大學(xué)出版社，2004，36.

[4]董霖.MATLAB 使用詳解[M].北京：電子工業(yè)出版社，2009，483.

[5]劉維.精通Matlab與C/C++混合程序設(shè)計(jì)[M].北京：北京航空航天大學(xué)出版社，2012.

[6]薜志涌.精通 Matlab[M].北京：北京航空航天大學(xué)出版社，2012：1，40.

[7]呂洪升.在 Word 界面上矩陣操作[J].巢湖學(xué)院學(xué)報，2013，（3）.