作者magic83v (R7)
看板Grad-ProbAsk
标题[理工] 108交大资演reduction
时间Wed Feb 13 18:45:40 2019
https://i.imgur.com/jclhMmO.jpg
https://i.imgur.com/VqYEqap.jpg
HC <p HC3
想问一下这题各位的想法
我的想法是只加两个点 没办法转换到使x.y.z连续 刚好又有给以上皆非... 我就猜e了
这是我的想法
case2
https://i.imgur.com/whg0aom.jpg
case3
https://i.imgur.com/ACg4kkm.jpg
我直观想觉得应该要多个点才能做到
怕明天也考类似的又不会写想搞懂
感谢各位
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 27.247.162.70
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1550054743.A.F15.html
1F：推 HungDa: case2应该是A但是我把ab连起来考完才想到吐血02/13 18:51
2F：→ HungDa: case3应该ABCD吧02/13 18:51
3F：→ alen0303: 这题组有++记号 多选几个选项有搞头吗02/13 18:52
4F：→ HungDa: 错一个选项就整题组错有念书跟没念书一样0分哭哭02/13 18:54
5F：→ uttc: 还好有研究去年那题02/13 19:15
能请问你的想法吗
6F：→ eric131204: 所以这题答案是什02/13 19:16
7F：推 HungDa: 不知道反正我应该说错了02/13 19:33
※ 编辑: magic83v (27.247.162.70), 02/13/2019 20:45:30
9F：→ uttc: 某位好心人分享的去年的解法 可以参考比对 02/13 21:25
10F：推 FRAXIS: case 2, 因为 (x, y) 不相连，所以 HC 只能有 x - z - y 02/13 23:13
11F：→ FRAXIS: 的情况（y - z - x 是对称的，因为是 undirectied graph） 02/13 23:14
12F：→ FRAXIS: 所以用 a, b 两个点来限制是可以的 02/13 23:14
13F：推 Youhao: 只加两个edge a和b的degree都是1还会形成cycle吗 02/14 00:06
14F：推 FRAXIS: case 2 至少要加 4 个 edge 吧 02/14 12:01
15F：→ Youhao: 这样这题多选的意思是要选哪几个edge要加吗XD 02/14 13:08
16F：→ magic83v: 清大也没考reduction qq 02/14 16:35
17F：→ magic83v: F大能请问你边应该加在哪吗 02/14 16:36
18F：推 anonimo: 36B/37BC/38ABC 02/15 14:07
19F：推 agag5123: 楼上正解 a,b放进里面，只能一端流进另一端流出 02/15 14:29
20F：→ agag5123: 所以b) x-a-z-b-y,有汉米尔图要流过a一定要走x-a-z，那 02/15 14:31
21F：→ agag5123: 表示原本就有图可以走x-z 02/15 14:32
22F：→ magic83v: 好吧喷光 我的图完全乱画一通 02/15 14:32
23F：→ agag5123: c)比较复杂，a,b都要跟xyz相连，保证有汉米尔图从xyz任 02/15 14:38
24F：→ agag5123: 一点进来时，一定要走a或b，从剩下两点其中之一出去， 02/15 14:38
25F：→ agag5123: 然後因为还有a或b存在，它非得把剩下的a或b走完，才可 02/15 14:38
26F：→ agag5123: 能能完成汉米尔cycle 02/15 14:38
27F：→ agag5123: 如此一来有路径成立的话，把a,b拔掉就是对应的汉米尔了 02/15 14:40
28F：推 kkjja90236: 为何错一个选项就全错啦 02/18 15:00