Ungerichteter Graph/Isomorphismus/Definition

Isomorphismus von Graphen

Es seien ${}G=(V,E)$ und ${}H=(W,F)$ Graphen. Ein Graphhomomorphismus ${}\varphi \colon G\rightarrow H$ heißt Isomorphismus, wenn es einen Graphhomomorphismus

$\psi \colon H\longrightarrow G$

derart gibt, dass

${}\psi \circ \varphi =\operatorname {Id} _{V}\,$

und

${}\varphi \circ \psi =\operatorname {Id} _{W}\,$

gilt.