Graph Theory Connectivity Graph Theory

What is connectivity in Graph theory?

The manner in which the graph is connected determines the possibility of traversing a graph from one vertex to another. One of the basic concepts of graph theory is connectivity. The graph is defined either as connected or disconnected by Connectivity. Based on edge or vertex, connectivity can be either edge connectivity or vertex connectivity

Define Connectivity

When a path exists between every pair of vertex, such a graph is a connected graph. Connectivity of the graph is the existence of a traverse path from every vertex to any other vertex. A graph is said to be disconnected if it has multiple disconnected vertices and edges.

Example 1

The below graph facilitates in travelling from one vertex to any other vertex. For instance, from vertex ‘a’ it is possible to traverse to vertex ‘e’ and the path used for the same is ‘a-b-e’.

Connectivity

Example 2

The following is a disconnected graph as there is no path between say for instance, vertex ‘a’ to vertex ‘f’ either directly or indirectly.

Connectivity

What is Cut Vertex in Graph Theory?

When a specific vertex is removed from the graph, it results in breaking the graph into two or more graphs. Such a vertex is known as Cut Vertex.

Note – Removal of a cut vertex results in a disconnected graph.

Number of cut vertices for a Graph ‘G’ is at the most (n–2).

Example

The vertices ‘e’ and ‘c’ are the cut vertices in the following graph.

Cut Vertex

The graph will be a disconnected graph either ‘e’ or ‘c’ is removed.

Cut Vertices with e

Cut Vertices without e

There is no path between vertex ‘c’ and vertex ‘h’, in the absence of ‘g’, therefore it is considered as a disconnected graph with cut vertex at ‘e’. One more cut vertex of the graph is ‘c’.

What is Cut Edge (Bridge) in Graph Theory?

When a specific edge is removed from the graph, it results in breaking the graph into two or more graphs. Such an edge is known as Cut Edge.

For a connected graph G, an edge ‘e’ ∈ G is considered as a cut edge if ‘G-e’ lets the graph into a disconnected graph.

Example

In the following graph, the cut edge is [(c, e)]

Cut Edge

The graphs results into a disconnected graph, by removing the edge (c, e).

Cut With Edge

Cut Without Edge

The above graph is broken into two graphs once the edge (c, e) is removed, resulting in a disconnected graph. Therefore the edge (c, e) is considered as the cut edge of the graph.

For instance, ‘G’ be a connected graph with ‘n’ vertices, then

  • When edge ‘e’ is not a part of any of the cycle in G, the cut edge e ∈ G.
  • The possible maximum number of cut edges is ‘n-1’.
  • When there is a cut edge, cut vertices also exist since at least one vertex of a cut edge is a cut vertex.
  • A cut edge may or may not exist when there is a cut vertex.

What is Cut Set of a Graph?

When certain number of edges is deleted from the graph, it results in making the graph disconnected. The edges that are deleted are termed as the Cut set of a graph.

For a connected graph ‘G’= (V, E), the subset E’ of E is considered as a cut set of G, when all the edges of E’ are deleted from G, enabling G to disconnect.

Example

The cut set for the following graph is E1 = {e1, e3, e5, e8}.

Cut Set of a Graph

Once the cut set is deleted, the graph appears as follows:

Cut Set of a Graph

The graph can be disconnected by using other cut sets such as

  • E3 = {e9} – Smallest cut set of the graph.
  • E4 = {e3, e4, e5}

What is Edge Connectivity?

Among all the possible cut sets, the number of edges in a smallest cut set is known as the Edge connectivity of G.

It is represented as λ(G).

For a connected graph G, the edge connectivity of G is the minimum number of edges which are removed for making ‘G’ disconnected.

If ‘G’ has a cut edge, then λ(G) is 1. (Edge connectivity of G.)

Example

The following connected graph can be made disconnected by deleting a minimum of two edges and hence the edge connectivity (λ(G)) is 2.

Edge Connectivity

The graph can be disconnected by removing the edges in four different ways:

Edge Connectivity

What is Vertex Connectivity?

Removal of the minimum number of vertices for making the graph disconnected or reducing to a trivial graph is known as Vertex Connectivity and is represented as K(G).

Example

The graph is made disconnected by removing two vertices ‘e’ and ‘i’.

Vertex Connectivity

If G has a cut vertex, then K(G) = 1.

Notation − For any connected graph G,

K(G) ≤ λ(G) ≤ δ(G)

Vertex connectivity (K(G)), edge connectivity (λ(G)), minimum number of degrees of G(δ(G)).

Example

Calculate λ(G) and K(G) for the following graph −

Vertex Connectivity Example

Solution

From the graph,

δ(G) = 3

K(G) ≤ λ(G) ≤ δ(G) = 3 (1)

K(G) ≥ 2 (2)

The graph G can be disconnected by deleting the edges {d, e} and {b, h},

Therefore,

λ(G) = 2

2 ≤ λ(G) ≤ δ(G) = 2 (3)

From (2) and (3), vertex connectivity K(G) = 2

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Graph Theory Topics