※ 引述《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
不知道有沒有錯..