The Gateway to Computer Science Excellence
+3 votes
354 views

                            

Are the two digraphs shown in the above figure isomorphic? Justify your answer.

in Graph Theory by Veteran (105k points)
edited by | 354 views

2 Answers

+2 votes
Best answer

Yes they are isomorphic

They have same number of vertices

They have same number of edges.

They have corresponding vertices with same indegree and outdegree.

$x_5$ and $y_4$ have same degree

The graphs can be redrawn as follows:

  

by Active (1k points)
selected by
+1 vote
since , all conditions like

no if points , no of edges, no of in degree and out degree sequences , no of cycle length all are same still they are necessary and  but not sufficient condition so we cant say at this point

for this if we map each vertex as one to one correspondence of both the graphs then they are isomorphic to each other

i.e. f(x5)=y4  , f(x4)=y5, f(x1)=(y2), f(x2)=y2, f(x3)=y3 , these one to one correspondence is done on the basis of thier no of in degree and no of out degree , since all vertices of both graphs matched so its isomorphic graph
by Active (5.1k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,562 answers
195,730 comments
101,645 users