Given an undirected graph G = (V, E), its edge connectivity eta (G) is the least

Question

Given an undirected graph G = (V, E), its edge connectivity eta (G) is the least k such that there are k edges whose removal disconnects G. (eta (G) = 0 for graphs that are not already connected: eta (G) = 1 for trees.) Show how to compute eta (G) by solving at most |V| max-flow problems on capacitated networks with O (|V|) vertices and O (|E|) edges. (Note, capacitated networks are allowed to have antiparallel edges-in keeping with the definitions in lecture, and in contrast with the definitions for flow networks (which is the same thing as capacitated networks) in the CLRS textbook.)

Explanation / Answer

Consider the undirected graph G = (V,E) and A V , let (A) = {e E : e = {a, v} for some a A, v A}. And Let t be the edge connectivity number of G. We know that k = min AV |(A)|.

To know that k min nullAV |(A)|, observe that for each null A V , now if all edges are removed in G (A) from G, the graph becomes disconnected.

And k min nullAV |G (A)|, let M E, |M| = k, is the set of edges such that G’ = (V,EM) is disconnected.

Let n V and let A be the set of nodes reachable from n in G’ . Then G (A) M and thus min nullAV |G (A)| k. Thus it is sufficient to find a minimum size cut G (A) in G.

Since the size of a min n t cut equals the value of a maximum n t flow by using MAX FLOW MIN CUT THEOREM , By this we know that if we fix some nodes n V and solve the max n t flow problem for each t V , t is not equal to n, The capacity of min cut is found by all these iterations by using minimal cut and hence the connectivity number k of G.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.