Chapter9 - Directed Graphs

Ex9.1 Pg 233

In [2]:
from numpy import mat
A=mat([[0,0, 0, 1],[1, 0, 1, 1],[1, 0, 0, 1],[1, 0, 1, 0]])
print 'adjacency matrix of graph G is: \n',A
A2=A**2
A3=A**3
print 'the number of ones in A is equal to the number of edges  in the graph i.e 8'

adjacency matrix of graph G is: 
[[0 0 0 1]
 [1 0 1 1]
 [1 0 0 1]
 [1 0 1 0]]
the number of ones in A is equal to the number of edges  in the graph i.e 8

Ex9.2 Pg 234

In [3]:
from numpy import mat
A=mat([[0, 0, 0, 1],[1, 0, 1, 1],[1 ,0 ,0 ,1],[1, 0, 1, 0]])
print 'adjacency matrix of graph G is : \n',A
A4=A**4#
A3=A**3#
A2=A**2#
B4=A+A2+A3+A4#
B4=[4, 11, 7 ,7 ,0, 0, 0 ,0 ,3 ,7 ,4 ,4 ,4, 11, 7, 7]
for i in range(0,16):
    if(B4[i]!=0):
        B4[i]=1
print 'Replacing non zero entries of B4 with 1 ,we get path (reachability) matrix P is:\n',B4
print 'there are zero entries in P,therefore the graph is not strongly connected'

adjacency matrix of graph G is : 
[[0 0 0 1]
 [1 0 1 1]
 [1 0 0 1]
 [1 0 1 0]]
Replacing non zero entries of B4 with 1 ,we get path (reachability) matrix P is:
[1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
there are zero entries in P,therefore the graph is not strongly connected