Isomorphism of graphs or equivalance of graphs?

229 Views Asked by At

By definition of graph isomorphism, it is apparent that two isomorphic graphs must have the same number of vertices, the same number of edges and the same degree of vertices. Is the following two graphs isomorphic?enter image description hereenter image description here. These two are bipartite graphs, but i am not sure whether i should call them isomorphic. Or, can i say that these two graphs are equivalent, i.e., fig.I=fig.II ?

2

There are 2 best solutions below

0
On BEST ANSWER

These graphs are isomorphic; the bijection that exhibits the isomorphism is a reflection in the central horizontal axis.

If there is such a concept of equivalence of graphs distinct from isomorphism of graphs, I've never heard of it; Google also doesn't seem to know about it.

0
On

you have a simple graph, by definition: An isomorphism a simple graph G to is a simple graph H is a bijection $f: V(G) \rightarrow V(H)$ such that $ uv \in E(G)$ if and only if $f(u)f(v) \in E(H) $ then we say "G is isomorphic to H", written $ G \cong H$ Here you could give a direct bijection

$$ 1\rightarrow 5 $$ $$ 2\rightarrow 6 $$ $$ 3\rightarrow 3 $$ $$ 4\rightarrow 4 $$ $$ 5\rightarrow 1 $$ $$ 6\rightarrow 2 $$

This function is injective and surjective.

One other way you could start to analyse adjacency matrices. You will see that the applying row and columns permutation on A(G), you will get A(H), this also is a proof of the isomorphism.