{
"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