Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Graph homomorphism
Summary
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 vertices.
Homomorphisms generalize various notions of graph colorings and allow the expression of an important class of constraint satisfaction problems, such as certain scheduling or frequency assignment problems.
The fact that homomorphisms can be composed leads to rich algebraic structures: a preorder on graphs, a distributive lattice, and a (one for undirected graphs and one for directed graphs).
The computational complexity of finding a homomorphism between given graphs is prohibitive in general, but a lot is known about special cases that are solvable in polynomial time. Boundaries between tractable and intractable cases have been an active area of research.
In this article, unless stated otherwise, graphs are finite, undirected graphs with loops allowed, but multiple edges (parallel edges) disallowed.
A graph homomorphism f from a graph to a graph , written
f : G → H
is a function from to that maps endpoints of each edge in to endpoints of an edge in . Formally, implies , for all pairs of vertices in .
If there exists any homomorphism from G to H, then G is said to be homomorphic to H or H-colorable. This is often denoted as just
G → H .
The above definition is extended to directed graphs. Then, for a homomorphism f : G → H, (f(u),f(v)) is an arc (directed edge) of H whenever (u,v) is an arc of G.
There is an injective homomorphism from G to H (i.e., one that never maps distinct vertices to one vertex) if and only if G is a subgraph of H.
If a homomorphism f : G → H is a bijection (a one-to-one correspondence between vertices of G and H) whose inverse function is also a graph homomorphism, then f is a graph isomorphism.
Covering maps are a special kind of homomorphisms that mirror the definition and many properties of covering maps in topology.
They are defined as surjective homomorphisms (i.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.