Problem
Breaking the Chain You're an administrator of a computer network. You want all computers in the network to be able to communicate with each other, and you also want to avoid a situation where one computer going offline breaks the communication path between other computers in the network. It's common to represent networks as graphs, with each node representing a computer and edges between nodes representing the connections between computers in the network. You're interested in how the diameter of a network graph relates to the level of vulnerability of that network. Assume that your network is represented by a graph G = (V. E), containing n nodes and m edges.
A. Suppose the diameter of the network is strictly greater than n/2, and let s and t denote the diametric nodes. Show that there must exist some node v, not equal to either s or t, such that deleting v from G destroys all paths from s to f. Hint: think about a BF'S tree rooted at s.
B. Give an algorithm to find such a node v. You may assume that you are given the nodes s and t, and that the distance between them is strictly greater than n/2. For full credit, your algorithm must run in O(m + n) time.
C. Briefly justify a good asymptotic bound on the runtime of your algorithm.
D. Suppose n 2 4 is even and the distance between the diametric nodes s and t is equal to n/2 (instead of strictly greater). Is there still always a node v not equal to s or t such that deleting " from G destroys all paths from s to t? If yes, provide a proof. If no, provide an example in which no such v exists (s and # should be clearly labeled; you may lose points if your example is needlessly large or confusing).