[理工] 109清大 計科

看板Grad-ProbAsk作者 (c-看看你)時間4年前 (2021/01/04 20:05), 4年前編輯推噓11(11062)
留言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, 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, 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, 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: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, 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, 4年前 , 41F
a大抱歉,我愚鈍還是不太懂QQ
01/07 16:21, 41F

01/07 16:21, 4年前 , 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, 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, 4年前 , 72F
目前想到的 看起來可以 求大大幫檢查
01/08 18:30, 72F

01/08 18:30, 4年前 , 73F
在2的邊中點 還有中間那點
01/08 18:30, 73F
文章代碼(AID): #1VymI3LH (Grad-ProbAsk)