Solution
The edge connectivity of some graph  is the minimum number of edges over some minimum cut of  , where is some flow network in which  and  and  for each  .  for each . For all ,  and remains constant where  for each  .
The edge connectivity of a graph depends on the connectivity between individual nodes. If the number of edges over the minimum cut  where  and  is k, then there must be k paths between  and that must be broken. This is due to the fact that each edge has a capacity of one, and paths cannot “share edges”; otherwise, removing the shared edge would break multiple paths. More precisely, capacity constraint will delete some edge from path  in  . The next path to consider need not include  as  and  . Once the two nodes with the fewest distinct paths are found, the edge connectivity is found.
Every possible must be considered unless some minimum cut yields one edge. Therefore, at most  flow networks must be constructed, each with a unique .
26.2-10
Suppose that a flow network has symmetric edges, that is, if and only if  . Show that the Edmonds-Karp algorithm terminates after at most  iterations.
Solution
From the time becomes critical to the next time it becomes critical,  and  increases by at least 2. The maximum number augmentations is  , so iterations are possible.
Share with your friends: |
