关系之性质与表现矩阵－－反身性.PPTVIP

第八章 關係(Relations) §8.1 Relations and Properties §8.2 n-ary Relations and Their Applications §8.3 Representing Relations §8.4 Closures of Relations §8.5 Equivalence Relations §8.6 Partial Orderings 利用矩陣表現關係(§8.3) 有限集合間的關係能以零－壹矩陣來表現。假設R是由集合A = {a1, a2, …, am}到集合B = {b1, b2, …, bn}（此處集合的元素可以任意方式排序，但若A = B時，我們使用相同的排列順序）。關係R能以矩陣MR = [mij]表示，其中 換句話說，表現關係R的零－壹矩陣中，第(i, j)個位置的元素為1，若ai與bj有關係；而第(i, j)個位置的元素為0，若ai與bj沒有關係。（這種表示法與集合A與B使用之順序相關。） 例：假設A = {1, 2, 3}而B = {1, 2}。令R為由A到B的關係，包含所有的有序對(a, b)，如果a?A，b?B，而且a b。何為R之矩陣表示法，其中a1= 1, a2 = 2, a3 = 3，而且b1 = 1, b2 = 2？ 解： 例：令A = {a1, a2, a3}而B = {b1, b2, b3, b4, b5}。若R的表現矩陣如下，則哪些有序對再關係R中？ 解： 關係之性質與表現矩陣－－反身性 當關係R是反身的若(a, a)?R，當a?A。 R是反身的若且唯若(ai, ai)?R，i = 1, 2, ..., n。 R是反身的若且唯若mii = 1，i = 1, 2, …, n。 換句話說，R是反身的，如果矩陣MR的主對角線之元素都為1。 譬如：若A = {1, 2}，R = {(1, 1), (1, 2), (2, 2)}。則 MR = 關係之性質與表現矩陣－－對稱性 在A = {a1, a2, …, an}上的關係R是對稱的，若且唯若 當(ai, aj)?R，能推導出(aj, ai)?R。 以矩陣來看，R是對稱的若且唯若對所有的整數對(i, j)，mij = mji。即，(MR) = (MR)t。 譬如：若A = {1, 2}，R = {(1, 1), (1, 2), (2, 1)}。則 MR = 關係之性質與表現矩陣－－反對稱性 關係R是反對稱的，其表現矩陣有下列性質：當i ? j時，若mij = 1，則mji = 0。 換言之，當i ? j，要不是mij = 0就是mji = 0。至於當i = j時則沒有限制。 譬如：若A = {1, 2}，R = {(1, 2), (2, 2)}。則 MR = 例：假設表現關係R的矩陣為 判斷R是否為反身的？對稱的？反對稱的？ 解： 布爾運算中的聯合(join)和交遇(meet) 能夠用來找出表現兩個關係之聯集與交集的矩陣。 例：假設R1和R2為集合A上的關係，其表現矩陣分別為 何為表現R1?R2和R1?R2的矩陣？ 假設R為由A到B的關係，S是由B到C的關係。而集合A，B與C分別有m，n和p個元素。令表現關係S?R ，R和S的矩陣分別為 MS?R = [tij]，MR = [rij]和MS = [sij]（矩陣之大小分別為m?p，m?n和n?p）。 有序對(ai, cj)屬於S?R若且唯若存在元素bk?B使得(ai, bk)屬於R，(bk, cj)屬於S。 因此，tij = 1若且唯若存在k使得rik = skj = 1。根據布爾積的定義， MS?R = MR ☉ MS 。 例：找出表現關係S?R的矩陣，其中表現R與S的矩陣分別為 解： S?R的表現矩陣為 例：找出表現關係R2的矩陣，其中表現R的矩陣為 解：表現關係R2的矩陣為 利用有向圖表現關係 還有一種重要的方法，以圖形方式來表現關係。每個在集合中的元素以頂點來表示，有序對使用一個有方向之邊來表現。當我們考慮有限集合上的關係時，這種圖形表現法是種有向圖(directed graph or digraph)。 定義：一個有向圖包含一個頂點(vertex)（或是節點(node)）集合V，以及一個V中元素之有序對多成集合E，其元素稱為邊(edge)（或是弧(arc)）。頂點a稱為邊(a, b)的初始點(initial vertex)，而頂點b成為此邊的終點(terminal vertex)。 由(a, a)所形成的邊用一個由頂點a到本身的弧來表現，這樣的