[理工] 清大資工計科研最後一題reduction

[can18 (18號)]

題目是 將無向圖中

HC reduce 至 HP

https://i.imgur.com/L9OH6L5.jpg

這樣轉換不知道可不可以？

感覺好像可以又有點怪怪的



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.14.160.181
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1517630997.A.6F4.html
→ s06i06: 已爆炸 幹+365
推 gary70812: tree 那題n是三小？ 感覺帶多少都可以
我算2
推 Dora5566: 幹有講無向圖喔?
有
我本來也是寫有向
發現好像不太行
→ Dora5566: 2
推 sam2000: 2
推 q1qip123: 看到這題直接笑出來哈哈哈嗚嗚嗚…
推 Dora5566: 我用接點拿邊的方式
求詳細
今年好多reduce
→ Dora5566: 有人知道清大正取幾分嗎
→ Dora5566: 或最低錄取
推 missingkid: 考幾分都是假的 是要看你能幹掉多少人
今年要幹掉1000人左右...
※ 編輯: can18 (101.14.160.181), 02/03/2018 12:20:20
推 gary70812: 到底怎麼算的 他也沒說n0有幾個
推 kai3570: 什麼什麼 n只有我算1嗎
→ kai3570: n0不是就是degree=1唷？
推 s06i06: Tree
推 sam2000: E+1=V E=deg/2
推 yaya517: 分享一下 希格瑪deg=2e=11n , e=v-1, v=6n, e=6n-1, 12n-
→ yaya517: 2=11n, n=2
推 s1020824: 1-b怎麼解啊qq
我算1222
※ 編輯: can18 (101.14.160.181), 02/03/2018 12:34:50
推 kai3570: 1-b我用高中的算法算XD
推 sam2000: 1~29分三堆 除3餘1 2 3的
算法跟s大一樣 s大答案跟我一樣嗎Q
※ 編輯: can18 (101.14.160.181), 02/03/2018 12:39:08
推 kssdpp222: 我算1224
幹我發現我加法加錯... 崩潰
※ 編輯: can18 (101.14.160.181), 02/03/2018 12:40:31
推 hsiohf5566: 1224...+1
推 missingkid: 我也是用餘數去算的 自己感覺蠻暴力
→ missingkid: 不知道有沒有其他方法
推 kai3570: 1224 +1
推 stacy62123: 嗚嗚GG
推 sam2000: 1224+1
Gggggg
推 ouryouth: 1224 +1
推 aRLJ: 我的想法是G中隨意一個點複製一份(該點的鄰點和接邊)，然後
→ aRLJ: 其中一個接邊到s另一個接邊到t
推 Dora5566: 計系寫60分鐘就出來了  無壓力
推 gary70812: 計組好難喔
推 donvito: 好多論述題 寫到手快斷掉
推 s06i06: 計系滿佛的
推 gary70812: banker algo 那題p1失敗後跳到p3後是不是要再check p1
推 a020304888a: 計系根本寫不完==
推 sarsman: 論述到沒時間惹qq
怎麼大家反應差那麼多XD
→ magic83v: 1b我一開始想窮舉找規律 舉幾個就放棄 第二次回來 用餘0
→ magic83v:  餘1 餘2 加到自己亂掉想驗算都不會==
往好處想我會算也算錯 QQ
推 arhtur945: 三的倍數我算980耶
c9取3 + c10取3 + c10取3 + (10取1*10取1*9取1)
推 Dora5566: 怎麼都沒公車…救命
推 leo0519: 1224+1
推 HungDa: 準備半天dp結果都考reduction啥鬼
→ JKLee: https://i.imgur.com/uHitb9Q.png
J大請問 你要怎麼保證u,v在HC為相鄰點
有可能 u ~> w1~> v ~> w2 ~> u才能繞成一個cycle吧
(上面的圖)
這樣 x -> u ~> w1~> v ~> w2 無法接到 y
或是 x -> u ~> w1~> v -> y 不為 HP
推 leoone: 那張圖是多找一個點連到所有點 所以所有情況都有考慮進去
→ arhtur945: 太棒了 我餘一跟餘二都數錯個 讚讚
※ 編輯: can18 (101.14.160.181), 02/03/2018 16:58:43
※ 編輯: can18 (101.14.160.181), 02/03/2018 17:01:14
→ JKLee: 上圖是將HC Prob. 轉成 HP Prob.
沒錯阿 可是要怎麼找u,v
你怎麼確定HC中u,v為相鄰
※ 編輯: can18 (101.14.160.181), 02/03/2018 17:02:56
→ JKLee: 若上右圖能找到HP,則HP兩端必為xy.將上右圖回復成上左圖,H
→ JKLee: P就可連成HC
→ JKLee: 找所有相鄰的uv.time=theta(|E|)=O(n^2)
→ JKLee: 找HP的演算法最多跑n^2次
了解了 要check多次
推 shownlin: 這題林立宇正課班NP後面有題台大103有類似的
推 sarsman: 我也是憑印象寫林立宇那題的解法，可是不確定印象有沒有
→ sarsman: 錯qq
推 Dora5566: 如果HC轉HP,用把某兩點之邊去除
→ Dora5566: 這種轉法可以嗎
估計不行 你去掉的邊不一定在HC中
推 Dora5566: 我沒有外接額外的點
推 Dora5566: 有道理
→ Dora5566: 我回去翻課本看看QQ
如果是有向圖的話 將任一點split成Vin 及Vout即可

推 aRLJ: 有向無向有差嗎?
有向將一點split成  Vin, Vout可以保證 :
  若有HP  Vout必為起點 Vin必為終點
  此時將Vin Vout merge可得原圖的HC

但在無向split成V1 V2中無法保證為起終點
有可能 HP 為 (V1 ~> ... ~> V2 ~> ....)
(所以我才又加了S,T 保證V1 V2他們是HP起點第2個及終點前2個
去掉S T就可merge回原圖的HC )

推 leoone: 子嘉說過圖形證明絕對不能拆邊 只能加東西進去
那是用induction的時候吧
不過確實 拆邊會出現不知道要拆哪一個邊的問題

推 aRLJ: 喔喔看懂了，原本是想說這個方法有向無向都可以用的意思
※ 編輯: can18 (1.173.124.34), 02/03/2018 21:49:09
推 winiel559: 講反了吧，是只能拆不能加
我也記得是 然後大多是拆點
※ 編輯: can18 (1.173.124.34), 02/03/2018 23:07:39
推 lldavuull: http://tinyurl.com/yav5s643 Reduction from HC to HP
我的做法應該就是這個
https://i.imgur.com/2pG8lM7.jpg
※ 編輯: can18 (1.173.124.34), 02/04/2018 00:03:15