作者aa871220 (怪人干怪事)
看板Grad-ProbAsk
标题[理工] 108 交大资演 reduction
时间Sun Dec 6 18:24:14 2020
https://i.imgur.com/Ntx9BFv.jpg
板上某篇文章看过了
正确答案是如下左图 字有点丑抱歉
原G中若含有path<x-z-y >的HC 若且唯若 新图G’中含path<x-b-z-a-y>的HC
但不知道是哪里逻辑不对
一开始想到的是右下图
原G中若含有path<x-z-y >的HC 若且唯若 新图G’中含path<x-b-a-z-y>的HC
我的想法是只要能确保能从y经G内部走到x就能透过<x-b-a-z-y>完成HC
不知道有没有人能提供反例点醒我QQ
https://i.imgur.com/eNwBwOH.jpg
-----
Sent from JPTT on my iPhone
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.113.136.218 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1607250256.A.00B.html
※ 编辑: aa871220 (140.113.136.218 台湾), 12/06/2020 18:27:43
※ 编辑: aa871220 (140.113.136.218 台湾), 12/06/2020 18:29:07
1F：→ aa871220: 自己补 从鬼打墙出来了== 已解决12/06 19:37
2F：推 walt9420: 请问一下 为何原G中若含有path<x-z-y >的HC 若且唯若 新12/08 23:45
3F：→ walt9420: 图G’中含path<x-b-z-a-y>的HC12/08 23:45
4F：→ aa871220: （=>)12/10 17:44
5F：→ aa871220: 设G中含path<v0,v1...x,z,y,...,vn>的HC12/10 17:44
6F：→ aa871220: 则可以在G’中走<v0,v1...x,b,z,a,y,...,vn>为其HC12/10 17:44
7F：→ aa871220: (<=) 12/10 17:44
8F：→ aa871220: 设G’中含<v0,v1...x,b,z,a,y,...,vn>HC12/10 17:44
9F：→ aa871220: 由於a,b为2-degree,因此HC一定会经12/10 17:44
10F：→ aa871220: Edge(x,b),(b,z),(z,a)(a,y)12/10 17:44
11F：→ aa871220: 故（a,b),(b,c)一定没被走过 12/10 17:44
12F：→ aa871220: 可在G中走<v0,v1...x,z,y,...,vn>得HC12/10 17:44
13F：→ aa871220: 倒数第二航更正 是（x,z),(z,y)12/10 17:44
14F：推 walt9420: 谢谢大大 祝考试顺利12/12 08:58
s
※ 编辑: aa871220 (140.113.136.219 台湾), 01/04/2021 15:41:50