Question

4 Graph Application: Network Connectivity (Adapted from Problem 9, Chapter 3 of K&T) Think of a communications network as a connected, undi rected graph, where messages from one node s to another node t are sent along paths from s to t. Nodes can sometimes fail. If a node v fails then no messages can be sent along edges incident on v. A network is particularly vulnerable if failure of a single node v can cause two nodes, say s and t, to become disconnected. That is, when v and its incident edges are removed from the network, there is no path from s to t. We call such a node v a vulnerability. 1. Suppose that connected, undirected graph G contains two nodes s and t such that the shortest path between s and t is strictly greater than n/2. Show that G must contain a vulnerability 2. Give an algorithm that, given as input G and a node s such that there is some node t for which the distance between s and t is guaranteed to be greater than n/2, finds a vulnerability. Your algorithm should have running time O(m n)

Have the explaination please.

Answer 1

1.)The vulnerability of a graph is a determination that includes certain properties of the graph not to be damaged after the removal of a number of vertices or edges. One measure of vulnerability to vertex removal is neighbour-integrity.

We need to prove

         -> Let G(V, E) be a connected undirected graph with |V | = n. Assume that n is even. Suppose G has two nodes s and t such that every simple path between s and t has strictly greater than n/2 edges. Then G has a node w, which is different from s and t, such that deleting w from G destroys all the paths between s and t.

proof-> Consider any breadth-first spanning tree T of G with s as the root. In T, each node v of G has a level, which is the length of (i.e., number of edges in) the shortest path from s to v. Since every path between s and t has length at least ` = (n/2) + 1, node t occurs at a level ≥ `. Consider levels 1 through n/2. The total number of nodes in levels 1 through n/2 is at most n − 2 (since nodes s and t don’t appear in any of these levels). If each of these n/2 levels has 2 or more nodes, then total number of nodes in G will exceed n. Therefore, there must be a level in the range 1 through n/2 containing just one node, say w. Clearly, if we delete w, the resulting graph has no path between s and t.

2.)

In short,

Algorithm:-

a.) Construct a breadth-first search of G, starting with node s. For each level i, construct the list L[i] of the nodes at level i.

b.) Find a level j, where 1 ≤ j ≤ n/2, such that L[j] has only one node, say w. (The above proof shows that such a level must exist.)

c.). Output node w.

The correctness of the above algorithm follows from the proof of Lemma 1. For the running time, note that Step 1 can be done in O(m + n) time since it involves just a breadth-first search of G. Steps 2 and 3 take O(n) and O(1) time respectively. So, the algorithm runs in O(m + n) time.