Re: [理工] 離散 Antisymmetric Relations 個數

看板Grad-ProbAsk作者Honor1984 (希望願望成真)時間9年前 (2016/09/14 13:25)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/3 (看更多)

※ 引述《brad84622 (brad84622)》之銘言： : http://i.imgur.com/fZIj2wF.jpg

: 主要是b選項 : http://i.imgur.com/iDtJKET.jpg

: 不太明白為何對角線一定是1 antisymmetric relation的定義 If R(a,b) and R(b,a), then a = b 或者 If R(a.b) with a =/= b, them R(b,a) must not hold. 所以對角線項不受限制，既然問題問|R|最大的情況就給所有的對角線項1 接下來是非對角線項設i =/= j 如M_ij = 1 => M_ji = 0 所以M_ij和M_ji綁在一起只要其中有一個1 另外一個一定得是0 所以求|R|最大的情況時就是在M_ij, M_ji這一個非對角項組裡面挑一個為1 另一個為0 總共有2種選擇而非對角項組總共有(n-1) + (n-2) + ... + 1 = n(n-1)/2 所以|R|最大的情況下是 1.對角項全1 2.每個非對角項組都是一個1，另一個為0的情況因此就有1 * 2 * 2 * 2 ... * 2 = 2自乘n(n-1)/2 種組合最後結果就是2^[n(n-1)/2]種關係矩陣滿足|R|最大的情況 : 而且反對稱部分算在一起 : 跟前面的算法不太一樣 : http://i.imgur.com/C7BRzjZ.jpg

: http://i.imgur.com/hhTmVI0.jpg

: 是我對題目的理解有錯嗎？ : ----- : Sent from JPTT on my Samsung SM-N9208. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.56.9.110 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1473830733.A.B4D.html

推

brad84622

09/14 19:05, , 1^F

09/14 19:05, 1^F

‣ 返回看板[ Grad-ProbAsk ] 研究

‣ 更多 Honor1984 的文章

文章代碼(AID): #1NsDzDjD (Grad-ProbAsk)