推 Karena1983:感謝 ^^ 03/26 20:17
推 ohstar:total order 是不是 |R|= n(n-1)/2 阿? 03/31 22:25
※ 引述《Karena1983 (@ __@")》之銘言：
: 熊熊忘記partial ordering 和 total ordering 這兩種relationship是怎樣的特性
: 翻了翻參考書也找不到
tatal order 全部有序
也就是在set A 之中 取任意兩element a,b
必存在 aRb 或 bRa 其中一個
比較公式一點的講法, 就是符合
1. reflexive
2. antisymmetric
3. transitive
4. exclusive-or
常見的例子是 (R, <) 或 (R, >) 之類的
partial order 部份有序
定義一點的講法, 就是符合
1. reflexive
2. antisymmetric
3. transitive
常見的例子是 ( R^2 , < ) 之類的
( 把 < 定義成 (a1,a2)<(b1,b2) if a1<b1 且 a2<b2 )
畫圖來說就是像這樣
partial order tatal order
a a
/ \ |
b c b
/ \ \ |
d e f c
\ / \ / |
g h d
↑
不一定長這樣
有很多種可能性
: 如果 |A| = n, 求 partial / total order relation on A 有公式套嗎？
total order: |R| = n(n+1)/2
partial order: 我想不到XD 待強者補完
: 順便問一題 98中山資工 離散
: Q: |A|=30 , equivalence relation R on A partitions A into equivalence
: classes A1, A2, A3, where |A1| = |A2| = |A3|, what is |R| = ?
我的答案是 |R| = 300
理由：
[ A1 R A1 , A1 R A2 , A1 R A3 ] [ 全都1 0 0 ]
MR = [ A2 R A1 , A2 R A2 , A2 R A3 ] = [ 0 全都1 0 ]
[ A3 R A1 , A3 R A2 , A3 R A3 ] [ 0 0 全都1 ]
因此
|R| = n^2 * 3 = 10^2 * 3 = 300
--
人家可不是為了你才這樣做的哦!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.198.35.85
※ 編輯: dendrobium 來自: 60.198.35.85 (03/26 20:11)