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