The first equivalence you mention is called isomorphism. Use
The second is not entirely clear to me, but you probably mean homeomorphism.
It seems reasonable (but I have not proven it!) that two directed graphs would be homeomorphic if we obtain isomorphic graphs after repeatedly removing vertices that have one incoming and one outgoing edge, like vertex
2 below, and replacing them with a single edge (would be
1 -> 3 below).
To avoid obtaining multigraphs or self loops, the removal should only be done if vertices
3 are distinct and there is no edge
1 -> 3 already.
Here's an implementation of this for directed graphs (since that is what you have in your example):
out[g_, v_] := First@DeleteCases[VertexOutComponent[g, v], v]
in[g_, v_] := First@DeleteCases[VertexInComponent[g, v], v]
homeomorphicQ[g1_?DirectedGraphQ, g2_?DirectedGraphQ] :=