關系矩陣在《離散數學》中的應用研究

陳瓊 楊潔 郭妍

摘 要： 高校課程《離散數學》是應用數學的一個重要分支，也是計算機專業的核心課程之一，還與《數據結構》、《操作系統》、《軟件工程》、《數據庫系統》、《人工智能》等課程聯系緊密.本文對矩陣在離散數學集合論中的應用展開討論，期望為初學者和數學工作者在學習離散數學時提供參考.

關鍵詞： 離散數學 關系矩陣 關系的閉包

《離散數學》課程主要包括矩陣代數、集合論、數理邏輯、代數系統、圖論五部分.通過離散數學的學習，可以提高抽象思維和嚴格的邏輯推理能力，養成良好的邏輯性、創新性、系統性、發散性等思維習慣.矩陣是線性代數中的一個基本概念，可以使很多抽象的數學概念得到具體的表示，并且把運算轉換成簡單的矩陣運算.矩陣成為解決許多數學問題的有力工具，在離散數學中的應用也很廣泛.下面就矩陣應用的實例進行討論.

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.