Cuts and Connectivity¶

Connected Component¶

Each connected part of a graph is called a connected component. Any graph with more than one component is called a disconnected graph. For example, in a forest, each tree is called a component, and the number of components in the forest is equal to the number of trees present. In the forest below, each component is shown with a different color.

Weakly Connected¶

If we replace the directed edges of a directed graph with undirected edges, and the resulting graph is connected, then we say the original graph (with directed edges) is weakly connected.

Strongly Connected¶

A directed graph is called strongly connected if for any two vertices u and v, there is a directed path from u to v and a directed path from v to u.

Algorithms for finding strongly connected components are used to solve \(2-SAT\) problems.

Strong Component¶

Strong components are the maximal strongly connected subgraphs of a graph.

Cut Vertex (Articulation Point)¶

A vertex is called a cut vertex if, after its removal from the graph, the number of its components increases.

Cut Edge (Bridge)¶

An edge is called a cut edge (or bridge) if its removal increases the number of connected components. An edge uv that is part of a cycle in a graph cannot be a cut edge, because after its removal, the two vertices u and v still have a path between them (through the rest of the cycle), so no new component is added to the graph.