Connected Graphs

tutorial and example
tutorial and example

What is connected graph?

A connected graph is a graph in which there is an edge between every pair of vertices. It means, we can travel from any point to any other point in the graph.

What is disconnected graph?

A graph G is said to be disconnected if there is no edge between the two vertices or we can say that a graph which is not connected is said to be disconnected.

NOTE: In an undirected graph G, the vertices u and v are said to be connected when there is a path between vertex u and vertex v. otherwise, they are called disconnected graphs.

Strongly connected graph: When a graph contains a directed path from u to v and a directed path from v to u then this graph is called strongly connected graph.

Weekly connected graph: When we replace all the directed edges of a graph with undirected edges, it produces a connected graph. This connected graph is called weekly connected graph.

For example:

1. This graph is said to be connected because it is possible to travel from any vertex to any other vertex in the graph.

2. In this graph, travelling from one vertex to other is not possible because all the vertex are not connected together therefore this is disconnected graph.

Super connected graph: If every minimum vertex-cut isolates a vertex, this type of graph is called super-connected or super-k graph.

Hyper connected graph: If the deletion of each minimum vertex-cut creates exactly two components, one of which is an isolated vertex, this type of graph is called hyper-connected or hyper-k graph.

Semi-hyper-connected: If any minimum vertex cut separates the graph into exactly two components, this type of graph is called semi-hyper-connected or semi-hyper-k graph.