Graph Connectivity

Graph Connectivity

In this tutorial, We will learn about the term path, walk and cycle that used in the connectivity. The connectivity means how the graph vertices are connected to each other like Given a graph, can we reach from a source vertex s to target vertex t using the edges of the graph?

Walk in Graph

A walk in a graph is a sequence of vertices where any two consecutive vertices are by an edge. In a walk, it is allowed to take vertices multiple times. The length of the walk is the number of the edge in the walk.

Path in Graph

If all the vertices in a walk are distinct, except possibly the first and the last vertex, then it is called a

path.

Cycle in Graph

A path of length greater than two is called a cycle if the first and the last vertex are the same.

Loop in Graph

A loop in is an edge that connects a vertex to itself.

Multi-edge in Graph

Multiple edges(also called parallel edges) are two or more edges that are incident to the same two vertices

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.