All from Algorithm Design p.188-190.
和訳はまだ
Question1:
T or F?
Let G be an arbitrary connected, undirected graph with a distinct cost c(e) on every edge e. Suppose
e* is the cheapest edge in G. Then there is a minimum spanning tree T of G that contains the edge e*.
Answer:
True. Refer to the proof of correctness of Prim's alg.
Q2:
(a)Suppose we are given an instance of the minimum spanning tree problem on a graph G with edge costs that are all positive and distinct. Let T be a minimum spanning tree for this instance. Now suppose we replace each edge cost by its square, thereby creating a new instance the problem with the same graph but different costs.
T or F? T must still be a minimum spanning tree for this new instance.
Answer:
True. When a >= b and c >= d(all positive integers), a^2 + c^2 > b^2 + d^2. This shows T's cost must still be minimum.
(b)Suppose we are given an instance of the shortest s-t path problem on a directed graph G. We assume that all edge costs are positive and distinct. Let P be a minimum-cost s-t path for this instance. Now suppose we replace each edge cost c(e) by its square c(e)^2, thereby creating a instance of the problem with the same graph but different costs.
T or F? P must still be a minimum-cost s-t path for this new instance.
Answer:
False. Suppose it is true. Then when a+b>=c+d, a^2+b^2>=c^2+d^2. This is simply false(consider the case where a = 3, b = 1, c = 2 and d = 2).
和訳はまだ
Question1:
T or F?
Let G be an arbitrary connected, undirected graph with a distinct cost c(e) on every edge e. Suppose
e* is the cheapest edge in G. Then there is a minimum spanning tree T of G that contains the edge e*.
Answer:
True. Refer to the proof of correctness of Prim's alg.
Q2:
(a)Suppose we are given an instance of the minimum spanning tree problem on a graph G with edge costs that are all positive and distinct. Let T be a minimum spanning tree for this instance. Now suppose we replace each edge cost by its square, thereby creating a new instance the problem with the same graph but different costs.
T or F? T must still be a minimum spanning tree for this new instance.
Answer:
True. When a >= b and c >= d(all positive integers), a^2 + c^2 > b^2 + d^2. This shows T's cost must still be minimum.
(b)Suppose we are given an instance of the shortest s-t path problem on a directed graph G. We assume that all edge costs are positive and distinct. Let P be a minimum-cost s-t path for this instance. Now suppose we replace each edge cost c(e) by its square c(e)^2, thereby creating a instance of the problem with the same graph but different costs.
T or F? P must still be a minimum-cost s-t path for this new instance.
Answer:
False. Suppose it is true. Then when a+b>=c+d, a^2+b^2>=c^2+d^2. This is simply false(consider the case where a = 3, b = 1, c = 2 and d = 2).