Independent Paths and Cut Sets in Graph Theory
undefined
Independent paths and
cut sets
Independent paths
Edge-independent
: two paths do not
share the same
edge
Vertex-independent
(node-independent):
two paths do not share the same
vertex
other than the starting and ending
vertices.
Sometimes, independent paths are also
called
disjoint paths
.
Connectivity
Edge connectivity
between a pair of
vertices: the number of
edge
-
independent paths between these
two vertices.
Vertex connectivity
between a pair
of vertices: the number of
vertex
-
independent paths between these
two vertices.
Cut set
(Vertex) cut set is a set of
vertices
whose
removal will disconnect a specified pair of
vertices.
Edge
cut set is a set of
edges
whose
removal will disconnect a specified pair of
vertices.
Minimum cut set is the smallest cut set
that will disconnect a specified pair of
vertices.
Menger’s theorem
If there is no cut set of size less
than n between a given pair of
vertices, then there are at least n
independent paths between the
same vertices.
The theorem applies both to edges
and to vertices.
Menger’s theorem
Menger’s theorem implies that the number of
vertex-independent paths must be greater than
or equal to the size of the minimum cut set.
On the other hand, if there are exactly n vertex-
independent paths, then one has (at least) to
remove a vertex from each path.
The size of the minimum cut set is not less than
the number of vertex-independent paths.
The size of the minimum cut set is equal to the
vertex connectivity.
Max-flow/min-cut theorem
Source
Sink
Max-flow/min-cut theorem
The edge version of Menger’s theorem
Imagine a network of water pipes.
Each edge has a maximum flow rate r.
What is the maximum flow rate from vertex A to
vertex B?
Suppose that there are exactly n edge-
independent paths between A and B.
Each edge-independent path can carry a flow
with rate r.
Thus, the maximum flow is at least nr.
Max-flow/min-cut theorem
Menger’s theorem implies that there is a cut set
of n edges between A and B.
As each edge can carry at most flow r, removing
the cut set reduce at most nr flow.
After the removal of the cut set, the network is
disconnected and the flow is 0.
This then implies that the maximum flow cannot
exceed nr.
The maximum flow is exactly nr, where n is the
number of edge-independent paths (the
minimum cut set).
Max-flow/min cut theorem
for weighted networks
In a weighted network, each edge is assigned a
weight (link capacity).
The maximum flow between a given pair of vertices
is equal to the sum of the weights on the edges of
the minimum edge cut set that separates the same
two vertices.
Start from the problem with integer weights.
Transform the weighted network into a multiedge
(unweighted) network by replacing an edge with
weight w by w edges.
General weights: allow r to 0 in the limiting case.
Independent paths and cut sets play a crucial role in graph theory, determining connectivity and flow rates in networks. Learn about edge-independent paths, vertex-independent paths, connectivity, cut sets, Menger's theorem, and the Max-flow/min-cut theorem, with practical examples and implications. Explore how these concepts shape network analysis and optimization strategies.
Uploaded on Sep 21, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Independent paths and cut sets
Independent paths Edge-independent: two paths do not share the same edge Vertex-independent (node-independent): two paths do not share the same vertex other than the starting and ending vertices. Sometimes, independent paths are also called disjoint paths.
Connectivity Edge connectivity between a pair of vertices: the number of edge- independent paths between these two vertices. Vertex connectivity between a pair of vertices: the number of vertex- independent paths between these two vertices.
Cut set (Vertex) cut set is a set of vertices whose removal will disconnect a specified pair of vertices. Edge cut set is a set of edges whose removal will disconnect a specified pair of vertices. Minimum cut set is the smallest cut set that will disconnect a specified pair of vertices.
Mengers theorem If there is no cut set of size less than n between a given pair of vertices, then there are at least n independent paths between the same vertices. The theorem applies both to edges and to vertices.
Mengers theorem Menger s theorem implies that the number of vertex-independent paths must be greater than or equal to the size of the minimum cut set. On the other hand, if there are exactly n vertex- independent paths, then one has (at least) to remove a vertex from each path. The size of the minimum cut set is not less than the number of vertex-independent paths. The size of the minimum cut set is equal to the vertex connectivity.
Max-flow/min-cut theorem Sink Source
Max-flow/min-cut theorem The edge version of Menger s theorem Imagine a network of water pipes. Each edge has a maximum flow rate r. What is the maximum flow rate from vertex A to vertex B? Suppose that there are exactly n edge- independent paths between A and B. Each edge-independent path can carry a flow with rate r. Thus, the maximum flow is at least nr.
Max-flow/min-cut theorem Menger s theorem implies that there is a cut set of n edges between A and B. As each edge can carry at most flow r, removing the cut set reduce at most nr flow. After the removal of the cut set, the network is disconnected and the flow is 0. This then implies that the maximum flow cannot exceed nr. The maximum flow is exactly nr, where n is the number of edge-independent paths (the minimum cut set).
Max-flow/min cut theorem for weighted networks In a weighted network, each edge is assigned a weight (link capacity). The maximum flow between a given pair of vertices is equal to the sum of the weights on the edges of the minimum edge cut set that separates the same two vertices. Start from the problem with integer weights. Transform the weighted network into a multiedge (unweighted) network by replacing an edge with weight w by w edges. General weights: allow r to 0 in the limiting case.
