4. (CS application: graph theory) This problem is based on an example in [ HP05
ID: 3120446 • Letter: 4
Question
4. (CS application: graph theory) This problem is based on an example in [ HP05 ]. Figure 2 shows a network in which the nodes A , B , C , and E are input nodes and node D an output node. For example, some type of liquid may enter the network a t nodes A , B , C , or E but ultimately leaves it at node D . There is a lot of redundancy in the network and we would like to eliminate the redundant arcs while still ensuring th at anything entering one of the input nodes can ultimately reach the output node. In the lang uage of graph theory, we are producing a spanning tree. To do this: (a) Set up the system of equations representing the network fl ow of the nodes and represent it as a matrix; this will be the A in A~x = ~ 0. To do so, for each node the sum of the input values should equal the sum of the output values. For example , the equation for node A is x 1 + x 4 = 0 Note that the system of equations will consist of seven variab les but only five equations. (b) Find the reduced row echelon form (RREF) of the matrix. (c) Eliminate from the network the arcs corresponding to the free variables; that is, keep the arcs corresponding to the pivot variables. Draw the final net work with the redundant arcs eliminated. Note that the directions of the arcs matters when constructin g the system of equations, but don’t matter in the final network since we assume that whateve r is flowing through the network can flow in either direction of an arc
X2(C X3 x, Xs X1 X4 D E B AExplanation / Answer
Equations are
@Node A: x1+x4=0;
@Node B: X5-x1-x2=0;
@Node C: x2+x3-x6=0;
@Node D: -x3-x7=0;
@Node E: x6+x7-x4-x5=0;
Its matrix form is;
1 0 0 1 0 0 0 0
-1 -1 0 0 1 0 0 0
0 1 1 0 0 -1 0 0
0 0 -1 0 0 0 -1 0
0 0 0 -1 -1 1 1 0
Its reduced echelon form is:
1 0 0 1 0 0 0 0
0 1 0 -1 -1 0 0 0
0 0 1 1 1 -1 0 0
0 0 0 1 1 -1 -1 0
0 0 0 0 0 0 0 0
Pivot arcs are;
x1,x2,x3,x4;
free arcs are:
x5,x6,x7;
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.