利用矩阵表现关系

1、第八章第八章 關係關係(Relations)8.1 Relations and Properties 8.2 n-ary Relations and Their Applications8.3 Representing Relations8.4 Closures of Relations8.5 Equivalence Relations8.6 Partial Orderings利用矩陣表現關係利用矩陣表現關係( 8.3) p有限集合間的關係能以零壹矩陣來表現。假設R是由集合A = a1, a2, , am到集合B = b1, b2, , bn（此處集合的元素可以任意方式排序，但若A = B時，

2、我們使用相同的排列順序）。關係R能以矩陣MR = mij表示，其中換句話說，表現關係R的零壹矩陣中，第(i, j)個位置的元素為1，若ai與bj有關係；而第(i, j)個位置的元素為0，若ai與bj沒有關係。（這種表示法與集合A與B使用之順序相關。） RbaRbamjijiij),(0),(1若若p例：例：假設A = 1, 2, 3而B = 1, 2。令R為由A到B的關係，包含所有的有序對(a, b)，如果aA，bB，而且a b。何為R之矩陣表示法，其中a1= 1, a2 = 2, a3 = 3，而且b1 = 1, b2 = 2？p解：解：p例：例：令A = a1, a2, a3而B = b1

3、, b2, b3, b4, b5。若R的表現矩陣如下，則哪些有序對再關係R中？p解：解：關係之性質與表現矩陣反身性關係之性質與表現矩陣反身性p當關係R是反身的若(a, a)R，當aA。R是反身的若且唯若(ai, ai)R，i = 1, 2, ., n。R是反身的若且唯若mii = 1，i = 1, 2, , n。換句話說，R是反身的，如果矩陣MR的主對角線之元素都為1。p譬如：若A = 1, 2，R = (1, 1), (1, 2), (2, 2)。則 MR = 關係之性質與表現矩陣對稱性關係之性質與表現矩陣對稱性p在A = a1, a2, , an上的關係R是對稱的，若且唯若當(ai, aj

4、)R，能推導出(aj, ai)R。以矩陣來看，R是對稱的若且唯若對所有的整數對(i, j)，mij = mji。即，(MR) = (MR)t。p譬如：若A = 1, 2，R = (1, 1), (1, 2), (2, 1)。則 MR = 關係之性質與表現矩陣反對稱性關係之性質與表現矩陣反對稱性p關係R是反對稱的，其表現矩陣有下列性質：當i j時，若mij = 1，則mji = 0。換言之，當i j，要不是mij = 0就是mji = 0。至於當i = j時則沒有限制。 p譬如：若A = 1, 2，R = (1, 2), (2, 2)。則 MR = p例：例：假設表現關係R的矩陣為判斷R是否為反

5、身的？對稱的？反對稱的？p解：解：110111011RM布爾運算中的聯合(join)和交遇(meet) 能夠用來找出表現兩個關係之聯集與交集的矩陣。 p例：例：假設R1和R2為集合A上的關係，其表現矩陣分別為 何為表現R1R2和R1R2的矩陣？p假設R為由A到B的關係，S是由B到C的關係。而集合A，B與C分別有m，n和p個元素。令表現關係S R ，R和S的矩陣分別為 MS R = tij，MR = rij和MS = sij（矩陣之大小分別為mp，mn和np）。p有序對(ai, cj)屬於S R若且唯若存在元素bkB使得(ai, bk)屬於R，(bk, cj)屬於S。因此，tij = 1若且唯若

6、存在k使得rik = skj = 1。根據布爾積的定義， MS R = MR MS 。 p例：例：找出表現關係S R的矩陣，其中表現R與S的矩陣分別為 p解：解： S R的表現矩陣為 p例：例：找出表現關係R2的矩陣，其中表現R的矩陣為p解：解：表現關係R2的矩陣為 利用有向圖表現關係利用有向圖表現關係 p還有一種重要的方法，以圖形方式來表現關係。每個在集合中的元素以頂點來表示，有序對使用一個有方向之邊來表現。當我們考慮有限集合上的關係時，這種圖形表現法是種有向圖有向圖(directed graph or digraph)。p定義：定義：一個有向圖包含一個頂點(vertex)（或是節點(nod

7、e)）集合V，以及一個V中元素之有序對多成集合E，其元素稱為邊(edge)（或是弧(arc)）。頂點a稱為邊(a, b)的初始點(initial vertex)，而頂點b成為此邊的終點(terminal vertex)。由(a, a)所形成的邊用一個由頂點a到本身的弧來表現，這樣的邊稱為迴圈迴圈(loop)。 p例：例：以a, b, c和d為頂點，(a, b), (a, d), (b, b), (b, d), (c, a), (c, b)和(d, b)為邊所成之有向圖如下圖所示。 p例：例：表現在集合1, 2, 3, 4上的關係R = (1, 1), (1, 3), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (4, 1)，之有向圖如：p例：例：若表現關