# 5 Trees and cut sets¶

## Example 01:Page 263¶

In [1]:
print "Problem of connecting 19 lamps to a single electric outlet by using extension cords each of which has four outlets"
total_lamps=19#Total lamps to be connected to a single electric outlet
outlets=4#Number of outlets in each extension cord.
def calc(lamp,outlet):
return (lamp-1)/(outlets-1)#Since any such connection is a quaternary tree with the single outlet connected to the root of the tree
print "Although there are many ways to connect the lights,",calc(total_lamps,outlets),"extension cords are always required."

Problem of connecting 19 lamps to a single electric outlet by using extension cords each of which has four outlets
Although there are many ways to connect the lights, 6 extension cords are always required.


## Example 02:Page 263¶

In [2]:
print "A hypothetical computer has an instruction which computes the sum of three numbers."
nodes=9#Number of leaf nodes in each regular ternary tree to compute the sum of nine numbers
num=3#An instruction adds only three numbers
def calc(node,num):
return (nodes-1)/(num-1)
print "The addition instruction will be executed ",calc(nodes,num),"times to find the sum of nine numbers"

A hypothetical computer has an instruction which computes the sum of three numbers.
The addition instruction will be executed  4 times to find the sum of nine numbers


## Example 03:Page 278¶

In [3]:
print "Implementation of Kruskal's algorithm"
n=input("Enter the number of nodes")
cost=[["" for i in range(n+1)]for j in range(n+1)]#Matrix is declared
parent=["" for i in range(n+1)]#List is declared
mincost=0#Initially mincost is zero
for i in range(1,n+1):
for j in range(1,n+1):#To include n, have used n+1
print "Enter the input for",i,j
cost[i][j]=input()#Gets input matrix
if cost[i][j]==0:
cost[i][j]=999#Max cost is assigned if there is no edge between the specified nodes
ne=1#Count of visited nodes
def find(i):
while parent[i]:
i=parent[i]
return i
def uni(i,j):
if i!=j:
parent[j]=i
return 1
return 0

print "\nThe edges of the minimum cost spanning tree is"
while ne<n:
min=999
for i in range(1,n+1):
for j in range(1,n+1):
if cost[i][j]<min:
min=cost[i][j]#If the new node has minimum value,takes the new value
global a
global v
global b
a=i
global u
u=i
b=j
v=j
u=find(u)
v=find(v)
if uni(u,v):
print "\nEdge",ne,"(",a," ,",b,")=",min
ne=ne+1
mincost=mincost+min
cost[a][b]=cost[b][a]=999
print "\nMinimum cost=",mincost

Implementation of Kruskal's algorithm
Enter the number of nodes9
Enter the input for 1 1
0
Enter the input for 1 2
4
Enter the input for 1 3
0
Enter the input for 1 4
0
Enter the input for 1 5
0
Enter the input for 1 6
0
Enter the input for 1 7
0
Enter the input for 1 8
5
Enter the input for 1 9
2
Enter the input for 2 1
4
Enter the input for 2 2
0
Enter the input for 2 3
4
Enter the input for 2 4
2
Enter the input for 2 5
0
Enter the input for 2 6
0
Enter the input for 2 7
0
Enter the input for 2 8
0
Enter the input for 2 9
1
Enter the input for 3 1
0
Enter the input for 3 2
4
Enter the input for 3 3
0
Enter the input for 3 4
4
Enter the input for 3 5
0
Enter the input for 3 6
0
Enter the input for 3 7
0
Enter the input for 3 8
0
Enter the input for 3 9
0
Enter the input for 4 1
0
Enter the input for 4 2
2
Enter the input for 4 3
4
Enter the input for 4 4
0
Enter the input for 4 5
9
Enter the input for 4 6
0
Enter the input for 4 7
0
Enter the input for 4 8
0
Enter the input for 4 9
3
Enter the input for 5 1
0
Enter the input for 5 2
0
Enter the input for 5 3
0
Enter the input for 5 4
9
Enter the input for 5 5
0
Enter the input for 5 6
6
Enter the input for 5 7
0
Enter the input for 5 8
0
Enter the input for 5 9
7
Enter the input for 6 1
0
Enter the input for 6 2
0
Enter the input for 6 3
0
Enter the input for 6 4
0
Enter the input for 6 5
6
Enter the input for 6 6
0
Enter the input for 6 7
5
Enter the input for 6 8
1
Enter the input for 6 9
4
Enter the input for 7 1
0
Enter the input for 7 2
0
Enter the input for 7 3
0
Enter the input for 7 4
0
Enter the input for 7 5
0
Enter the input for 7 6
5
Enter the input for 7 7
0
Enter the input for 7 8
5
Enter the input for 7 9
0
Enter the input for 8 1
5
Enter the input for 8 2
0
Enter the input for 8 3
0
Enter the input for 8 4
0
Enter the input for 8 5
0
Enter the input for 8 6
1
Enter the input for 8 7
5
Enter the input for 8 8
0
Enter the input for 8 9
8
Enter the input for 9 1
2
Enter the input for 9 2
1
Enter the input for 9 3
0
Enter the input for 9 4
3
Enter the input for 9 5
7
Enter the input for 9 6
4
Enter the input for 9 7
0
Enter the input for 9 8
8
Enter the input for 9 9
0

