In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, 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''. 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 .
More formally, a quotient graph is a
quotient object in the
category
Category, plural categories, may refer to:
Philosophy and general uses
*Categorization, categories in cognitive science, information science and generally
*Category of being
* ''Categories'' (Aristotle)
*Category (Kant)
*Categories (Peirce)
*C ...
of graphs. The category of graphs is
concretizable – mapping a graph to its set of vertices makes it a
concrete category
In mathematics, a concrete category is a category that is equipped with a faithful functor to the category of sets (or sometimes to another category, ''see Relative concreteness below''). This functor makes it possible to think of the objects of ...
– so its objects can be regarded as "sets with additional structure", and a quotient graph corresponds to the graph induced on the
quotient set
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
''V''/''R'' of its vertex set ''V''. Further, there is a
graph homomorphism
In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent verti ...
(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
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
In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex ide ...
); if the vertices are connected, this is called
edge contraction
In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex id ...
.
Special types of quotient
The
condensation
Condensation is the change of the state of matter from the gas phase into the liquid phase, and is the reverse of vaporization. The word most often refers to the water cycle. It can also be defined as the change in the state of water vapor to ...
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.
The result of one or more
edge contraction
In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex id ...
s 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
In the mathematical discipline of graph theory, a graph is a covering graph of another graph if there is a covering map from the vertex set of to the vertex set of . A covering map is a surjection and a local isomorphism: the neighbourhood of ...
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.
Computational complexity
It is
NP-complete, given an -vertex
cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.
A bicubic graph is a cubic bip ...
''G'' and a parameter , to determine whether ''G'' can be obtained as a quotient of a
planar graph with vertices.
[.]
References
{{reflist
Graph operations
Graph