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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

\varphi : G \rightarrow G'

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

Литература

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