connectivity of graph

Connectivity of graphs: 

Connectivity of graphs

Connectivity of a graph: 

A graph is said to be connected , if there is a path between any two vertices. Some graphs are “more connected” than others. Two numerical parameters :- edge connectivity & vertex connectivity are useful in measuring a graph’s connectedness. Connectivity of a graph

Edge connectivity: 

Edge connectivity

definition: 

λ( G ) = min{ k | k = | S |, G − S disconnected, S ⊆ E G } definition

Slide 5: 

The edge-connectivity λ( G ) of a connected graph G is the smallest number of edges whose removal disconnects G . When λ( G ) ≥ k , the graph G is said to be k -edge-connected.

Slide 6: 

The above graph G1 can be split up into two components by removing one of the edges bc or bd. G1 has edge-connectivity 1 . λ( G1 ) =1 a b c d

Slide 7: 

The above graph G2 can be disconnected by removing a single edge, cd G2 has edge-connectivity 1. λ( G2 ) =1 a b c d f e

Slide 8: 

The above graph G3 cannot be disconnected by removing a single edge, but the removal of two edges (such as ac and bc ) disconnects it . G3 has edge-connectivity 2. λ( G3 ) =2 a b e c d

Cut Set : 

A cut set of a connected graph G is a set S of edges with the following properties: The removal of all edges in S disconnects G . The removal of some (but not all) of edges in S does not disconnects G Cut set is also known as edge-cut Cut Set

-Or-: 

An edge- cut S of G consists of edges so that G − S is disconnected . -Or-

Slide 11: 

We can disconnect G by removing the three edges bd , be , and ce , but we cannot disconnect it by removing just two of these edges. So,{ bd , be, ce } is a cut set of the graph G . { df,eg } is another cut set { fh } is another cut set a b d c e g f h

bridge: 

Or cut-edge ( not edge-cut ) is an edge-cut consisting of a single edge. Or A bridge is a single edge whose removal disconnects a graph bridge

Slide 13: 

The above graph G can be split up into two components by removing one of the edges bc or bd . Therefore, edge bc or bd is a bridge a b c d

Relationship between cut-set & edge connectivity: 

λ( G ) = min{ k | k = | S |, G − S disconnected, S ⊆ E G } Where S is the cut set of graph G(V,E) Relationship between cut-set & edge connectivity

Theorem: 

“ If S is a cut set of the connected graph G, then G − S has two components” Proof . Let S = {e1, . . . , ek }. The graph G−{e1, . . . , ek−1} is connected (and so is G if k = 1) by condition #2. When we remove the edges from the connected graph, we get at most two components. Theorem

EXAMPLE: 

{ e1, e4} , {e6, e7} , {e1, e2, e3} , {e8} , {e3, e4, e5, e6} , {e2, e5, e7} , {e2, e5, e6} and {e2, e3, e4} are cut sets. EXAMPLE

Proposition : 

Let G be a graph. Then the edge connectivity λ( G ) is less than or equal to the minimum vertex degree δ min ( G ). Proof: Let v be a vertex of graph G , with degree k= δ min ( G). Then the deletion of the k edges that are incident on vertex v separates v from the other vertices of G Proposition

theorem: 

An edge e is a bridge of G iff e lies on no cycle on G Proof: By definition- A bridge is a single edge whose removal disconnects a graph. If it lies on a cycle, its removal will not disconnect the graph theorem

Vertex connectivity: 

Vertex connectivity

definition: 

k ( G ) = min{ k | k = | S |, G − S disconnected , S ⊆ VG } 0  (G)  n-1 Where n is the number of vertices of the graph. definition

Slide 21: 

The connectivity (or vertex connectivity) K ( G ) of a connected graph G is the minimum number of vertices whose removal disconnects G . When K ( G ) ≥ k , the graph is said to be k -connected (or k -vertex connected).

Slide 22: 

The above graph G can be disconnected by removal of single vertex (either b or c). The G has connectivity 1. T hat is G is 1-connected or simply connected . a b c d

Slide 23: 

The above graph G can be disconnected by removal of single vertex (either c or d). The G has connectivity 1 a b c d f e

Slide 24: 

The above G can be disconnected by removing just one vertex i.e., vertex c. The G has connectivity 1 a b e c d

Slide 25: 

The above G cannot be disconnected by removing a single vertex, but the removal of two non-adjacent vertices (such as b and c) disconnects it. The G has connectivity 2 a b c d

Vertex cut set: 

A vertex-cut set of a connected graph G is a set S of vertices with the following properties. the removal of all the vertices in S disconnects G. the removal of some (but not all) of vertices in S does not disconnects G. Vertex cut set

-or-: 

A vertex-cut in a graph G is a vertex set S such that G-S is disconnected. Also known as separating set. We also say that S separates the vertices u and v and it is a ( u, v ) -separating set , if u and v belong to different connected components of G−S. -or-

Slide 28: 

We can disconnects the graph by removing the two vertices b and e, but we cannot disconnect it by removing just one of these vertices. The vertex-cut set of G is {b, e}. a b d c e g f h

Cut-Vertex: 

A cut-vertex ( not vertex-cut ) is a single vertex whose removal disconnects a graph . Cut vertex is also known as cut point Cut-Vertex

Slide 30: 

