Parts of a graph that are linked together. Two vertices are in the same connected component if there is some path between them.

Many practical problems involve connected components:

For directed graphs, there are two definitions of connected components. A directed graph is weakly connected if it would be connected by ignoring the direction of edges, i.e., if all edges were replaced by undirected edges. A directed graph is strongly connected if there exists a (directed) path between every pair of vertices. Consider a city traffic network consisting of one-way and two-way streets. The network is strongly connected if it is possible to drive legally between every two intersections. The network is weakly connected if it is possible to drive, legally or illegally, between every two intersections. The network is disconnected if it's impossible to drive between some point and some other point.

Topology extends the notion of a connected component in an undirected graph (described above). The connected components of a topological space X are the maximal (by inclusion) connected subspaces of X.

Equivalently: Define an equivalence relation x~y ("x and y are connected") on points in X: x~y iff there is no partition X=A∪B into disjoint open subsets A,B for which x∈A and y∈B. The connected components of X are the equivalence classes of ~ (aka "X/~").

A related notion is path connected component; however, due to the difference between connectedness and path connectedness, the two concepts are not equivalent for general topological spaces.

Log in or registerto write something here or to contact authors.