The edges of the minimum cost spanning tree is

Edge 1 ( 2  , 9 )= 1

Edge 2 ( 6  , 8 )= 1

Edge 3 ( 1  , 9 )= 2

Edge 4 ( 2  , 4 )= 2

Edge 5 ( 2  , 3 )= 4

Edge 6 ( 6  , 9 )= 4

Edge 7 ( 6  , 7 )= 5

Edge 8 ( 5  , 6 )= 6

Minimum cost= 25


## Example 04:Page 280¶

In [4]:
print "PRIM'S ALGORITHM"
n=input("Enter the number of nodes")
cost=[["" for i in range(n+1)]for j in range(n+1)]#Matrix declaration
visited=[0 for i in range(n+1)]#List declaration
n1=n+1#For use in range()
for i in range(1,n+1):
for j in range(1,n+1):
print "Enter the input for",i,j
if(cost[i][j]==0):
cost[i][j]=999#If there is no edge between two nodes, assign high cost
visited[1]=1#First node is initially visited
ne=1#Variable for node counting
mincost=0#Initially mincost is zero

print "\n"
while ne<n:
min=999
for i in range(1,n):
for j in range(1,n+1):#Generates all nodes
if(cost[i][j]<min):
if(visited[i]!=0):
min=cost[i][j]#Changes value if the new node has less cost
global a
a=i
u=i
global b
b=j
global v
v=j
if(visited[v]==0 or visited[u]==0):

print "\nedge",ne,":(",a," ",b,")","cost",min
ne=ne+1
mincost=mincost+min
visited[b]=1
cost[a][b]=cost[b][a]=999
print "minimum cost=",mincost

PRIM'S ALGORITHM
Enter the number of nodes7
Enter the input for 1 1
0
Enter the input for 1 2
2
Enter the input for 1 3
0
Enter the input for 1 4
0
Enter the input for 1 5
0
Enter the input for 1 6
1
Enter the input for 1 7
6
Enter the input for 2 1
2
Enter the input for 2 2
0
Enter the input for 2 3
5
Enter the input for 2 4
0
Enter the input for 2 5
0
Enter the input for 2 6
0
Enter the input for 2 7
1
Enter the input for 3 1
0
Enter the input for 3 2
5
Enter the input for 3 3
0
Enter the input for 3 4
6
Enter the input for 3 5
0
Enter the input for 3 6
0
Enter the input for 3 7
3
Enter the input for 4 1
0
Enter the input for 4 2
0
Enter the input for 4 3
6
Enter the input for 4 4
0
Enter the input for 4 5
3
Enter the input for 4 6
0
Enter the input for 4 7
3
Enter the input for 5 1
0
Enter the input for 5 2
0
Enter the input for 5 3
0
Enter the input for 5 4
3
Enter the input for 5 5
0
Enter the input for 5 6
2
Enter the input for 5 7
7
Enter the input for 6 1
1
Enter the input for 6 2
0
Enter the input for 6 3
0
Enter the input for 6 4
0
Enter the input for 6 5
2
Enter the input for 6 6
0
Enter the input for 6 7
4
Enter the input for 7 1
6
Enter the input for 7 2
1
Enter the input for 7 3
3
Enter the input for 7 4
3
Enter the input for 7 5
7
Enter the input for 7 6
4
Enter the input for 7 7
0

edge 1 :( 1   6 ) cost 1

edge 2 :( 1   2 ) cost 2

edge 3 :( 2   7 ) cost 1

edge 4 :( 6   5 ) cost 2

edge 5 :( 5   4 ) cost 3

edge 6 :( 2   3 ) cost 5
minimum cost= 14