The above graph G can be disconnected by removal of single vertex (either c or d ). The vertex c or d is a cut-vertex a b c d f e

Relationship between vertex -cut & connectivity: 

The ( vertex ) connectivity number k ( G ) of G is defined as k ( G ) = min{ k | k = | S |, G − S disconnected S ⊆ V G } . A graph G is k - connected , if k ( G ) ≥ k . In other words, • k ( G ) = 0, if G is disconnected, • k ( G ) = V G − 1, if G is a complete graph, and • otherwise k ( G ) equals the minimum size of a vertex cut of G . Relationship between vertex -cut & connectivity

theorem: 

The vertex v is a cut vertex of the connected graph G if and only if there exist two vertices u and w in the graph G such that (i) v ≠ u , v ≠ w and u ≠ w , but (ii) v is on every u – w path . theorem

proof: 

First, let us consider the case that v is a cut-vertex of G. Then, G − v is not connected and there are at least two components G1 = (V1,E1) and G2 = (V2,E2). We choose u ∈ V1 and w ∈ V2 . The u–w path is in G because it is connected. If v is not on this path, then the path is also in G − v . The same reasoning can be used for all the u–w paths in G. If v is in every u–w path, then the vertices u and w are not connected in G − v . proof

example: 

example a b e c d

block: 

A block is a connected graph which has no cut vertices. A block of a graph is a maximal sub graph with no cut vertices . block

Slide 37: 

GRAPH BLOCKS

Menger's theorem: 

Menger's theorem states that “If u and v are non-adjacent vertices in a graph G, then the maximum number of internally disjoint u-v paths equals the minimum number of vertices in a u-v separating set .” Menger's theorem

Proof by induction : 

Proof by induction Basis: m = 2. Inductive step: Assume true for all graphs of size  m Let U be a minimum u-v separating set. Clearly , the number of u-v disjoint paths is at most |U| = k.

Proof (cont): 

Proof (cont) We look at all minimum u-v separating sets. There are three cases Case 1: There is a u-v separating set U that contains a vertex that is adjacent to both u and v Case 2: There is u-v separating set W with a vertex not adjacent to u and a vertex not adjacent to v Case 3: For each min. u-v separating set S, either (every vertex in S is adjacent to u but not to v) or (every vertex in S is adjacent to v but not to u)

Case 1: 

Case 1 Consider G-{x }: It’s size is less than m U- {x} is a min. separating set for G-{x }. Since |U-{x}| = k -1, by the induction hypothesis, there are k-1 internally disjoint u-v paths in G-{ x} So in G, we have these paths plus u-x-v Done . G1 G2 U x u v

Case 2: 

Case 2 G1 G2 W Note: x and y can be the same vertex u v x y

Case 2: 

Case 2 W = {w1, …, wk } First let’s construct G(u) which contains all u- wi paths for all wi  W in G1 + W Make a new graph G’(u) by adding a new vertex v’ to G(u) and connecting it to all wi Construct G(v) and G’(v) similarly W w1 u v’ wk … G1

Case 2: 

Case 2 size G’(u) < m W is a min u-v’ seperating set of size k. By the ind. hyp ., there are k disjoint u-v’ paths. We take these paths and delete v’ from them. Call the resulting paths P1 With similar reasoning, we conclude that G’(v) has k disjoint v-u’ paths. Generate paths P2 in a similar fashion. Combine P1 and P2 using the vertices wi . We obtained k internally disjoint paths for G W w1 u v’ wk …

Case 3: 

Case 3 We have either the situation on the left or the symmetric case (where v is connected to all in S) G1 G2 S u v

Case 3: 

Case 3 Let P = { u,x,y , … , v} be a u-v geodesic in G Let e = ( x,y ) and consider G-e Claim: The size k’ of any minimum u-v separating set in G-e is also k. Clearly , k’  k-1. Suppose , for contradiction, that k’ = k-1 (i.e. the claim is false ). Let Z be a min u-v separating set in G-e Z + {x} is a min u-v separating set in G So all vertices in Z are adjacent to u (we are in case 3) Z + {y} is a min u-v separating set in G So y is adjacent to v

Case 3 (cont): 

Case 3 (cont) G-{e} has a min. u-v separating set of size k. By ind. hyp . It has k internally disjoint u-v paths. So does G!

Slide 48: 

The edge-connectivity version of Menger's theorem is as follows: Let G be a finite undirected graph and x and y two distinct vertices. Then the theorem states that the size of the minimum edge cut for x and y is equal to the maximum number of pairwise edge-independent paths from x to y . The vertex-connectivity statement of Menger's theorem is as follows: Let G be a finite undirected graph and x and y two nonadjacent vertices. Then the theorem states that the size of the minimum vertex cut for x and y is equal to the maximum number of pairwise vertex-independent paths from x to y .

application: 

Network survivability The connectivity measures K ( G ) and λ( G ) are used in a quantified model of network survivability, which is the capacity of a network to retain connections among its nodes after some edges or nodes are removed application

And note one more thing…: 

For every connected graph, K( G ) ≤ λ( G ) ≤ δ min ( G) And note one more thing…

Slide 51: 

Thank you for your support…. SHAMEER P H DEPT OF FUTURES STUDIES KERALA UNIVERSITY phshameer@gmail.com