graph theory In mathematics, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph theory), vertices'' ( ...

, 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 Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented i ...

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 category theory Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topolo ...

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), ''Categories'' (Aristotle) *Category (Kant) ...

of graphs. The category of graphs is concretizable – mapping a graph to its set of vertices makes it a

concrete category In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mod ...

– 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 (mathematics), 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 ...

''V''/''R'' of its vertex set ''V''. Further, there is a

graph homomorphism In the mathematics, mathematical field of graph theory, a graph homomorphism is a mapping between two graph (discrete mathematics), graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs tha ...

(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); if the vertices are connected, this is called

edge contraction In graph theory, an edge contraction is an Graph operations, operation that removes an edge from a Graph (discrete mathematics), graph while simultaneously merging the two Vertex (graph theory), vertices that it previously joined. Edge contractio ...

Special types of quotient

The

condensation Condensation is the change of the state of matter from the gas, gas phase into the liquid, 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 w ...

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 reachability, reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a Partition of a set ...

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 Cycle graph#Directed cycle graph, directed cycles. That is, it consists of Vertex (graph theory), vertices and edge (graph ...

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 In the mathematics, mathematical discipline of graph theory, a graph (discrete mathematics), graph is a covering graph of another graph if there is a covering map from the Vertex (graph theory), vertex set of to the vertex set of . A covering m ...

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

, given an -vertex

cubic graph In the mathematics, mathematical field of graph theory, a cubic graph is a Graph (discrete mathematics), graph in which all vertex (graph theory), vertices have degree (graph theory), degree three. In other words, a cubic graph is a 3-regula ...

''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 (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. I ...

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