在Word上轻松实现Warshajj算法

吕洪升

（巢湖学院，安徽 巢湖 238000）

1 引言

在离散数学教学中，含n个元素集合S上的二元关系R的传递闭包t（R）的计算是一个比较麻烦的过程，课堂上如何清晰、简单地讲述显得至关重要，所谓简单，就是不用程序语言编程，也不明显使用专门软件，而在教学常用的电子教案PowerPoint或Word平台上得到所需的计算结果，并能如意控制其显示与隐藏。

1.1 Warshajj算法

设M为关系R的关系矩阵或关系图的邻接矩阵，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，转步骤 3，否则停止。

这是一个计算二元关系R的传递闭包t（R）的有效算法[2]，该算法包含两重循环，无论用哪种程序设计语言去实现，n较大时计算都耗时、费力，如果借助矩阵实验室软件Matlab的矩阵计算功能，可轻易得出关系矩阵M的1——n幂，再相加，转成逻辑矩阵即是传递闭包t（R）的关系矩阵——关系图的可达矩阵，t（R）随之可得。

1.2 理论依据

依据二元关系理论及其与关系矩阵的对应规律，关系矩阵A的1——n幂的和矩阵，逻辑化后（记为）R2就是关系R的传递闭包t（R）的关系矩阵。因为关系矩阵A的m（m是任意自然数）次幂矩阵 （记为）Am 的每个元素 Am[j，k]（j=1，2，……，n，k=1，2，……，n）是对应关系R中结点j到结点k长为m的路的数量，按传递闭包的定义，只要有一个 m，使 Am[j，k]非 0时，j到 k应该有且仅需一条边连接，而对所有m，都有Am[j，k]=0时，j到k不连接；或者说，结点j可达结点k（只要有某个 m 使 Am[j，k]非 0），传递闭包 t（R）中就应连接；否则（对所有 m，都有 Am[j，k]=0），传递闭包t（R）中就不应连接，这些信息恰好包含在所得的逻辑矩阵R2中，而且R2也只包含传递闭包 t（R）的连接关系[3]。 另外，长于结点数（n）的路一定有长度小于结点n的路（m）替代，所以，只需要计算关系矩阵1——n次幂就可以了。

1.3 Matlab 为后台工具

更进一步，如果引入工程软件Matlab作为后台工具，在Word界面（或 PowerPoint）可无缝隙链接或调用Matlab的强大矩阵计算功能[4]，而不用考虑学生是否具备Matlab程序设计语言的基础，也不用刻意补充讲授该语言的各种规定和程序设计的语法体系，更不用其它程序设计语言的基础，由Word本身即能完成许多复杂计算。这对数学教师求之不得，计算完全在后台进行，计算结果需要时可以前台显示，既避免了用Microsoft Word（或PowerPoint）设计数学教案时，所插入的数学公式不能与其它文字统一编辑的无奈，也不需专门调用数学软件实现计算，可谓一举两得。

2 配置Word运行环境

我们仅对常用的微软文字处理软件Word进行配置，使其在正常进行文字处理的同时还具有数据计算、绘图等其它功能，更进一步还能直接调用集Fortran、Pascal、C语言等于一体的第四代程序设计语言[5]，处理许多智能操作，并能自如控制计算结果的显示和隐藏，而人机交互的界面就是普通的Microsoft Word。

2.1 Matlab 的安装和运行

早期的Matlab，由于容量大，安装费时费力，很不容易，现在有绿色便携版或云软件系统（百度一下就有许多资源），只要下载到U盘中，在任一部装有Windows XP或Windows 7操作系统的PC机上就能即插即用，不用安装，非常方便，当然在Unix平台上使用也简单[6]，不需赘述。

2.2 notebook 安装

本机使用的操作系统是Windows 7，且假定已安装了Microsoft Word2007（Windows和 Word其它版本操作类似）。首先运行Matlab软件，在其命令窗口输入notebook-setup回车 （这里要注意notebook与后面“-setup”的减号之间要空一格，否则系统报错，安装失败），在欢迎界面中键入Microsoft Word2007前面的数字5（图略），就完成了安装。

2.3 notebook 启动

无论在Matlab还是在Word2007环境下，都有多种启动方法。

2.3.1 在 Matlab 窗口启动

在Matlab命令窗口，键入notebook，回车，新M-book模板（notebook的核心模块）文档即可供编辑。操作的窗口就是我们常见的Word2007界面，直观区别就是在菜单栏多了一个notebook选项（如果您的Word2007使用过VBA或其它宏指令，notebook选项将会是“加载项”菜单的二级菜单，如图1，使用完全一样）。

图1

