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 In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relatio ...

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) ...

of graphs. The category of graphs is

concretizable 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 t ...

– 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 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 ...

quotient map In topology and related areas of mathematics, the quotient space of a topological space under a given equivalence relation is a new topological space constructed by endowing the quotient set of the original topological space with the quotient ...

) 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); 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 ...

of a directed graph is the quotient graph where the

strongly connected component In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that ...

s form the blocks of the partition. This construction can be used to derive a

directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one v ...

from any directed graph. The result of one or more

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 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 In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...

, 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 bipa ...

''G'' and a parameter , to determine whether ''G'' can be obtained as a quotient of a

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

with vertices..

References

{{reflist Graph operations

Graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...