Problem:
This problem explores the relationship between two definitions about graph distances. In this problem, we consider only graphs that are undirected and connected. The diameter of a graph is the maximum, over all choices of vertices $ s $ and $ t $, of the shortest-path distance between $ s $ and $ t $. (Recall the shortest-path distance between $ s $ and $ t $ is the fewest number of edges in an $ s-t $ path.)
Next, for a vertex $ s $, let $ l(s) $ denote the maximum, over all vertices $ t $, of the shortest-path distance between $ s $ and $ t $. The radius of a graph is the minimum of $ l(s) $ over all choices of the vertex $ s $.
Which of the following inequalities always hold (i.e., in every undirected connected graph) for the radius $ r $ and the diameter $ d $? [Select all that apply.]
Solution
$ r \le d $ is obvious, $ d $ is maximum of all shortest paths and $ r $ is the minimum all longest shortest path with a fixed source.
What is not so obvious is $ r \ge \frac{d}{2} $. Suppose that is not true, then let $ S-T $ be the diameter path (i.e. the longest shortest path) and $ c $ (for center) stand for the $ s $ we chosen for $ r $.
Now $ c - S $ path is of length at most $ r $, and so is the $ c - T $ path, therefore the path $ S - c - T $ has length at most $ 2r $, and we know that this must be at least $ d $, therefore, we have $ r \ge \frac{d}{2} $.
This problem explores the relationship between two definitions about graph distances. In this problem, we consider only graphs that are undirected and connected. The diameter of a graph is the maximum, over all choices of vertices $ s $ and $ t $, of the shortest-path distance between $ s $ and $ t $. (Recall the shortest-path distance between $ s $ and $ t $ is the fewest number of edges in an $ s-t $ path.)
Next, for a vertex $ s $, let $ l(s) $ denote the maximum, over all vertices $ t $, of the shortest-path distance between $ s $ and $ t $. The radius of a graph is the minimum of $ l(s) $ over all choices of the vertex $ s $.
Which of the following inequalities always hold (i.e., in every undirected connected graph) for the radius $ r $ and the diameter $ d $? [Select all that apply.]
Solution
$ r \le d $ is obvious, $ d $ is maximum of all shortest paths and $ r $ is the minimum all longest shortest path with a fixed source.
What is not so obvious is $ r \ge \frac{d}{2} $. Suppose that is not true, then let $ S-T $ be the diameter path (i.e. the longest shortest path) and $ c $ (for center) stand for the $ s $ we chosen for $ r $.
Now $ c - S $ path is of length at most $ r $, and so is the $ c - T $ path, therefore the path $ S - c - T $ has length at most $ 2r $, and we know that this must be at least $ d $, therefore, we have $ r \ge \frac{d}{2} $.
No comments:
Post a Comment