[理工] 109清大 計科

看板Grad-ProbAsk作者 (c-看看你)時間4年前 (2021/01/04 20:05), 4年前編輯推噓11(11推 0噓 62→)
留言73則, 4人參與, 4年前最新討論串1/1
想問這題，不太確定自己對題目的理解正不正確 https://i.imgur.com/Ht1Fuer.jpg
https://i.imgur.com/8RFOJrv.jpg
這三題答案我都寫yes，然後下面是我畫的example，若有錯再麻煩各大神糾正，謝謝！ https://i.imgur.com/UdksBYK.jpg
還有這一題，不知道該怎麼證明 https://i.imgur.com/R6Qa95Q.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 112.104.18.31 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1609761923.A.551.html ※ 編輯: seafoodccu (112.104.18.31 臺灣), 01/04/2021 21:07:28
→
01/04 21:23, 4年前 , 1F
b-ii 畫個等腰三角形 邊長2,2,1
01/04 21:23, 1F
→
01/04 21:27, 4年前 , 2F
9.很經典 新增一個元素 sum/2
01/04 21:27, 2F
→
01/04 21:27, 4年前 , 3F
就可以從2-partition reduce成 3-partition
01/04 21:27, 3F
→
01/04 21:32, 4年前 , 4F
12.應該只要能構造就好
01/04 21:32, 4F
→
01/04 22:46, 4年前 , 5F
m大，還是不太懂，為什麼是新增sum/2的元素？
01/04 22:46, 5F
→
01/05 00:38, 4年前 , 6F
01/05 00:38, 6F
→
01/05 13:58, 4年前 , 7F
懂了，感謝m大！
01/05 13:58, 7F
推
01/07 10:28, 4年前 , 8F
01/07 10:28, 8F
→
01/07 10:28, 4年前 , 9F
各位你們b-ii 的例子都是錯的喔
01/07 10:28, 9F
→
01/07 11:38, 4年前 , 10F
感謝a大！請問有什麼好的例子嗎？畫不出來QQ
01/07 11:38, 10F
推
01/07 13:04, 4年前 , 11F
01/07 13:04, 11F
→
01/07 13:04, 4年前 , 12F
我朋友畫的 看起來應該是對的沒錯
01/07 13:04, 12F
→
01/07 13:12, 4年前 , 13F
想請問a大原PO原本畫的是哪裡有誤呢?
01/07 13:12, 13F
→
01/07 13:13, 4年前 , 14F
看起來x到各點max shortest都是8 其他abc點max shortest
01/07 13:13, 14F
→
01/07 13:13, 4年前 , 15F
path也是8，不知道我有哪裡沒注意到的地方QQ
01/07 13:13, 15F
推
01/07 13:16, 4年前 , 16F
不好意思 發現上面打錯更正 abcd max shortest path
01/07 13:16, 16F
→
01/07 13:28, 4年前 , 17F
我畫的如果X點把邊切成6：2的話，max shortest path會
01/07 13:28, 17F
→
01/07 13:28, 4年前 , 18F
變成6
01/07 13:28, 18F
→
01/07 13:29, 4年前 , 19F
這樣center只能在邊上
01/07 13:29, 19F
→
01/07 13:33, 4年前 , 20F
01/07 13:33, 20F
→
01/07 13:33, 4年前 , 21F
a大，如果x這樣設，好像也不符合了
01/07 13:33, 21F
→
01/07 13:40, 4年前 , 22F
不過s大原本不是切成44嗎@@?
01/07 13:40, 22F
→
01/07 13:47, 4年前 , 23F
但有更好的切法讓shortest path變更短呀，X只是我假設
01/07 13:47, 23F
→
01/07 13:47, 4年前 , 24F
的，所以對那張圖來說，有其他的在邊上的center可以
01/07 13:47, 24F
→
01/07 13:47, 4年前 , 25F
有最短的距離
01/07 13:47, 25F
→
01/07 13:52, 4年前 , 26F
不過題目不是只有說舉例嗎 > <?
01/07 13:52, 26F
→
01/07 14:05, 4年前 , 27F
01/07 14:05, 27F
→
01/07 14:07, 4年前 , 28F
不知道改成這樣對不對，我找不到任何其他在邊上的點
01/07 14:07, 28F
※ 編輯: seafoodccu (112.104.18.31 臺灣), 01/07/2021 14:22:41
→
01/07 14:23, 4年前 , 29F
有最大最短距離小於2，且點a、c的最大最短距離也是2
01/07 14:23, 29F
→
01/07 15:29, 4年前 , 30F
看起來沒錯，我也是最小只有找到2 acx
01/07 15:29, 30F
推
01/07 16:00, 4年前 , 31F
題目的absolutely center定義是要找可以到所有點的距離
01/07 16:00, 31F
→
01/07 16:00, 4年前 , 32F
的max最小那個 所以原po的那個只有切4，2那個點符合
01/07 16:00, 32F
→
01/07 16:01, 4年前 , 33F
我剛剛的那個反例中間是沒有點的 那是兩條邊 所以你只能
01/07 16:01, 33F
→
01/07 16:01, 4年前 , 34F
點在其中一邊上
01/07 16:01, 34F
→
01/07 16:03, 4年前 , 35F
原po新的那張圖你x只能選一個邊畫 不能畫在兩個邊上啦
01/07 16:03, 35F
推
01/07 16:08, 4年前 , 36F
01/07 16:08, 36F
→
01/07 16:08, 4年前 , 37F
要把他拉開來看
01/07 16:08, 37F
→
01/07 16:09, 4年前 , 38F
左邊是我的右邊是原po新的
01/07 16:09, 38F
→
01/07 16:10, 4年前 , 39F
我的應該才行得通
01/07 16:10, 39F
→
01/07 16:21, 4年前 , 40F
01/07 16:21, 40F
推
01/07 16:21, 4年前 , 41F
a大抱歉，我愚鈍還是不太懂QQ
01/07 16:21, 41F
→
01/07 16:21, 4年前 , 42F
01/07 16:21, 42F
→
01/07 16:21, 4年前 , 43F
這是原Po最一開始的圖，各點到各點的maximum shortest
01/07 16:21, 43F
→
01/07 16:21, 4年前 , 44F
path = 8(abcdx)，這樣不是表示abcdx每個都是 absolute
01/07 16:21, 44F
→
01/07 16:21, 4年前 , 45F
ly center嗎？（大家都相同，所以大家都是minimum?)
01/07 16:21, 45F
→
01/07 16:21, 4年前 , 46F
有誤會弄錯的地方請打醒我QQ
01/07 16:21, 46F
→
01/07 16:21, 4年前 , 47F
a大你的圖如果這樣切呢，是不是有更短的2.5
01/07 16:21, 47F
推
01/07 16:28, 4年前 , 48F
01/07 16:28, 48F
→
01/07 16:28, 4年前 , 49F
t大b小題說我們現在定義讓center可以在邊上讓到各點距離
01/07 16:28, 49F
→
01/07 16:28, 4年前 , 50F
更小 稱為absolutely center 所以我找到x到各點的距離最
01/07 16:28, 50F
→
01/07 16:28, 4年前 , 51F
多6 其他點就不可能是absolutely center了
01/07 16:28, 51F
→
01/07 16:29, 4年前 , 52F
回原po 竟然！看來我的也沒找到QQ
01/07 16:29, 52F
→
01/07 16:30, 4年前 , 53F
不知道有沒有大大能找到反例或是證明不會同時在點跟邊上
01/07 16:30, 53F
→
01/07 16:30, 4年前 , 54F
了
01/07 16:30, 54F
→
01/07 17:17, 4年前 , 55F
了解惹! 謝謝大家QQ
01/07 17:17, 55F
→
01/07 17:53, 4年前 , 56F
欸欸 所以我b-ii的例子也是錯的嗎QQ?
01/07 17:53, 56F
→
01/07 17:55, 4年前 , 57F
結果隨便舉個例子都錯 看來要想清楚一點QQ
01/07 17:55, 57F
→
01/07 17:55, 4年前 , 58F
會不會其實這題根本沒反例啊XD
01/07 17:55, 58F
推
01/07 23:05, 4年前 , 59F
考慮三個點a,b,c d(a,b) = L (最長的shortest path)
01/07 23:05, 59F
→
01/07 23:11, 4年前 , 60F
這樣有符合b-ii嗎
01/07 23:11, 60F
→
01/07 23:35, 4年前 , 61F
自答 不符合
01/07 23:35, 61F
推
01/07 23:47, 4年前 , 62F
上面的edge都是最短路徑
01/07 23:47, 62F
→
01/07 23:48, 4年前 , 63F
a,b是absolute center ， d1+d2 < max
01/07 23:48, 63F
→
01/07 23:54, 4年前 , 64F
假設有一點p在edge上，並且p也是absolute center
01/07 23:54, 64F
→
01/07 23:55, 4年前 , 65F
p必須在ab的最短路徑上(簡單證明)
01/07 23:55, 65F
→
01/07 23:57, 4年前 , 66F
令d(a,p) = max-d1，則d(b,p) = d1
01/07 23:57, 66F
推
01/07 23:59, 4年前 , 67F
根據定義 d(c,p) = max
01/07 23:59, 67F
→
01/08 00:00, 4年前 , 68F
但是根據上面所述 d(c,p) = min(max, d1+d2) = d1+d2
01/08 00:00, 68F
→
01/08 00:01, 4年前 , 69F
抱歉我寫錯了 我等等重回
01/08 00:01, 69F
→
01/08 00:46, 4年前 , 70F
我放棄 感覺有啥地方卡住了 應該可以從上面的方向去思考
01/08 00:46, 70F
推
01/08 18:30, 4年前 , 71F
01/08 18:30, 71F
→
01/08 18:30, 4年前 , 72F
目前想到的 看起來可以 求大大幫檢查
01/08 18:30, 72F
→
01/08 18:30, 4年前 , 73F
在2的邊中點 還有中間那點
01/08 18:30, 73F
‣ 更多 seafoodccu 的文章
文章代碼(AID): #1VymI3LH (Grad-ProbAsk)