Jump to content

Quotient graph

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by J. Finkelstein (talk | contribs) at 20:06, 29 March 2015 (Adds brief definition of quotient graph.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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 any vertex in B is adjacent to any vertex in C with respect to the edge set of 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.