[理工] 108 交大資演 reduction

[aa871220 (怪人幹怪事)]

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://www.ptt.cc/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
→ aa871220: 自己補 從鬼打牆出來了== 已解決
推 walt9420: 請問一下 為何原G中若含有path<x-z-y >的HC 若且唯若 新
→ walt9420: 圖G’中含path<x-b-z-a-y>的HC
→ aa871220: （=>)
→ aa871220: 設G中含path<v0,v1...x,z,y,...,vn>的HC
→ aa871220: 則可以在G’中走<v0,v1...x,b,z,a,y,...,vn>為其HC
→ aa871220: (<=)
→ aa871220: 設G’中含<v0,v1...x,b,z,a,y,...,vn>HC
→ aa871220: 由於a,b為2-degree,因此HC一定會經
→ aa871220: Edge(x,b),(b,z),(z,a)(a,y)
→ aa871220: 故（a,b),(b,c)一定沒被走過
→ aa871220: 可在G中走<v0,v1...x,z,y,...,vn>得HC
→ aa871220: 倒數第二航更正 是（x,z),(z,y)
推 walt9420: 謝謝大大 祝考試順利
s
※ 編輯: aa871220 (140.113.136.219 臺灣), 01/04/2021 15:41:50