Гомоморфизм графа

Гомоморфизм графа (Homomorphism of a graph) — преобразование графа, представляющее последовательность его элементарных гомоморфизмов. Гомоморфизмом является, в частности, каждый изоморфизм. Гомоморфизм может рассматриваться как функция

$\varphi : G \rightarrow G'$

такая, что если вершины $u$ и $v$ смежны в $G$, то вершины $\varphi(u)$ и $\varphi(v)$ смежны в $G'$. Говорят также, что $\varphi$ есть гомоморфизм графа $G$ на граф $G'$. Граф $G'$ называется гомоморфным образом графа $G$ и обозначается $\varphi G$.

Литература

• Харари Ф. Теория графов. — М.: Мир, 1973.