Definition:Homomorphism (Graph Theory)
Jump to navigation
Jump to search
This page is about Homomorphism in the context of Graph Theory. For other uses, see Homomorphism.
This article is complete as far as it goes, but it could do with expansion. In particular: Extend the definition to digraphs and rename as appropriate. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding this information. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Expand}} from the code.If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page. |
Definition
Let $G = \struct {\map V G, \map E G}$ and $H = \struct {\map V H, \map E H}$ be graphs.
Let there exist a mapping $F: \map V G \to \map V H$ such that:
- for each edge $\set {u, v} \in \map E G$
- there exists an edge $\set {\map F u, \map F v} \in \map E H$.
Then $G$ and $H$ are homomorphic.
The mapping $F$ is called a homomorphism from $G$ to $H$.
Linguistic Note
The word homomorphism comes from the Greek morphe (μορφή) meaning form or structure, with the prefix homo- meaning similar.
Thus homomorphism means similar structure.
Sources
There are no source works cited for this page. Source citations are highly desirable, and mandatory for all definition pages. Definition pages whose content is wholly or partly unsourced are in danger of having such content deleted. To discuss this page in more detail, feel free to use the talk page. |