楼主:
aa871220 (TMVP_Yueko)
2020-12-06 18:24:14https://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
楼主:
aa871220 (TMVP_Yueko)
2020-12-10 17:44:00（=>)设G中含path<v0,v1...x,z,y,...,vn>的HC则可以在G’中走<v0,v1...x,b,z,a,y,...,vn>为其HC(<=)设G’中含<v0,v1...x,b,z,a,y,...,vn>HC由于a,b为2-degree,因此HC一定会经Edge(x,b),(b,z),(z,a)(a,y)故（a,b),(b,c)一定没被走过可在G中走<v0,v1...x,z,y,...,vn>得HC倒数第二航更正 是（x,z),(z,y)