[理工] [離散] 二元關係計數

看板Grad-ProbAsk作者 (aska)時間12年前 (2012/02/12 11:04), 編輯推噓12(12推 0噓 33→)
留言45則, 11人參與, 最新討論串1/1
有一題是這樣的 是二元關係 共有五個元素 構成5*5矩陣 問 reflexive and symmetric but not transitive 答案寫 2^10 - ΣS(5,i) (i從1~5) = 972 想請問 二元關係的話 reflexive and symmetric 不就代表transitive 成立了嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.116.112.16
→
02/12 11:24, , 1F
反例 {(1,2)(2,1)(2,3)(3,2)} union R0
02/12 11:24, 1F
→
02/12 12:00, , 2F
可是二元關係只有1和0不是嗎....
02/12 12:00, 2F
→
02/12 12:45, , 3F
不是喔 而且題目都說有五元了
02/12 12:45, 3F
→
02/12 13:21, , 4F
二元關係是指元素與元素之間的關係只有0跟1
02/12 13:21, 4F
→
02/12 18:40, , 5F
沒有啊，反身對稱遞移是等價關係啊~~
02/12 18:40, 5F
推
02/12 18:46, , 6F
onlyeric23提的反例很好了 有(3,2)和(2,1)
02/12 18:46, 6F
→
02/12 18:46, , 7F
但不一定有(3,1)
02/12 18:46, 7F
→
02/12 18:47, , 8F
二元關係 意思就是"有"或"沒有"關係 換句話說就是1和0
02/12 18:47, 8F
→
02/12 18:48, , 9F
劃成5*5的01矩陣即可表示五個元素對五個元素間的關係
02/12 18:48, 9F
→
02/12 19:45, , 10F
全-等價關係
02/12 19:45, 10F
→
02/12 23:37, , 11F
ΣS(5,i) 這個是怎麼算啊?
02/12 23:37, 11F
→
02/12 23:43, , 12F
第二類Stirling數
02/12 23:43, 12F
推
02/13 00:13, , 13F
解答扣法就是拿所有反身對稱 去扣相異等價關係個數
02/13 00:13, 13F
推
02/13 00:14, , 14F
關係一定都是「有」或「沒有」 跟幾元沒關吧
02/13 00:14, 14F
→
02/13 00:15, , 15F
二元關係是AxB的一個子集 三元關係是AxBxC的一個子集
02/13 00:15, 15F
→
02/13 00:16, , 16F
並不是說三元關係就是指元素跟元素之間是0,1,2
02/13 00:16, 16F
→
02/13 00:17, , 17F
三元關係寫下來也是一個三維的0-1陣列
02/13 00:17, 17F
推
02/13 00:19, , 18F
定義問題 這邊打字沒辦法打完全 感謝樓上補足
02/13 00:19, 18F
→
02/13 00:20, , 19F
但是 R為A至B的關係 S為B至C的關係 作關係合成
02/13 00:20, 19F
→
02/13 00:20, , 20F
你所得到的關係矩陣 照理說會由{0,1,2}組成
02/13 00:20, 20F
→
02/13 00:21, , 21F
但通常會將它化成 Boolean matrix 只剩下{0,1}組成
02/13 00:21, 21F
→
02/13 00:22, , 22F
那如果你是想說 三元關係是以三維矩陣表示 那就是0和1組成
02/13 00:22, 22F
推
02/13 00:23, , 23F
你所提到的R跟S都是二元關係 合成以後也還是二元關係
02/13 00:23, 23F
推
02/13 00:24, , 24F
想問pikachu大 相異等價關係個數指的是??
02/13 00:24, 24F
→
02/13 00:24, , 25F
為什麼合成以後矩陣要用0,1,2？
02/13 00:24, 25F
推
02/13 00:26, , 26F
因為 aRb 且 bSc 所以為2
02/13 00:26, 26F
推
02/13 00:27, , 27F
ΣS(5,i)就是5個元素相異等價關係個數也就是P5阿
02/13 00:27, 27F
→
02/13 00:28, , 28F
若aRb 或 bSc 只有一個有關係 則為1
02/13 00:28, 28F
→
02/13 00:28, , 29F
你要有反身對稱但沒遞移 不就拿所有反身遞移去扣等價
02/13 00:28, 29F
→
02/13 00:29, , 30F
關係個數 因為有反身對稱遞移不就等價關係
02/13 00:29, 30F
推
02/13 00:30, , 31F
Let T = R。S,(a,c)in T<=>存在b s.t (a,b)in R,(b,c)in S
02/13 00:30, 31F
→
02/13 00:31, , 32F
你講的合成是這個定義下的合成嗎@@
02/13 00:31, 32F
→
02/13 00:32, , 33F
看起來你的合成矩陣只是原先兩個矩陣相加
02/13 00:32, 33F
推
02/13 00:33, , 34F
嗯 看起來應該是同一個合成定義
02/13 00:33, 34F
→
02/13 00:33, , 35F
不是欸 不是相加 是矩陣相乘
02/13 00:33, 35F
→
02/13 00:35, , 36F
可能我剛剛打的不太對 aTc 的關係矩陣 如果某一元素是2
02/13 00:35, 36F
→
02/13 00:35, , 37F
則代表 aRb且bSc 有兩個
02/13 00:35, 37F
→
02/13 00:36, , 38F
前面應該是打錯了 造成誤解 拍謝~
02/13 00:36, 38F
推
02/13 00:38, , 39F
相乘的話 (a,b)in R且(b,c)in S應該只會對乘法結果貢獻1
02/13 00:38, 39F
→
02/13 00:40, , 40F
ok我了解你的意思了 但這樣子乘出來的矩陣會是0~n不只0~2
02/13 00:40, 40F
→
02/13 00:41, , 41F
因為T矩陣裡 (a,c)=k 代表a跟c之間有k個不同的走法
02/13 00:41, 41F
推
02/13 00:44, , 42F
所以 那個n 其實還是要看b的元素個數 才能決定
02/13 00:44, 42F
→
02/13 00:44, , 43F
n最多不會超過b的元素個數
02/13 00:44, 43F
→
02/13 00:45, , 44F
bbhands 已經把詳細的合成與關係矩陣的關係寫出啦~
02/13 00:45, 44F
→
09/11 14:55, , 45F
ok我了解你的意思了 https://daxiv.com
09/11 14:55, 45F
‣ 更多 askaleroux 的文章
文章代碼(AID): #1FDonCFB (Grad-ProbAsk)