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