Definition:Homomorphism (Graph Theory)

From ProofWiki
Jump to navigation Jump to search

This page is about Homomorphism in the context of Graph Theory. For other uses, see Homomorphism.



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