Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2014:journals:maggie:home [2014/04/01 22:53] – [7.5 A First Application: The Bipartite Matching Problem] weatherlym | courses:cs211:winter2014:journals:maggie:home [2014/04/01 23:11] (current) – [7.6 Disjoint Paths in Directed and Undirected Graphs] weatherlym | ||
|---|---|---|---|
| Line 471: | Line 471: | ||
| ====== 7.6 Disjoint Paths in Directed and Undirected Graphs ====== | ====== 7.6 Disjoint Paths in Directed and Undirected Graphs ====== | ||
| + | * We say that a set of paths is edge-disjoint if no two paths share an edge, | ||
| + | * Given a directed graph G = (V, E) with two distinguished nodes s, t in V, the Directed Edge-Disjoint Paths Problem is to find the maximum number of edge-disjoint s-t paths in G | ||
| + | * The Undirected Edge-Disjoint Paths Problem is to find the maximum number of edge-disjoint s-t paths in an undirected graph G | ||
| + | * Both directed and the undirected versions of the problem can be solved using flows, starting with the directed problem, given the graph G = (V, E) we define a flow network in which s and t are the source and sink, and with capacity of 1 on each edge, suppose there are k edge-disjoint s-t paths, we can make each of these carry one unit of flow. If there are k edge-disjoint paths in a directed graph G from s to t, then the value of the maximum s-t flow in G is at least k | ||
| + | * If f is a 0-1 valued flow of value v, then the set of edges with flow value f(e) = 1 contains a set of v edge-disjoint paths | ||
| + | * There are k edge-disjoint paths in a directed graph G from s to t if and only if het value of the maximum value of an s-t flow in G is at least k | ||
| + | * The Ford-Fulkerson Algorithm can be used to find a maximum set of edge-disjoint s-t paths in a directed graph G in O(mn) time | ||
| + | * In every directed graph with nodes s and t, the maximum number of edge-disjoint s-t paths is equal to the number of edges whose removal separates s from t | ||
| + | * There are k edge-disjoint paths in an undirected graph G from s to to if and only if the maximum value of an s-t flow in the directed version G' of G is at least k. The Ford-Fulkerson Algorithm can be used to find a maximum set of disjoint s-t paths in an undirected graph G in O(mn) time | ||
| + | * In every undirected graph with nodes s and t, the maximum umber of edge-disjoint s-t paths is equal to the minimum number of edges whose removal separates s from t. | ||
