graph theory In mathematics and computer science, 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 ...

, a branch of

mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, two graphs ''G'' and ''H'' are called homomorphically equivalent if there exists a graph homomorphism

f\colon G \to H

and a graph homomorphism

g\colon H \to G

. An example usage of this notion is that any two

core Core or cores may refer to: Science and technology * Core (anatomy), everything except the appendages * Core (laboratory), a highly specialized shared research resource * Core (manufacturing), used in casting and molding * Core (optical fiber ...

s of a graph are homomorphically equivalent. Homomorphic equivalence also comes up in the theory of

database In computing, a database is an organized collection of data or a type of data store based on the use of a database management system (DBMS), the software that interacts with end users, applications, and the database itself to capture and a ...

s. Given a

database schema The database schema is the structure of a database described in a formal language supported typically by a relational database management system (RDBMS). The term "wikt:schema, schema" refers to the organization of data as a blueprint of how the ...

, two instances ''I'' and ''J'' on it are called homomorphically equivalent if there exists an instance homomorphism

f\colon I\to J

and an instance homomorphism

g\colon J\to I

. Deciding whether two graphs are homomorphically equivalent is

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

. In fact for any

category Category, plural categories, may refer to: General uses *Classification, the general act of allocating things to classes/categories Philosophy * Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) * Category ( ...

''C'', one can define homomorphic equivalence. It is used in the theory of accessible categories, where "weak universality" is the best one can hope for in terms of injectivity classes; see Adamek and Rosicky, "Locally Presentable and Accessible Categories".

References

Graph theory Equivalence (mathematics) {{graph-stub