作者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/cn.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