Connectivity is a basic concept of graph theory. It defines whether a graph is connected or disconnected. Without connectivity, it is not possible to traverse a graph from one vertex to another vertex.
• A graph is said to be connected graph if there is a path between every pair of vertex. From every vertex to any other vertex there must be some path to traverse. This is called the connectivity of a graph.
• A graph is said to be disconnected, if there exists multiple disconnected vertices and edges.
Graph connectivity theories are essential in network applications, routing transportation networks, network tolerance etc.
Example of connected Graph:
In the above example, it is possible to travel from one vertex to another vertex. Here, we can traverse from vertex B to H using the path B -> A -> D -> F -> E -> H. Hence it is a connected graph.
Example of disconnected Graph:
In the above example, it is not possible to traverse from vertex B to H because there is no path between them directly or indirectly. Hence, it is a disconnected graph.
Walk:
A walk can be defined as a sequence of edges and vertices of a graph. When we have a graph and traverse it, then that traverse will be known as a walk.
In a walk, there can be repeated edges and vertices.
The number of edges which is covered in a walk will be known as the Length of the walk.
There are two types of the walk, which are described as follows:
Open walk
Closed walk
For example: In this example, we have a graph, which is described as follows:
In the above graph, there can be many walks, but some of them are described as follows:
Trail:
A trail is a walk in which no edge is repeated. The vertices can be repeated.
Path:
A walk in which no vertices and edges are repeated is called a path.
So for a path, the following two points are important, which are described as follows:
Edges cannot be repeated
Vertex cannot be repeated
In the above graph, there is a path, which is described as follows:
Circuit:
A closed trial which contains at least three edges is called a circuit.
So for a circuit, the following two points are important, which are described as follows:
Edges cannot be repeated
Vertex can be repeated
In the above graph, there is a circuit, which is described as follows:
Cycle:
A cycle is a circuit in which no vertex is repeated other than the starting and ending vertices.
