in Graph Theory recategorized by
1,203 views
7 votes
7 votes

                            

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

in Graph Theory recategorized by
1.2k views

3 Answers

5 votes
5 votes
Best answer

Yes they are isomorphic

  • They have the same number of vertices
  • They have the same number of edges.
  • They have corresponding vertices with the same in-degree and out-degree.

$x_5$ and $y_4$ have the same degree.

The graphs can be redrawn as follows:

  

edited by

1 comment

for a particular directed graph, 

Inout
x112
x221
x312
x421
x522

for the second graph

inout
y121
y212
y321
y422
y512

because of directed graph here should we just match the order of in-degree and out-degree sequence of vertices (whether they are the same or not)? 

0
0
1 vote
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
0 votes
0 votes
Yes.

 The given graph is isomorphism . If you shrink vertex y4 of  2nd graph then you got same graph which is 1st.

Related questions

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