Quotient graph

In graph theory, a quotient graph Q of a graph G is a graph whose vertices are blocks of a partition of the vertices of G and where block B is adjacent to block C if some vertex in B is adjacent to some vertex in C with respect to the edge set of G.[1] In other words, if G has edge set E and vertex set V and R is the equivalence relation induced by the partition, then the quotient graph has vertex set V/R and edge set {([u]R, [v]R) | (u, v) ∈ E(G)}.

Intuitively, this corresponds to "gluing together" (formally, "identifying") vertices and edges of the graph.

The simplest non-trivial quotient graph is one obtained by identifying two vertices (vertex identification); if the vertices are connected, this is called edge contraction.

[2] The result of one or more edge contractions in an undirected graph G is a quotient of G, in which the blocks are the connected components of the subgraph of G formed by the contracted edges.

[3] Given an n-vertex cubic graph G and a parameter k, the computational complexity of determining whether G can be obtained as a quotient of a planar graph with n + k vertices is NP-complete.

A directed graph (blue and black) and its condensation (yellow). The strongly connected components (subsets of blue vertices within each yellow vertex) form the blocks of a partition giving rise to the quotient.