in Graph Theory edited by
4,144 views
28 votes
28 votes

Suppose $\begin{pmatrix}
0&1 &0&0&0&1 \\
1&0&1&0&0&0  \\
0&1&0&1&0&1  \\
0&0&1&0&1&0  \\
0&0&0&1&0&1  \\
1&0&1&0&1&0
\end{pmatrix}$

is the adjacency matrix of an undirected graph with six vertices: that is, the rows and columns are indexed by vertices of the graph, and an entry is $1$ if the corresponding vertices are connected by an edge and is $0$ otherwise; the same order of vertices is used for the rows and columns. Which of the graphs below has the above adjacency matrix?

 

                                     

  1. Only $(i)$
  2. Only $(ii)$
  3. Only $(iii)$
  4. Only $(iv)$ 
  5.  $(i)$ and $(ii)$
in Graph Theory edited by
4.1k views

4 Comments

Add each row of matrix by this you will get degree of that vertex so do it for each row then you will get degree sequence of given graph (3 3 2 2 2 2) with this degree sequence check the degree sequence of given option graph you will find

a degree sequence (3 3 2 2 2 2)

b degree sequence (3 3 2 2 2 2)

c. Degree sequence (3 3 3 3 2 2)

D.degree sequence (3  2 2 2 2 2)

C and .D option which will not match with given graph degree sequence

So option e is correct
3
3

@rajinder singh check your degree sequence for last graph. There are two nodes with degree 3.

1
1

Detailed Video Solution: TIFR CSE 2015 Adjacency Matrix

0
0

7 Answers

28 votes
28 votes
Best answer

Yes, Option (E) must be the right answer.


Number of edges in the graph:

Since the graphs are undirected, it can be observed that there will be two $1$'s in the adjacency matrix corresponding to each edge in the graph.

For example, suppose two there is an edge between nodes $A \  \& \ B$, then there will be $1$ in position $[A, B]$ & there will be a $1$ in position $[B,A]$ of the adjacency matrix.

That's why the given adjacency matrix is symmetric.


So the number of edges in the graph must be equal to half the number of $1$'s in the adjacency matrix.

Hence number of edges will be $7$ in the graph.

All the other graphs except (iii), have $7$ edges.So it is clear that the adjacency matrix does not represents graph (iii).

Isomorphism:

From the definition of Isomorphic graphs, it can be inferred that,

Isomorphic graphs must have same (adjacency matrix) representation.

Thus after eliminating graph (iii) we have to check for isomorphism among graphs (i), (ii) & (iv).

It can clearly be observed that graphs (ii) & (iv) are not isomorphic to each other.

It can also be observed that graph (i) & (ii) are isomorphic(Rotate graph (i) by $90$ degree left/right.

Graph (ii) is looking like a closed envelope in the figure, try to view it like an open envelope, like a trapezium over a rectangle.) 

So now it can be inferred that either the adjacency matrix is representing both graphs (i) & (ii) or it is only representing (iv).


Cycles of length 6 :

Now from the adjacency matrix it can be observed that there should be a cycle of length $6$ in the graph, since $[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 1] $ are all $1$'s in the matrix.(as $1$ at any position $[x, y]$ represents an edge between $x \ \& \ y$ in the graph).

& both graphs (i) & (ii) have cycles of length $6$, but graph (iv) does not has any cycle of length $6$, it has cycles of length $4 \ \& \ 5$ only.

Thus graph (iv) can not have the above adjacency matrix.

Hence the adjacency matrix represents graphs (i) & (ii).

edited by

4 Comments

@Anurag-Isomorphism doesn't say that the isomorphic graphs have same adjacency matrix. They will have similar but not always same adjacency matrix. However, if you have same adjacency matrix for two graphs then they are definitely isomorphic.

For two isomorphic graphs having adjacency matrix A1 and A2, they are similar and if these two graphs are isomorphic then there should exist a permutation matrix P such that

A2=PA1PT

Reference: https://www.youtube.com/watch?v=UCle3Smvh1s

3
3
edited by

I watched the whole video that you provided in above comment. After watching and understanding video, i agree with your thoughts. According to this video, two graphs are isomorphic if and only if there exists such alpha function(see shown in video). If you know the alpha function (means you know the corresponding mapping between vertices of those two graph)  then you can easily able to derive that required permutation matrix. Or if you know the permutation matrix and able to derive function alpha.

Reason of statement, that said by Ayush Upadhyaya sir (if you have same adjacency matrix for two graphs then they are definitely isomorphic) :-  In this case identity matrix will be that required permutation matrix. As permutation matrix exist so, alpha function will also exist. 

 

0
0
In the adjacency matrix, vertices of degree 3 are connected(i.e. there is a edge between them) but in graph (iv) it is not so. In that way also we can eliminate graph (iv)
0
0
But we are building the P and $P^T$ by looking at the structure of both the graphs. Isn’t there a more mathematical way to know P and its transpose?
0
0
10 votes
10 votes

Adjacency matrix represents the graph :

It can be seen that there are only 2 cycles of length 4 and 1 cycle of length 6.

iii) is eliminated as it has a cycle of length 3.

iv) is eliominated as it has a cycle of length 5.

i) and ii) are isomorphic because both have a cycle of length 4 and in that cycle 2 nodes are connected to 1 node each and those 2 nodes are connected using an edge..

So E) is the answer ...

2 Comments

nice explanation@vicky rix
0
0
Best answer. simple and elegant.
0
0
4 votes
4 votes
this question correspondence to the isomorphism topic, but when to choose hard way if u can do it in easy way. Almost everthing is given. the adajency matrix represents the graph. each row can give u the degree of each vertex. counting 1.

v1=2 v2=2 v3=3 v4=2 v5=2 v6=3.

u only have to search for  graph with the above degree. clearly option e.

don't know who upvoted this .
1 vote
1 vote

Using isomorphism and cycle finding will take a lot of time but an observation can save our precious time during exam.

Option 3 is straightforward out of consideration. Now we are left with 1,2 and 4.In the adjaceny matrix,we can see that vertex 3(row 3) and vertex 6(row 6) have degree=3.

Also,row 3 has entry in 6th column and row 6 has entry in 3rd column,that means the only degree 3 vertices present are directly connected.So option 4 is also ruled out.

Also 1 and 2 are clearly isomorphic.

Hence option E is absolutely correct.

Answer:

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