推 JacobSyu: 推! 這大題頗難,,,3-CNF就不能在P解了吧... 12/29 09:51
→ FRAXIS: 你解了 就可以得到一百萬.. 12/29 21:20
推 JoJo56: 推，查了老半天沒搞懂 12/30 19:50
推 JacobSyu: 加油!! 2月中可以連續考到爽... 12/30 21:10
※ 引述《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.
NPC, Hamiltonian Path可以reduce到這個問題。
: (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.
NPC, 從(1)可以reduce到這問題，把edge weight變號。
: (3)Find a negative weight directed cycle in a weight directed graph.
P, Bellman-Ford algorithm可以解。
: (4) "" positive ""
P, 把edge weight變號的，然後用Bellman-Ford algorithm。
: (5)Find a largest cycle in a graph,where the edge-weight is 1 for each edge.
NPC, Hamiltonian tour可以reduce到這問題。
: (6) smallest
P, 針對某一個點，只要用BFS就可以找出包含該點的最小cycle。
所以只要使用|V|次BFS就可以找出圖中最小cycle了。
http://en.wikipedia.org/wiki/Girth_%28graph_theory%29
: (7)Find a max-cut in a flow network
NPC, well-known result
: (8) min-cut
P, 用maximum-flow-minumum-cut解。
http://en.wikipedia.org/wiki/Minimum_cut
: (9)Find a max independent set in an interval graph
P, 用greedy algorithm解。
http://en.wikipedia.org/wiki/Interval_scheduling
: (10)2-CNF SAT problem
P, 用DFS可以解。
http://en.wikipedia.org/wiki/2-satisfiability#Algorithms
不知道有沒有錯..
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.149
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1419777600.A.F70.html