Chapter8 - Graph Theory

Ex8.1 Pg 193

In [1]:
from numpy import mat
# refer to page 8.6
print 'given a graph with 6 nodes viz. node1,node2....node6'
A=mat([[0, 1, 0, 1 ,1 ,0],[1, 0, 1, 0, 1, 0],[0, 1, 0, 0, 0, 1],[1, 0, 0 ,0 ,0 ,0],[1 ,1, 0, 0, 0, 0],[0, 0, 1, 0 ,0 ,0]])
print 'The adjacency matrix for A is : \n',A
print 'sequence A is a path from node4 to node6# but it is not a trail since the edge from node1 to node2 is used twice'
B=mat([[0 ,0, 0, 1, 1, 0],[0, 0 ,0 ,0 ,1, 1],[0, 0, 0, 0 ,0, 0],[1, 0, 0 ,0 ,0,0],[1, 1, 0, 0, 0, 0],[0,1, 0 ,0, 0, 0]])
print 'The adjacency matrix for B is : \n',B
print 'sequence B is not a path since there is no edge from node2 to node6 is used twice'
C=mat([[0, 0, 0 ,1 ,1 ,0],[0, 0, 1, 0, 1, 0],[0, 1, 0, 0, 1, 0],[1, 0, 0, 0, 0, 0],[1, 1, 1, 0, 0, 1],[0, 0, 0, 0, 1, 0]])
print 'sequence C is a trail since is no edge is used twice'
D=mat([[0, 0 ,0 ,1, 1, 0],[0, 0, 0, 0, 0, 0],[0, 0 ,0 ,0, 1, 1],[1, 0, 0,0, 0, 0],[1, 0, 1, 0, 0, 0],[0, 0, 1 ,0 ,0 ,0]])
print 'The adjacency matrix for D is : \n',D
print 'sequence D is a simple path from node4 to node6'
given a graph with 6 nodes viz. node1,node2....node6
The adjacency matrix for A is : 
[[0 1 0 1 1 0]
 [1 0 1 0 1 0]
 [0 1 0 0 0 1]
 [1 0 0 0 0 0]
 [1 1 0 0 0 0]
 [0 0 1 0 0 0]]
sequence A is a path from node4 to node6# but it is not a trail since the edge from node1 to node2 is used twice
The adjacency matrix for B is : 
[[0 0 0 1 1 0]
 [0 0 0 0 1 1]
 [0 0 0 0 0 0]
 [1 0 0 0 0 0]
 [1 1 0 0 0 0]
 [0 1 0 0 0 0]]
sequence B is not a path since there is no edge from node2 to node6 is used twice
sequence C is a trail since is no edge is used twice
The adjacency matrix for D is : 
[[0 0 0 1 1 0]
 [0 0 0 0 0 0]
 [0 0 0 0 1 1]
 [1 0 0 0 0 0]
 [1 0 1 0 0 0]
 [0 0 1 0 0 0]]
sequence D is a simple path from node4 to node6

Ex8.2 Pg 200

In [1]:
from numpy import int32,mat
print 'to find:minimal spanning tree'
print 'the adjacency matrix for the weighted graph(nodeA,nodeB...nodeF) of 6 nodes is :'
K=mat([[0,0,7,0, 4, 7],[0, 0, 8, 3, 7 ,5],[7, 8, 0, 0, 6, 0],[0, 3 ,0 ,0, 0, 4],[4, 7 ,6 ,0 ,0 ,0],[7, 5, 0, 4, 0, 0]])
print 'edges of the graph'
AC=7#  
AE=4#
AF=7#
BC=8#
BD=3#
BE=7#
BF=5#
CE=6#
DF=4#
M=[AC,AE,AF,BC,BD,BE,BF,CE,DF]#  #set of all edges
V=int32(M)#
L=sorted(V, reverse = True) #edges sorted in decreasing order of their weights
print 'deleting edges without disconnecting the graph until 5 edges remain'
N=[BE,CE,AE,DF,BD]#  #edges in minimum spanning tree
Sum=sum(N)#
print 'weight of the minimal spanning tree is : ',Sum


print 'another method of finding a minimal spanning tree is :'
K=sorted(V)#edges sorted in increasing order
N2=[BD,AE,DF,CE,AF]#  #edges in minimum spanning tree
Sum2=sum(N2)#
print 'weight of the minimal spanning tree is : ',Sum2
to find:minimal spanning tree
the adjacency matrix for the weighted graph(nodeA,nodeB...nodeF) of 6 nodes is :
edges of the graph
deleting edges without disconnecting the graph until 5 edges remain
weight of the minimal spanning tree is :  24
another method of finding a minimal spanning tree is :
weight of the minimal spanning tree is :  24