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)}.
More formally, a quotient graph is a quotient object in the category of graphs. The category of graphs is concretizable – mapping a graph to its set of vertices makes it a concrete category – so its objects can be regarded as "sets with additional structure", and a quotient graph corresponds to the graph induced on the quotient set V/R of its vertex set V. Further, there is a graph homomorphism (a quotient map) from a graph to a quotient graph, sending each vertex or edge to the equivalence class that it belongs to. Intuitively, this corresponds to "gluing together" (formally, "identifying") vertices and edges of the graph.
Examples edit
A graph is trivially a quotient graph of itself (each block of the partition is a single vertex), and the graph consisting of a single point is the quotient graph of any non-empty graph (the partition consisting of a single block of all vertices). 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.
Special types of quotient edit
The condensation of a directed graph is the quotient graph where the strongly connected components form the blocks of the partition. This construction can be used to derive a directed acyclic graph from any directed graph.[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. However, for quotients more generally, the blocks of the partition giving rise to the quotient do not need to form connected subgraphs.
If G is a covering graph of another graph H, then H is a quotient graph of G. The blocks of the corresponding partition are the inverse images of the vertices of H under the covering map. However, covering maps have an additional requirement that is not true more generally of quotients, that the map be a local isomorphism.[3]
Computational complexity edit
It is NP-complete, given an n-vertex cubic graph G and a parameter k, to determine whether G can be obtained as a quotient of a planar graph with n + k vertices.[4]
References edit
- ^ Sanders, Peter; Schulz, Christian (2013), "High quality graph partitioning", Graph partitioning and graph clustering, Contemp. Math., vol. 588, Amer. Math. Soc., Providence, RI, pp. 1–17, doi:10.1090/conm/588/11700, MR 3074893.
- ^ Bloem, Roderick; Gabow, Harold N.; Somenzi, Fabio (January 2006), "An algorithm for strongly connected component analysis in n log n symbolic steps", Formal Methods in System Design, 28 (1): 37–56, doi:10.1007/s10703-006-4341-z, S2CID 11747844.
- ^ Gardiner, A. (1974), "Antipodal covering graphs", Journal of Combinatorial Theory, Series B, 16 (3): 255–273, doi:10.1016/0095-8956(74)90072-0, MR 0340090.
- ^ Faria, L.; de Figueiredo, C. M. H.; Mendonça, C. F. X. (2001), "Splitting number is NP-complete", Discrete Applied Mathematics, 108 (1–2): 65–83, doi:10.1016/S0166-218X(00)00220-1, MR 1804713.