作者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/m.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