graph-theory-3.pdf

Document Content and Description Below

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-connectiv... ty 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]

Last updated: 1 year ago

Preview 1 out of 21 pages