Connectivity in graph theory refers to the degree to which the vertices (or nodes) of a graph are connected to each other. It is a fundamental concept that helps in understanding the structure and properties of graphs.
Problems
Several problems related to connectivity in graphs include:
S-t Connectivity Problem
Given two vertices s and t in a graph G, determine whether there is a path from s to t.
S-t Shortest Path Problem
Given two vertices s and t in a weighted graph G, find the shortest path from s to t.
- Breadth First Search (BFS) can be used for unweighted graphs.
Applications
- smallest number of hops in a communication network
- maze traversal
- etc
