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")
print "Enter the adjacency matrix"
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 adjacency matrix
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")
print "Enter the adjacency matrix"
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
        cost[i][j]=input()#Get the adjacency matrix
        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 adjacency matrix
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