Graph isomorphism

cosmos 11th November 2017 at 3:04pm

See Graph theory

A (graph) isomorphism is a mapping between vertices of two graphs G=(VG,EG)G=(V_G, E_G) and G=(VG,EG)G'=(V_G', E_G') (if(i)i \mapsto f(i) such that iVGi \in V_G and jVGj \in V_G') such that the edge (i,j)(i,j) is contained in the set of edges of GG, if and only if the edge (f(i),g(i))(f(i), g(i)) is contained in the set of edges of GG'. To graphs are isomorphic if there exists an isomorphism between them. They are then also called "topologically equivalent".

Graph homomorphism means there is only implication of edge from domain to codomain