[理工][DS考古] 交大103

[JoJo56 (JoJO)]

想請問以下幾題，順便對下答案
9.假設P不等於NP 當以下問題為P則選1 NP-hard or NP-complete選2 其他選3
(1)Find a longest simple path between two nodes,where the given graph has
   positive edge weights.
(2)Find a shortest simple path between two nodes in a directed graph with
   negative and/or positive edge weights ,and containing negative weight
   cycles.
(3)Find a negative weight directed cycle in a weight directed graph.
(4)   ""  positive                      ""
(5)Find a largest cycle in a graph,where the edge-weight is 1 for each edge.
(6)       smallest
(7)Find a max-cut in a flow network
(8)       min-cut
(9)Find a max independent set in an interval graph
(10)2-CNF SAT problem

想問問大家的答案，目前我寫的是2、7、8、9、10都是NPC，剩下的都不清楚
我很好奇他假設P不等於NP是不是有甚麼陷阱?
還有3既不屬於P又不屬於NPC那是又甚麼??

10.這題有圖片希望大大能自行翻一下
(1)n=8，所以output = 8! ??? (2) ???
↑這題我不曉得要寫甚麼，希望能解釋一下

11.我寫的是F T F F T

12.MAX flow 2+3 = 5，切邊(S,A)(A,C)(C,D)
有些邊流量並沒有滿(如A,C還有1的流量)，就直接切了，可以嗎？

求解，感恩

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.234.39.17
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1419338270.A.47F.html
推 FRAXIS: 1, 5, 7是NPC, 如果 P = NP, 那NPC = P 這題就變成多選題
→ FRAXIS: 不屬於P 又不屬於 NPC 是有可能的 像是co-NP-Hard..
推 APE36: 12.不行哦，要算到滿才會是正確解
推 JacobSyu: 11.a 若E小比Floyd快,我寫True...
→ JoJo56: 那請問第9題的所有答案是甚麼呢？想確認一下
→ JoJo56: 11題的話我是用DS的角度去看得Bellman's跟Floyd均為O(N^2)
→ JoJo56: Dijkstra's為O(n^2)但不可以有負邊
→ JoJo56: 12題用BFS來跑流量就找不到切邊的樣子
推 JacobSyu: 12.resudual net.cut為c(S,A)+c(C,D)=5
→ JacobSyu: 11.依照cormen bellman+Dijk.:O(VE+VlgE), Floyd O(V^3)
→ JacobSyu: 11.提及Bell. technique=>使人聯想John.說太細易有bug
→ JacobSyu: 9.NPC:1,2,4,5,6,7,8,9,10  P:3  (是這樣?
→ JacobSyu: 3.我想到bellman...O(VE)
推 JacobSyu: 6.即使weight=1, nC3+nC4+...+nCn=2^n仍屬NP
→ JacobSyu: 6.cycle至少由3邊構成...至多n
→ JacobSyu: 6.大碩筆記大部分有整理分類,要感謝之前大大...偉X 爛
推 JacobSyu: bellman可得最大負循環?最小負循環稍加修改應該也可以P?
推 JacobSyu: 或者bellman 只能判斷(找)負循環 最大(小)無法判定(問!
→ JoJo56: 11題因為DS上寫都為O(n^3)所以我才認為是一樣快，寫F
→ JoJo56: 但用ALGO來看，邊小的確是Bellman比較快 了解
→ JoJo56: O碩近幾年都沒有DS考古題的詳解，還挺困擾的
→ JoJo56: 12題的(a)用Edmonds-Karp求出MAX flow=5但找不出切邊
→ JoJo56: (b)用Ford-Fulkerson求出MAX Flow=4切邊(S,A)(A,C)(C,D)