{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Chapter8 - Graph Theory"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex8.1 Pg 193"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"given a graph with 6 nodes viz. node1,node2....node6\n",
"The adjacency matrix for A is : \n",
"[[0 1 0 1 1 0]\n",
" [1 0 1 0 1 0]\n",
" [0 1 0 0 0 1]\n",
" [1 0 0 0 0 0]\n",
" [1 1 0 0 0 0]\n",
" [0 0 1 0 0 0]]\n",
"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\n",
"The adjacency matrix for B is : \n",
"[[0 0 0 1 1 0]\n",
" [0 0 0 0 1 1]\n",
" [0 0 0 0 0 0]\n",
" [1 0 0 0 0 0]\n",
" [1 1 0 0 0 0]\n",
" [0 1 0 0 0 0]]\n",
"sequence B is not a path since there is no edge from node2 to node6 is used twice\n",
"sequence C is a trail since is no edge is used twice\n",
"The adjacency matrix for D is : \n",
"[[0 0 0 1 1 0]\n",
" [0 0 0 0 0 0]\n",
" [0 0 0 0 1 1]\n",
" [1 0 0 0 0 0]\n",
" [1 0 1 0 0 0]\n",
" [0 0 1 0 0 0]]\n",
"sequence D is a simple path from node4 to node6\n"
]
}
],
"source": [
"from numpy import mat\n",
"# refer to page 8.6\n",
"print 'given a graph with 6 nodes viz. node1,node2....node6'\n",
"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]])\n",
"print 'The adjacency matrix for A is : \\n',A\n",
"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'\n",
"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]])\n",
"print 'The adjacency matrix for B is : \\n',B\n",
"print 'sequence B is not a path since there is no edge from node2 to node6 is used twice'\n",
"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]])\n",
"print 'sequence C is a trail since is no edge is used twice'\n",
"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]])\n",
"print 'The adjacency matrix for D is : \\n',D\n",
"print 'sequence D is a simple path from node4 to node6'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ex8.2 Pg 200"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"to find:minimal spanning tree\n",
"the adjacency matrix for the weighted graph(nodeA,nodeB...nodeF) of 6 nodes is :\n",
"edges of the graph\n",
"deleting edges without disconnecting the graph until 5 edges remain\n",
"weight of the minimal spanning tree is : 24\n",
"another method of finding a minimal spanning tree is :\n",
"weight of the minimal spanning tree is : 24\n"
]
}
],
"source": [
"from numpy import int32,mat\n",
"print 'to find:minimal spanning tree'\n",
"print 'the adjacency matrix for the weighted graph(nodeA,nodeB...nodeF) of 6 nodes is :'\n",
"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]])\n",
"print 'edges of the graph'\n",
"AC=7# \n",
"AE=4#\n",
"AF=7#\n",
"BC=8#\n",
"BD=3#\n",
"BE=7#\n",
"BF=5#\n",
"CE=6#\n",
"DF=4#\n",
"M=[AC,AE,AF,BC,BD,BE,BF,CE,DF]# #set of all edges\n",
"V=int32(M)#\n",
"L=sorted(V, reverse = True) #edges sorted in decreasing order of their weights\n",
"print 'deleting edges without disconnecting the graph until 5 edges remain'\n",
"N=[BE,CE,AE,DF,BD]# #edges in minimum spanning tree\n",
"Sum=sum(N)#\n",
"print 'weight of the minimal spanning tree is : ',Sum\n",
"\n",
"\n",
"print 'another method of finding a minimal spanning tree is :'\n",
"K=sorted(V)#edges sorted in increasing order\n",
"N2=[BD,AE,DF,CE,AF]# #edges in minimum spanning tree\n",
"Sum2=sum(N2)#\n",
"print 'weight of the minimal spanning tree is : ',Sum2"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.9"
}
},
"nbformat": 4,
"nbformat_minor": 0
}