Problem:
Consider a directed graph with distinct and non-negative edge lengths and a source vertex $ s $. Fix a destination vertex $ t $, and assume that the graph contains at least one $ s - t $ path. Which of the following statements are true? [Check all that apply.]
Solution:
(Option 1) There is a shortest $ s - t $ path with no repeated vertices (i.e., a "simple" or "loopless" such path).
This choice is correct - but it is not immediately obvious how can one claim this fact, especially so the problem statement does not imply the graph is finite (am I thinking too much?).
Denote the set of $ s - t $ path *lengths* be $ \mathbf{L} $. Now $ \mathbf{L} $ is a set of integer and therefore there is a minimum value $ m $ by Archimedean Principle. Therefore the set $ \{ p : p \in \mathbf{L} and length(p) = m \} $ is not empty and any path in the set is a shortest path.
Suppose the contrary that such a path has one or more loop, we can remove the loop. That cannot reduce the path length because that path is already shortest (i.e. every edge in the loop has to be 0 length). Therefore the path with one less loop must be also in the set, inductively the set must have a path without any loops.
(Option 2) The shortest (i.e., minimum-length) s-t path might have as many as n−1 edges, where n is the number of vertices.
This choice is correct, consider the graph that is simply a chain from $ s $ to $ t $, it must go through all vertices.
(Option 3) The shortest s-t path must include the minimum-length edge of G.
This is incorrect. Consider the graph
s - 10 -> t
s - 3 -> u
u - 8 -> t
The shortest path from $ s $ to $ t $ is the direct path, and it does not include the minimum length edge.
(Option 4) The shortest s-t path must exclude the maximum-length edge of G.
This is also incorrect. Consider the graph
s - 10 -> t
There is only one path and therefore the edge is also the maximum edge and cannot be excluded.
Consider a directed graph with distinct and non-negative edge lengths and a source vertex $ s $. Fix a destination vertex $ t $, and assume that the graph contains at least one $ s - t $ path. Which of the following statements are true? [Check all that apply.]
Solution:
(Option 1) There is a shortest $ s - t $ path with no repeated vertices (i.e., a "simple" or "loopless" such path).
This choice is correct - but it is not immediately obvious how can one claim this fact, especially so the problem statement does not imply the graph is finite (am I thinking too much?).
Denote the set of $ s - t $ path *lengths* be $ \mathbf{L} $. Now $ \mathbf{L} $ is a set of integer and therefore there is a minimum value $ m $ by Archimedean Principle. Therefore the set $ \{ p : p \in \mathbf{L} and length(p) = m \} $ is not empty and any path in the set is a shortest path.
Suppose the contrary that such a path has one or more loop, we can remove the loop. That cannot reduce the path length because that path is already shortest (i.e. every edge in the loop has to be 0 length). Therefore the path with one less loop must be also in the set, inductively the set must have a path without any loops.
(Option 2) The shortest (i.e., minimum-length) s-t path might have as many as n−1 edges, where n is the number of vertices.
This choice is correct, consider the graph that is simply a chain from $ s $ to $ t $, it must go through all vertices.
(Option 3) The shortest s-t path must include the minimum-length edge of G.
This is incorrect. Consider the graph
s - 10 -> t
s - 3 -> u
u - 8 -> t
The shortest path from $ s $ to $ t $ is the direct path, and it does not include the minimum length edge.
(Option 4) The shortest s-t path must exclude the maximum-length edge of G.
This is also incorrect. Consider the graph
s - 10 -> t
There is only one path and therefore the edge is also the maximum edge and cannot be excluded.
No comments:
Post a Comment