Computer Science - Graphs

Question

I've been given an adjacency matrix and asked to state whether the corresponding graph is undirected or not.

How do we say whether a graph is undirected or not simply looking at its adjacency matrix.

Answer 1

Prior knowledge

1. Adjacent nodes in the graph means any pair of nodes that are connected.
2. An undirectional graph means the connection between any pair of adjacent nodes is bidirectional

Adjacency matrix represents all the possible pairs of nodes along with the information about the direction of the connection across each pair if any [1 means there is connection from the node representing row to the node representing column ]

e.g. A1 A2 A3

A1 0 0 1

A2 0 0 0

A3 1 0 0

The adjacent matrix above is symmetric , since the top triangle of the matrix( with the left diagonal as base) is a mirror image of the bottom triangle.. mathematically A1A2=A2A1, A1A3=A3A1 etc. This can be interpreted as when there is a connection from A1 to A2 then there is one from A2 to A1 and so on i.e. all the connections are bidirectional . This concludes that if we can prove that the adjacent matrix is symmetric, the graph behind that matrix has to be undirectional.

The linear algebra says that the transpose of a symmetric matrix is same as the matrix itself, This is quite intuitive, since transposing a matrix is just shifting the column and rows

e.g

A1 A2 A3

A1 0 0 1

A2 0 0 0

A3 1 0 0

||

transpose

||

A1 A2 A3

A1 0 0 1

A2 0 0 0

A3 1 0 0

Thus the final step is to calculate the transpose of the given adjacent matrix and compare it with the original one cell by cell. If the comparison is successful for all the cells then the graph behind matrix is undirectional.

I am sharing a piece of code from GEEKFORGEEK that implements it

Note: More compact codes can be written if, you are familiar with python/numpy

# Simple Python code for check a matrix is

# symmetric or not.

# Fills transpose of mat[N][N] in tr[N][N]

def transpose(mat, tr, N):

for i in range(N):

for j in range(N):

tr[i][j] = mat[j][i]

# Returns true if mat[N][N] is symmetric, else false

def isSymmetric(mat, N):

tr = [ [0 for j in range(len(mat[0])) ] for i in range(len(mat)) ]

transpose(mat, tr, N)

for i in range(N):

for j in range(N):

if (mat[i][j] != tr[i][j]):

return False

return True

# Driver code

mat = [ [ 1, 3, 5 ], [ 3, 2, 4 ], [ 5, 4, 1 ] ]

if (isSymmetric(mat, 3)):

print "Yes"

else:

print "No"

# This code is contributed by Sachin Bisht

Answer 2

per wikipedia

If the graph is undirected (i.e. all of its edges

are bidirectional), the adjacency matrix is symmetric.

That is, the matrix is equal to it's Transpose (rows and

columns switch places).

This makes sense, because if the links are bi-directional

then adjacent nodes will appear in the matrix..

ex. Node i and j are adjacent. Then 1's shall appear

in row i and column j AND row j and column i

For example, the matrix

1 2 3

2 4 5

3 5 6

is symmetric... because the transpose is

1 2 3

2 4 5

3 5 6

/*********** CODE STARTS HERE *******************/

class SymmetricMatrix

{

private int error_code;

SymmetricMatrix()

{

error_code=0;

}

public int GetErrorCode() { return(error_code); }

//returns true if the matrix is symmetric, false otherwise;

// sets error_code member to -1 and returns false if indexes do not match;

public boolean IsSymmetric( int A[][])

{

int N=A.length;

int M=A[0].length;

boolean boolReturn = true;

if (M==N)

{

error_code = 0;

for (int iLoop=0; iLoop<M; iLoop++)

{

for (int jLoop=0; jLoop<N; jLoop++)

{

if (A[iLoop][jLoop]!=A[jLoop][iLoop])

{

boolReturn=false;

break;

} //if elements match

} //jLoop

} //iLoop

} //if square matrix

else // not a square matrix : sets the error flag

{

error_code=-1;

boolReturn=false;

}

return(boolReturn);

}

public static void main(String args[])

{

int A[][] = { {1,2,3},

{2,4,5},

{3,5,7} //comment out one of these rows to raise the error code

};

SymmetricMatrix m = new SymmetricMatrix();

if (m.IsSymmetric(A))

{

System.out.println(" matrix is symmetric ");

}

else

{

if (m.GetErrorCode()==0)

{

System.out.println(" matrix is not symmetric ");

}

else

{

System.out.println(" invalid matrix size: must be square matrix !!");

}

}

}

}