The Gateway to Computer Science Excellence
+22 votes
960 views

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 by Boss (30.7k points)
edited by | 960 views
0
unable to see any graphs
+2
fixed now..
+2
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
+1

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

7 Answers

+25 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).

by Boss (14.3k points)
edited by
+2

@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: 

+7 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 ...

by Loyal (8k points)
0
+3 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 .
by Boss (16.1k points)
+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.

by Junior (961 points)
0 votes

Draw the graph directly from Adjacency Matrix.

 

The graph is isomorphic to i and iv

by Active (2.5k points)
0 votes
  • Given the adjacency matrix
  V1 V2 V3 V4 V5 V6 DEGREE
V1 0 1 0 0 0 1 2
V2 1 0 1 0 0 0 2
V3 0 1 0 1 0 1 3
V4 0 0 1 0 1 0 2
V5 0 0 0 1 0 1 2
V6 1 0 1 0 1 0 3

We get to know that the degree sequence of the graph is 2 2 2 2 3 3 but the degree sequence of the graph in (iii) is 2 2 3 3 3 3 which clearly does not match so we eliminate this option (iii).

For Graph 4, I begin to label vertices based on the information present in the adjacency matrix.

Soon, you'll get to know that you'll be unable to find a label for vertices in graph (iv).

  • V1 is a degree 2 vertex which is adjacent to a degree 2(v2) and degree 3 vertex(6).So, I label it in graph as follows.

  • Now Since V2 is adjacent to V1(degree 2) and V3(a degree 3), V3 must be as below.

  • Now, as per adjacency matrix, Vertex V3 is adjacent to V6(a degree 3) vertex, which is not possible in above figure. So, we are unable to get a labelling for this graph, so we eliminate this option too!!.

For, graphs (i) and (ii) I am easily able to find a labelling which matches my adjacency matrix.

Graph (1)

Graph 2

Yes, since here two graphs have the same adjacency matrix, they are isomorphic(converse not necessarily true always).So, the answer is option (E).

by Boss (29k points)
–3 votes

We can draw graph directly from Adjacency Matrix.

This Graph will be similar to graph 2.

Hence Answer is (b) only 2.

by Boss (41.2k points)
edited by
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
50,737 questions
57,258 answers
198,086 comments
104,735 users