4. Connectivity
4.1. Connectivity
4.2. The Menger Theorem and its consequences
4.3. Flows in a graph
4.4. The thoughness of a grpah
Vertex-cut and vertex-connectivity
Edge-cut and edge-connectivty
Whitney's connec
...
4. Connectivity
4.1. Connectivity
4.2. The Menger Theorem and its consequences
4.3. Flows in a graph
4.4. The thoughness of a grpah
Vertex-cut and vertex-connectivity
Edge-cut and edge-connectivty
Whitney's connectivity theorem: ((G) (G) ((G)
Further theorems for the relation of ((G) and ((G) for special
graphs
The value of a flow and the capacity of a cut
The Max-Flow-Min-Cut Theorem
A new proof for the Menger Theorem
The Whitney's characterization
Application (Reliable network)
Graph Theory 3 2
4.1. Connectivity
We recall the definitions connected, disconnected and component.
If G is connected and G − W is disconnected, where W is a set of
vertices, then we say that W separates G, or that W is a vertex-cut.
If in G − W two vertices s and t belong to different components then
W separates s from t.
A graph G is k-vertex-connected (k 2) if
either Kk+1
or it has at least k+2 vertices and no set of k – 1 vertex separate
G.
Graph Theory 3 3
A connected graph is also said to be 1-connected.
The maximal value of k for which a connected graph G is k-vertex connected is the vertex-connectivity of G, denoted by ((G). If G is
disconnected, we put ((G)=0.
The vertex-connectivity – ((G) – of a graph G is
the minimum cardinality of a vertex-cut if G is not complete, and
((G) = n – 1 if G = Kn for some positive integer n.
κ( G ) = min { W : W ⊂ V ( G ) and W is a vertex - cut}
The two definitions is equivalent.
If a graph G is k-vertex-connected then ((G) k.
Graph Theory 3 4
Every graph that is not complete has a vertex-cut: the set of all
vertices distinct from two nonadjacent vertices is a vertex-cut.2
Graph Theory 3 5
Examples-1:
A nontrivial graph has vertex-connectivity 0 iff it is disconnected.
A graph G has vertex-connectivity 1 iff G = K2 or G is connected
with cut-vertices.
((G) 2 iff G is nonseparable of order 3 or more.
Graph Theory 3 6
The edge-connectivity (G) is defined analogously:
An edge-cut in a graph G is a set X of edges of G such that G – X is
disconnected.
An edge-cut X is minimal if no proper subset of X is also an edgecut.
If X is a minimal edge-cut of a connected graph G, then G – X
contains exactly two components.
The edge-connectivity, ((G), of a graph G is the minimum
cardinality of an edge-cut of G if G is nontrivial, and ((K1) = 0.
A graph G is k-edge-connected (k 2) if it has at least two vertices
and no set of at most k – 1 edges separates G.
Graph Theory 3 7
Examples 2:
A graph G is 2-edge-connected if it is connected, has at least two
vertices and contains no bridge.
((G) = 0 iff G is disconnected or trivial.
((G) =1 iff G is connected and contains a bridge.
Examples 3:
It is often easy to determine the connectivity of a given graph. If
1 j n then
((Pj) = ((Pj) = 1 ((Cn) = (Cn) = 2
((Kn) = ((Kn) = n – 1 ((Kj, n) = (Kj, n) = j
Graph Theory 3 8
[Show More]
 V1-V2.png)
