[理工] 107台大數學 106台聯大計組

看板Grad-ProbAsk作者 (萬能史哥)時間5年前 (2019/02/05 18:03), 編輯推噓2(2推 0噓 9→)
留言11則, 4人參與, 5年前最新討論串1/1
不好意思 小弟想弱弱的請教一下 先是第一題 107台大數學 https://imgur.com/StvE96v.jpg
他這題是說要尋找n個頂點，簡單圖的可能性，那我想問大家這題要怎麼算呢？ 因為簡單圖的點有可能邊連到自己，那我想問一下簡單圖的定義一定要是連通圖嗎？ 可以有孤立點嗎？ 第二題 106台聯大 計組 https://imgur.com/MKO1T83.jpg
https://imgur.com/Pcnl61L.jpg
https://imgur.com/ixqbFua.jpg
這題我題目完全都不懂他是什麼意思，為什麼解答要多一個xor， 然後為什麼operation信號又多一個4？ 大神可以講得越詳細越好嗎拜託了 ～～～～ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.113.95 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1549361003.A.E18.html
→
02/05 18:21, 5年前 , 1F
1.簡單圖跟連通圖應該是兩件事?
02/05 18:21, 1F
→
02/05 18:23, 5年前 , 2F
adjacency matrix共n平方格 每格代表一條邊存在與否
02/05 18:23, 2F
推
02/05 18:23, 5年前 , 3F
題幹說要xor gate啊
02/05 18:23, 3F
→
02/05 18:23, 5年前 , 4F
總共N^2條可能的邊 所以總共應該有2^(N^2)可能的圖?
02/05 18:23, 4F
→
02/05 18:23, 5年前 , 5F
（4）前面有一段字講很清楚
02/05 18:23, 5F
推
02/05 23:23, 5年前 , 6F
一般simple graph的定義是任2點之間最多一條邊
02/05 23:23, 6F
→
02/05 23:24, 5年前 , 7F
這題又允許每點有loop 所以最多可有C(n,2)+n條邊
02/05 23:24, 7F
→
02/05 23:25, 5年前 , 8F
每邊可有可無兩種選擇 所以可以有2^(C(n,2)+n)種圖
02/05 23:25, 8F
→
02/05 23:29, 5年前 , 9F
第二小題問m個邊 那就是所有邊取m個 C(C(n,2)+n , m)
02/05 23:29, 9F
→
02/06 00:46, 5年前 , 10F
想錯了，C(n,2)+n種才對
02/06 00:46, 10F
→
02/09 09:31, 5年前 , 11F
好的謝謝 我再去研究一下
02/09 09:31, 11F
‣ 更多 kaidi620 的文章
文章代碼(AID): #1SMLzhuO (Grad-ProbAsk)