9-39 Grey Construction would like to determine the least expensive way of connec
ID: 394496 • Letter: 9
Question
9-39 Grey Construction would like to determine the least expensive way of connecting houses it is building with cable TV. It has identified 11 possible branches or routes that could be used to connect the houses. The cost in hundreds of dollars and the branches are summarized in the following table.
What is the least expensive way to run cable to the houses?
BRANCH
START NODE
END NODE
COST ($100s)
Branch 1
1
2
5
Branch 2
1
3
6
Branch 3
1
4
6
Branch 4
1
5
5
Branch 5
2
6
7
Branch 6
3
7
5
Branch 7
4
7
7
Branch 8
5
8
4
Branch 9
6
7
1
Branch 10
7
9
6
Branch 11
8
9
2
After reviewing cable and installation costs, Grey Construction would like to alter the costs for installing cable TV between its houses. The first branches need to be changed. The changes are summarized in the following table. What is the impact on total costs?
BRANCH
START NODE
END NODE
COST ($100s)
Branch 1
1
2
5
Branch 2
1
3
1
Branch 3
1
4
1
Branch 4
1
5
1
Branch 5
2
6
7
Branch 6
3
7
5
Branch 7
4
7
7
Branch 8
5
8
4
Branch 9
6
7
1
Branch 10
7
9
6
Branch 11
8
9
2
BRANCH
START NODE
END NODE
COST ($100s)
Branch 1
1
2
5
Branch 2
1
3
6
Branch 3
1
4
6
Branch 4
1
5
5
Branch 5
2
6
7
Branch 6
3
7
5
Branch 7
4
7
7
Branch 8
5
8
4
Branch 9
6
7
1
Branch 10
7
9
6
Branch 11
8
9
2
Explanation / Answer
The problem is about connecting each node with minimum cost. This is a problem on Minimal Spanning tree.The steps are provided below
Step1: Start from Node 1. Keep the node 1 as permanent and write the Branches generated from node 1 with their costs. Select the branch having least cost and add the ending node to the permanent set.
There are two branches having least cost 5 i.e. 1-2 and 1-5 I am selecting arbitrarily 1-2 and adding 2 to the permanent node
Step-2: After adding the new node add the branches connected to the new node to the branch list and select the least cost among all and add the node to the permanent list as shown above
Selecting1-5 as it is having least cost and add 5 to the permanent node
Repeat the above steps to find the minimum cost network
Step3:
Select 5-8 branch having least cost and add 8 to permanent node
Select 8-9 and add 9 to permanent node
As from 9, there is no node connected and it is the ending node try to select the least cost branch from remaining in the next step
Select1-3 randomly as it is having least cost and add 3 to permanent node
Select 3-7 and add 7 to permanent node
As 7 and 9 are already there in the permanent list ignore that branch and select1-4 from the list
Select6-7 as having the least cost 1
The total cost would be
1-2=5
1-3=6
1-4=6
1-5=5
3-7=5
5-8= 4
6-7=1
8-9=2
Total = 5+6+6+5+5+4+1+2=34($100s)
************************************************************************
Changed one
Only the cost has been decresed
So total cost would be
5+1+1+1+5+4+1+2=20
The solution remains same as the least cost values are to be taken into the solution
Please comment if any doubt
Rate me
thanks
Permanent set Branch Cost {1} 1-2 5 1-3 6 1-4 6 1-5 5Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.