Explore BrainMass

Explore BrainMass

    Edge connectivity

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    The edge connectivity of an undirected graph is the minimum number <i>k</i> of edges that must be removed to disconnect the graph. For example, the edge connectivity of a tree is 1, and the edge connectivity of a cyclic chain of vertices is 2. Show how the edge connectivity of an undirected graph G = (V, E) can be determined by running a maximum-flow algorithm on at most |V| flow networks, each having O(V) vertices and O(E) edges.

    © BrainMass Inc. brainmass.com November 24, 2021, 12:08 pm ad1c9bdddf

    Solution Preview

    Please see the attached file.

    Solution: (note: != means "not equal to"; )

    Construct a directed graph G' from G by replacing each edge {u, v} in G by two directed edges (u, v) and (v, u) in G'. Let g(u,v) be the maximum flow value from u to v through G' with all edge capacities
    equal to one. Pick an arbitrary node u ...

    Solution Summary

    Edge connectivity is emphasized.