关系矩阵在《离散数学》中的应用研究

陈琼 杨洁 郭妍

摘 要： 高校课程《离散数学》是应用数学的一个重要分支，也是计算机专业的核心课程之一，还与《数据结构》、《操作系统》、《软件工程》、《数据库系统》、《人工智能》等课程联系紧密.本文对矩阵在离散数学集合论中的应用展开讨论，期望为初学者和数学工作者在学习离散数学时提供参考.

关键词： 离散数学 关系矩阵 关系的闭包

《离散数学》课程主要包括矩阵代数、集合论、数理逻辑、代数系统、图论五部分.通过离散数学的学习，可以提高抽象思维和严格的逻辑推理能力，养成良好的逻辑性、创新性、系统性、发散性等思维习惯.矩阵是线性代数中的一个基本概念，可以使很多抽象的数学概念得到具体的表示，并且把运算转换成简单的矩阵运算.矩阵成为解决许多数学问题的有力工具，在离散数学中的应用也很广泛.下面就矩阵应用的实例进行讨论.

1.矩阵的定义

由m×n个数a■（i=1，2，…，m；j=1，2，…，n），在括号（ ）内排列成m行n列（横的称行，纵的称列）的一个长方形数表a■ a■ … a■a■ a■ … a■… … … …a■ a■ … a■，称为矩阵A■=（a■）■.通常用大写字母A、B…表示，其中a■称为矩阵第i行第j列的元素.

2.关系矩阵

定义：设X，Y是任意两个集合，则称笛卡尔积X×Y的任一子集为从X到Y的二元关系，简称关系，记为R，R？哿X×Y.设A={x■，x■，…，x■}，R是A上的关系，

若〈x■，x■〉∈R，则r■=1；若〈x■，x■〉？埸R，则r■=0，则

（r■）=r■ r■ … r■r■ r■ … r■… … … …r■ r■ … r■是R的关系矩阵，记作M■.

例如：A={1，2，3，4}，R={〈1，1〉，〈1，3〉，〈2，3〉，〈3，2〉，〈4，2〉}，则R的关系矩阵是M■=1 0 1 00 0 1 00 1 0 00 1 0 0.

3.关系的五种性质

不仅反映在集合表达式上，而且明显地反映在关系矩阵上，特点如下表：

4.关系的闭包

定理：设R为A上的关系，则有（1）自反闭包r（R）=R∪R■；（2）对称闭包s（R）=R∪R■；（3）传递闭包t（R）=R∪R■∪R■∪…

例1：已知关系矩阵M■=1 1 00 0 01 1 0，求它的自反闭包r（R）、对称闭包s（R）和传递闭包的关系矩阵.

解：M■=M■∪M■=1 1 00 1 01 1 1 M■=M■∪M■=1 1 11 0 11 1 0

M■=1 1 00 0 01 1 0■=1 1 00 0 01 1 0=M■，则得出R=R■=R■=R■（n=1，2，3…）

而t（R）=R∪R■∪R■∪…=R，有M■=M■=1 1 00 0 01 1 0.

关系的表示方法关系图主要表达结点与结点间的邻接关系，就是使用上面方法直接从R的关系矩阵得到.

例2：R的关系图为 ，

试给出它的自反闭包r（R）、对称闭包s（R）和传递闭包t（R）的关系图.

解：自反闭包r（R）的关系图为，

对称闭包s（R）的关系图为，

下面求传递闭包的关系矩阵：

M■=0 1 0 0 00 0 1 0 10 0 0 1 00 0 1 0 00 0 0 0 1 M■=0 0 1 0 10 0 0 1 10 0 1 0 00 0 0 1 00 0 0 0 1

M■=M■.M■=0 0 0 1 10 0 1 0 10 0 0 1 00 0 1 0 00 0 0 0 1 M■=M■.M■=0 0 1 0 10 0 0 1 10 0 1 0 00 0 0 1 00 0 0 0 1=M■

M■∪M■∪M■=0 1 1 1 10 0 1 1 10 0 1 1 00 0 1 1 00 0 0 0 1

则t（R）={〈a，b〉，〈a，c〉，〈a，d〉，〈a，e〉，〈b，c〉，〈b，d〉，〈b，e〉，〈c，c〉，〈c，d〉，〈d，c〉，〈d，d〉，〈e，e〉}

得到传递闭包的关系图为.

参考文献：

[1]陈华峰，杨勇.离散数学基础[M].北京：中国水利水电出版社，2012.

[2]耿素云，屈婉玲.离散数学（修订版）[M].北京：高等教育出版社，2004.

[3]李文钰，杜忠复，张丽春.浅谈关系矩阵在离散数学教学中的应用研究[J].数学学习与研究，2015.3.