M-book模板定义了Word与Matlab进行通讯的宏指令、文档格式和工具栏，初次使用，要进行初始化设置，就是将宏安全性设置为“中”（不同版本操作系统的windows设置稍有不同），允许Matlab使用notebook中的宏。

2.3.2 在 Word 窗口启动

若先打开Word（Matlab必须先打开），击“新建/我的模板/M-book.dot”文档（见图2），击“确定”按键即进入空文档编辑状态，后面的操作就是普通Word。

图2

2.3.3 编辑或打开已有文档

这与Word通常操作完全一样，不用重复。

3 Word界面上实现Warshajj算法

我们结合实例详细介绍Warshajj算法实现的方法步骤，在操作过程中，为避免篇幅太长，将隐藏中间计算结果，隐藏或显示方法只是菜单选择的区别，文中将具体说明。

3.1 计算关系R的传递闭包t（R）

例题 1 设 S＝{a，b，c，d}，S 上的关系 R={（a，b），（b，a），（b，c），（c，d）}（图3），计算 R 的传递闭包 t（R）。

3.1.1 解题一般步骤

第一步 输入关系矩阵A并读入内存（注意本例集合S的元素个数n为4）。

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

b选中（点亮）A

c设为输入细胞[7]。 击 Define Input cell（图4），计算但不显示结果（结果保存在Matlab工作内存中，供后继调用。如果同时打开多个M-book文档且变量相互调用时，要注意不同窗口、文件变量交换时的影响）；击Evaluate cell，计算并显示结果。

第二步 计算A的2-n次幂（其中n为集合S的元素个数或对应关系图的结点数，方法与第一步完全一样）。

a输入公式A2=A*A

b选中（点亮）

c设为输入细胞[A2=A*A]（同第一步，计算但不显示结果，击Define Input cell菜单）。

完全一样依次计算出A3=A2*A，A4=A3*A。

A3=A2*A;A4=A3*A

A的更高次幂完全一样依次算出。

第三步 将第二步中计算的结果A、A2、A3、A4、……An（A的各次幂）相加并记为R1。

R1=A+A2+A3+A4

第四步 逻辑化R1,并显示所得逻辑矩阵，记为R2。

R2=logical（R1） （logical为逻辑转换命令，显示这一步的结果，只要在图4中击Evaluate cell菜单）

逻辑矩阵R2就是我们所求的关系R的传递闭包t（R）所对应的关系矩阵。

从R2很轻易地得到我们所求的R的传递闭包 t （R）＝{（a，b），（b，a），（b，c），（c，d），（a，c），（a，d），（b，d）}，

图4

对应的关系图也容易得到（图5）。

解答完毕。

3.2 例题 2

求无向简单图 （图6）的可达矩阵或传递闭包。

显 然 S＝{1，2，3，4，5，6，7}，S 上 的 关 系 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）}，现在计算R 的传递闭包 t（R）。

解 我们只给出计算R的传递闭包t（R）关系矩阵的详细步骤。

第一步 输入R的关系矩阵 （图的邻接矩阵）A并读入内存（设为不显示结果的输入细胞，供后继计算调用）。

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选中（点亮）

c设为输入细胞 击图4中Define Input cell菜单（计算但不显示结果并保存在Matlab工作内存中，供后继调用）。

第二步 计算A的2-7次幂。

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

b选中（点亮）

c设为输入细胞（不显示结果，图4中击Define Input cell菜单）。

第三步 将计算结果 A、A2、A3、A4、A5、A6、A7（A的各次幂）相加并记为R1（不显示结果,击Define Input cell菜单）。

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

第四步 逻辑化R1,所得逻辑矩阵记为R2。R2=logical（R1）（显示这一步的结果：点亮并在图4中击Evaluate cell菜单）

这就是关系R的传递闭包t（R）对应的关系矩阵或可达矩阵。

4 小结

教学要依据已有的条件、学生的基础，想办法化繁为简、化难为易，循序渐进地将新知识传授给学生，我们实现Warshajj算法似乎只做了加减法，同时学生根本看不见Matlab的后台调用，不增加学生负担，容易被接受，还能启迪有兴趣的学生深入钻研，逐步学会Matlab的其它许多功能。

[1]左孝凌，李为鑑，刘永才.离散数学[M].上海：上海科学技术文献出版社，1982，124.

[2]耿素云.集合论与图论（离散数学第二分册）[M].北京：北京大学出版社，1998，61.

[3]殷剑宏，吴开亚.图论及其算法[M].合肥：中国科学技术大学出版社，2004，36.

[4]董霖.MATLAB 使用详解[M].北京：电子工业出版社，2009，483.

[5]刘维.精通Matlab与C/C++混合程序设计[M].北京：北京航空航天大学出版社，2012.

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

[7]吕洪升.在 Word 界面上矩阵操作[J].巢湖学院学报，2013，（3）.