[理工] 109清大 計科

[seafoodccu (c-看看你)]

想問這題，不太確定自己對題目的理解正不正確
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
→ mathtsai: b-ii 畫個等腰三角形 邊長2,2,1
→ mathtsai: 9.很經典 新增一個元素 sum/2
→ mathtsai: 就可以從2-partition reduce成 3-partition
→ mathtsai: 12.應該只要能構造就好
→ seafoodccu: m大，還是不太懂，為什麼是新增sum/2的元素？
→ mathtsai: https://reurl.cc/e80A07 參考
→ seafoodccu: 懂了，感謝m大！
推 alex391a: https://i.imgur.com/SmZqPnO.jpg
→ alex391a: 各位你們b-ii 的例子都是錯的喔
→ seafoodccu: 感謝a大！請問有什麼好的例子嗎？畫不出來QQ
推 alex391a: https://i.imgur.com/SveTCTJ.jpg
→ alex391a: 我朋友畫的 看起來應該是對的沒錯
→ try66889: 想請問a大原PO原本畫的是哪裡有誤呢?
→ try66889: 看起來x到各點max shortest都是8 其他abc點max shortest
→ try66889: path也是8，不知道我有哪裡沒注意到的地方QQ
推 try66889: 不好意思 發現上面打錯更正 abcd max shortest path
→ seafoodccu: 我畫的如果X點把邊切成6：2的話，max shortest path會
→ seafoodccu: 變成6
→ seafoodccu: 這樣center只能在邊上
→ seafoodccu:  https://i.imgur.com/9DPQi9G.jpg
→ seafoodccu: a大，如果x這樣設，好像也不符合了
→ try66889: 不過s大原本不是切成44嗎@@?
→ seafoodccu: 但有更好的切法讓shortest path變更短呀，X只是我假設
→ seafoodccu: 的，所以對那張圖來說，有其他的在邊上的center可以
→ seafoodccu: 有最短的距離
→ try66889: 不過題目不是只有說舉例嗎 > <?
→ seafoodccu:  https://i.imgur.com/PPM8Mig.jpg
→ seafoodccu: 不知道改成這樣對不對，我找不到任何其他在邊上的點
※ 編輯: seafoodccu (112.104.18.31 臺灣), 01/07/2021 14:22:41
→ seafoodccu: 有最大最短距離小於2，且點a、c的最大最短距離也是2
→ try66889: 看起來沒錯，我也是最小只有找到2 acx
推 alex391a: 題目的absolutely center定義是要找可以到所有點的距離
→ alex391a: 的max最小那個 所以原po的那個只有切4，2那個點符合
→ alex391a: 我剛剛的那個反例中間是沒有點的 那是兩條邊 所以你只能
→ alex391a: 點在其中一邊上
→ alex391a: 原po新的那張圖你x只能選一個邊畫 不能畫在兩個邊上啦
推 alex391a: https://i.imgur.com/yZxbUhO.jpg
→ alex391a: 要把他拉開來看
→ alex391a: 左邊是我的右邊是原po新的
→ alex391a: 我的應該才行得通
→ seafoodccu:  https://i.imgur.com/kCxtXaV.jpg
推 try66889: a大抱歉，我愚鈍還是不太懂QQ
→ try66889: https://i.imgur.com/wRuafOK.jpg
→ try66889: 這是原Po最一開始的圖，各點到各點的maximum shortest
→ try66889: path = 8(abcdx)，這樣不是表示abcdx每個都是 absolute
→ try66889: ly center嗎？（大家都相同，所以大家都是minimum?)
→ try66889: 有誤會弄錯的地方請打醒我QQ
→ seafoodccu: a大你的圖如果這樣切呢，是不是有更短的2.5
推 alex391a: https://i.imgur.com/8ffEKMp.jpg
→ alex391a: t大b小題說我們現在定義讓center可以在邊上讓到各點距離
→ alex391a: 更小 稱為absolutely center 所以我找到x到各點的距離最
→ alex391a: 多6 其他點就不可能是absolutely center了
→ alex391a: 回原po 竟然！看來我的也沒找到QQ
→ alex391a: 不知道有沒有大大能找到反例或是證明不會同時在點跟邊上
→ alex391a: 了
→ try66889: 了解惹! 謝謝大家QQ
→ mathtsai: 欸欸 所以我b-ii的例子也是錯的嗎QQ?
→ mathtsai: 結果隨便舉個例子都錯 看來要想清楚一點QQ
→ mathtsai: 會不會其實這題根本沒反例啊XD
推 mathtsai: 考慮三個點a,b,c d(a,b) = L (最長的shortest path)
→ mathtsai: https://imgur.com/UqlK6C4 這樣有符合b-ii嗎
→ mathtsai: 自答 不符合
推 mathtsai: https://imgur.com/xasTue5 上面的edge都是最短路徑
→ mathtsai: a,b是absolute center ， d1+d2 < max
→ mathtsai: 假設有一點p在edge上，並且p也是absolute center
→ mathtsai: p必須在ab的最短路徑上(簡單證明)
→ mathtsai: 令d(a,p) = max-d1，則d(b,p) = d1
推 mathtsai: 根據定義 d(c,p) = max
→ mathtsai: 但是根據上面所述 d(c,p) = min(max, d1+d2) = d1+d2
→ mathtsai: 抱歉我寫錯了 我等等重回
→ mathtsai: 我放棄 感覺有啥地方卡住了 應該可以從上面的方向去思考
推 alex391a: https://i.imgur.com/OlhFpb0.jpg
→ alex391a: 目前想到的 看起來可以 求大大幫檢查
→ alex391a: 在2的邊中點  還有中間那點
→ coco5747769:  https://i.imgur.com/kj6bCF9.jpg  我是畫這樣求檢
→ coco5747769: 查
推 alex391a: 跟我畫的類似吧