關係矩陣在《離散數學》中的應用研究
數學教學與研究
作者：陳瓊 楊潔 郭妍
摘 要： 高校課程《離散數學》是應用數學的一個重要分支，也是計算機專業的核心課程之一，還與《數據結構》、《操作係統》、《軟件工程》、《數據庫係統》、《人工智能》等課程聯係緊密.本文對矩陣在離散數學集合論中的應用展開討論，期望為初學者和數學工作者在學習離散數學時提供參考.
關鍵詞： 離散數學 關係矩陣 關係的閉包
《離散數學》課程主要包括矩陣代數、集合論、數理邏輯、代數係統、圖論五部分.通過離散數學的學習，可以提高抽象思維和嚴格的邏輯推理能力，養成良好的邏輯性、創新性、係統性、發散性等思維習慣.矩陣是線性代數中的一個基本概念，可以使很多抽象的數學概念得到具體的表示，並且把運算轉換成簡單的矩陣運算.矩陣成為解決許多數學問題的有力工具，在離散數學中的應用也很廣泛.下麵就矩陣應用的實例進行討論.
1.矩陣的定義
由m×n個數a（i=1，2，…，m；j=1，2，…，n），在括號（ ）內排列成m行n列（橫的稱行，縱的稱列）的一個長方形數表a a … aa 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 … rr 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.