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)}. For example, the condensation of a strongly connected graph is the quotient graph where the strongly connected components form the blocks of the partition.[2]

References

  1. ↑ Sanders, Peter; Schulz, Christian (2013), "High quality graph partitioning", Graph partitioning and graph clustering, Contemp. Math. 588, Amer. Math. Soc., Providence, RI, pp. 1–17, doi:10.1090/conm/588/11700, MR 3074893.
  2. ↑ 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.
This article is issued from Wikipedia - version of the Monday, June 29, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.