diff options
Diffstat (limited to 'Elements_of_discrete_mathematics/Chapter5.ipynb')
| -rwxr-xr-x | Elements_of_discrete_mathematics/Chapter5.ipynb | 2242 |
1 files changed, 2242 insertions, 0 deletions
diff --git a/Elements_of_discrete_mathematics/Chapter5.ipynb b/Elements_of_discrete_mathematics/Chapter5.ipynb new file mode 100755 index 00000000..79b98a7c --- /dev/null +++ b/Elements_of_discrete_mathematics/Chapter5.ipynb @@ -0,0 +1,2242 @@ +{
+ "metadata": {
+ "name": "",
+ "signature": "sha256:ecb9bbda12d6fdb3e39aeaf2fe5ef561c8a8f84a2def1400dc3ed8df4da10809"
+ },
+ "nbformat": 3,
+ "nbformat_minor": 0,
+ "worksheets": [
+ {
+ "cells": [
+ {
+ "cell_type": "heading",
+ "level": 1,
+ "metadata": {},
+ "source": [
+ "5 Trees and cut sets"
+ ]
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 01:Page 263"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Problem of connecting 19 lamps to a single electric outlet by using extension cords each of which has four outlets\"\n",
+ "total_lamps=19#Total lamps to be connected to a single electric outlet\n",
+ "outlets=4#Number of outlets in each extension cord.\n",
+ "def calc(lamp,outlet):\n",
+ " return (lamp-1)/(outlets-1)#Since any such connection is a quaternary tree with the single outlet connected to the root of the tree\n",
+ "print \"Although there are many ways to connect the lights,\",calc(total_lamps,outlets),\"extension cords are always required.\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Problem of connecting 19 lamps to a single electric outlet by using extension cords each of which has four outlets\n",
+ "Although there are many ways to connect the lights, 6 extension cords are always required.\n"
+ ]
+ }
+ ],
+ "prompt_number": 1
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 02:Page 263"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"A hypothetical computer has an instruction which computes the sum of three numbers.\"\n",
+ "nodes=9#Number of leaf nodes in each regular ternary tree to compute the sum of nine numbers\n",
+ "num=3#An instruction adds only three numbers\n",
+ "def calc(node,num):\n",
+ " return (nodes-1)/(num-1)\n",
+ "print \"The addition instruction will be executed \",calc(nodes,num),\"times to find the sum of nine numbers\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "A hypothetical computer has an instruction which computes the sum of three numbers.\n",
+ "The addition instruction will be executed 4 times to find the sum of nine numbers\n"
+ ]
+ }
+ ],
+ "prompt_number": 2
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 03:Page 278"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Implementation of Kruskal's algorithm\"\n",
+ "n=input(\"Enter the number of nodes\")\n",
+ "print \"Enter the adjacency matrix\"\n",
+ "cost=[[\"\" for i in range(n+1)]for j in range(n+1)]#Matrix is declared\n",
+ "parent=[\"\" for i in range(n+1)]#List is declared\n",
+ "mincost=0#Initially mincost is zero\n",
+ "for i in range(1,n+1):\n",
+ " for j in range(1,n+1):#To include n, have used n+1\n",
+ " print \"Enter the input for\",i,j\n",
+ " cost[i][j]=input()#Gets input matrix\n",
+ " if cost[i][j]==0:\n",
+ " cost[i][j]=999#Max cost is assigned if there is no edge between the specified nodes\n",
+ "ne=1#Count of visited nodes\n",
+ "def find(i):\n",
+ " while parent[i]:\n",
+ " i=parent[i]\n",
+ " return i\n",
+ "def uni(i,j):\n",
+ " if i!=j:\n",
+ " parent[j]=i\n",
+ " return 1\n",
+ " return 0\n",
+ "\n",
+ "print \"\\nThe edges of the minimum cost spanning tree is\"\n",
+ "while ne<n:\n",
+ " min=999\n",
+ " for i in range(1,n+1):\n",
+ " for j in range(1,n+1):\n",
+ " if cost[i][j]<min:\n",
+ " min=cost[i][j]#If the new node has minimum value,takes the new value\n",
+ " global a\n",
+ " global v\n",
+ " global b\n",
+ " a=i\n",
+ " global u\n",
+ " u=i\n",
+ " b=j\n",
+ " v=j\n",
+ " u=find(u)\n",
+ " v=find(v)\n",
+ " if uni(u,v):\n",
+ " print \"\\nEdge\",ne,\"(\",a,\" ,\",b,\")=\",min\n",
+ " ne=ne+1\n",
+ " mincost=mincost+min\n",
+ " cost[a][b]=cost[b][a]=999\n",
+ "print \"\\nMinimum cost=\",mincost\n",
+ "\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Implementation of Kruskal's algorithm\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the number of nodes9\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the adjacency matrix\n",
+ "Enter the input for 1 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "5\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "2\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "2\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "2\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "9\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "3\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "9\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "6\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "7\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "6\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "5\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "5\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "5\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "5\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "5\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "8\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "2\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "3\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "7\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "8\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\n",
+ "The edges of the minimum cost spanning tree is\n",
+ "\n",
+ "Edge 1 ( 2 , 9 )= 1\n",
+ "\n",
+ "Edge 2 ( 6 , 8 )= 1\n",
+ "\n",
+ "Edge 3 ( 1 , 9 )= 2\n",
+ "\n",
+ "Edge 4 ( 2 , 4 )= 2\n",
+ "\n",
+ "Edge 5 ( 2 , 3 )= 4\n",
+ "\n",
+ "Edge 6 ( 6 , 9 )= 4\n",
+ "\n",
+ "Edge 7 ( 6 , 7 )= 5\n",
+ "\n",
+ "Edge 8 ( 5 , 6 )= 6\n",
+ "\n",
+ "Minimum cost= 25\n"
+ ]
+ }
+ ],
+ "prompt_number": 3
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 04:Page 280"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"PRIM'S ALGORITHM\"\n",
+ "n=input(\"Enter the number of nodes\")\n",
+ "print \"Enter the adjacency matrix\"\n",
+ "cost=[[\"\" for i in range(n+1)]for j in range(n+1)]#Matrix declaration\n",
+ "visited=[0 for i in range(n+1)]#List declaration\n",
+ "n1=n+1#For use in range()\n",
+ "for i in range(1,n+1):\n",
+ " for j in range(1,n+1):\n",
+ " print \"Enter the input for\",i,j\n",
+ " cost[i][j]=input()#Get the adjacency matrix\n",
+ " if(cost[i][j]==0):\n",
+ " cost[i][j]=999#If there is no edge between two nodes, assign high cost\n",
+ "visited[1]=1#First node is initially visited\n",
+ "ne=1#Variable for node counting\n",
+ "mincost=0#Initially mincost is zero\n",
+ "\n",
+ "print \"\\n\"\n",
+ "while ne<n:\n",
+ " min=999\n",
+ " for i in range(1,n):\n",
+ " for j in range(1,n+1):#Generates all nodes\n",
+ " if(cost[i][j]<min):\n",
+ " if(visited[i]!=0):\n",
+ " min=cost[i][j]#Changes value if the new node has less cost\n",
+ " global a\n",
+ " a=i\n",
+ " u=i\n",
+ " global b\n",
+ " b=j\n",
+ " global v\n",
+ " v=j\n",
+ " if(visited[v]==0 or visited[u]==0):\n",
+ " \n",
+ " print \"\\nedge\",ne,\":(\",a,\" \",b,\")\",\"cost\",min\n",
+ " ne=ne+1\n",
+ " mincost=mincost+min\n",
+ " visited[b]=1\n",
+ " cost[a][b]=cost[b][a]=999\n",
+ "print \"minimum cost=\",mincost\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "PRIM'S ALGORITHM\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the number of nodes7\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the adjacency matrix\n",
+ "Enter the input for 1 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "2\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "6\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "2\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "5\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "5\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "6\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "3\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "6\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "3\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "3\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "3\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "2\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "7\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "2\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "6\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "3\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "3\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "7\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\n",
+ "\n",
+ "\n",
+ "edge 1 :( 1 6 ) cost 1\n",
+ "\n",
+ "edge 2 :( 1 2 ) cost 2\n",
+ "\n",
+ "edge 3 :( 2 7 ) cost 1\n",
+ "\n",
+ "edge 4 :( 6 5 ) cost 2\n",
+ "\n",
+ "edge 5 :( 5 4 ) cost 3\n",
+ "\n",
+ "edge 6 :( 2 3 ) cost 5\n",
+ "minimum cost= 14\n"
+ ]
+ }
+ ],
+ "prompt_number": 4
+ }
+ ],
+ "metadata": {}
+ }
+ ]
+}
\ No newline at end of file |