Problem #1 (Conceptual Questions) [20 points] Please answer "yes" or "no" to the following questions. If your answer is no, please state the reason or provide a counter-example. (1) A network flow problem can always be solved as a linear program. (2) We can use the simplex method to solve the network program problems. (3) The shortest path can always be found in a directed graph. (4) The maximum flow problem can be unbounded. (5) All integer programs are difficult to solve. (6) In general, integer programs are harder to solve than linear programs. (7) Dijkstra's algorithm is a polynomial-time algorithm. (8) The branch-and-bound algorithm is a polynomial-time algorithm. (9) The Ford-Fulkerson algorithm for the maximum flow problem is a polynomial-time algorithm. (10) Some maximum-flow problems could not be formulated as a linear program. 2