作者:
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)