Jump to content

Quotient graph

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by AnomieBOT (talk | contribs) at 02:33, 30 March 2015 (Dating maintenance tags: {{Unreferenced}}). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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.