利用矩陣表現(xiàn)關(guān)系

1、第八章第八章 關(guān)係關(guān)係(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利用矩陣表現(xiàn)關(guān)係利用矩陣表現(xiàn)關(guān)係( 8.3) p有限集合間的關(guān)係能以零壹矩陣來(lái)表現(xiàn)。假設(shè)R是由集合A = a1, a2, , am到集合B = b1, b2, , bn（此處集合的元素可以任意方式排序，但若A = B時(shí)，

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

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

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

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

6、存在k使得rik = skj = 1。根據(jù)布爾積的定義， MS R = MR MS 。 p例：例：找出表現(xiàn)關(guān)係S R的矩陣，其中表現(xiàn)R與S的矩陣分別為 p解：解： S R的表現(xiàn)矩陣為 p例：例：找出表現(xiàn)關(guān)係R2的矩陣，其中表現(xiàn)R的矩陣為p解：解：表現(xiàn)關(guān)係R2的矩陣為 利用有向圖表現(xiàn)關(guān)係利用有向圖表現(xiàn)關(guān)係 p還有一種重要的方法，以圖形方式來(lái)表現(xiàn)關(guān)係。每個(gè)在集合中的元素以頂點(diǎn)來(lái)表示，有序?qū)κ褂靡粋€(gè)有方向之邊來(lái)表現(xiàn)。當(dāng)我們考慮有限集合上的關(guān)係時(shí)，這種圖形表現(xiàn)法是種有向圖有向圖(directed graph or digraph)。p定義：定義：一個(gè)有向圖包含一個(gè)頂點(diǎn)(vertex)（或是節(jié)點(diǎn)(nod

7、e)）集合V，以及一個(gè)V中元素之有序?qū)Χ喑杉螮，其元素稱為邊(edge)（或是弧(arc)）。頂點(diǎn)a稱為邊(a, b)的初始點(diǎn)(initial vertex)，而頂點(diǎn)b成為此邊的終點(diǎn)(terminal vertex)。由(a, a)所形成的邊用一個(gè)由頂點(diǎn)a到本身的弧來(lái)表現(xiàn)，這樣的邊稱為迴圈迴圈(loop)。 p例：例：以a, b, c和d為頂點(diǎn)，(a, b), (a, d), (b, b), (b, d), (c, a), (c, b)和(d, b)為邊所成之有向圖如下圖所示。 p例：例：表現(xiàn)在集合1, 2, 3, 4上的關(guān)係R = (1, 1), (1, 3), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (4, 1)，之有向圖如：p例：例：若表現(xiàn)關(guān)