5
$\begingroup$

I am learning about Network Analysis in Linear Algebra and I need help figuring out how to get the equations from this graph:

The arrows represent how many particles are going in a given direction.

Network Graph

The back of the book tells me they are:

$$x_1 + x_2 = 20$$ $$x_3 + 20 = x_4$$ $$x_2 + x_3 = 20$$ $$x_1 + 10 = x_5$$ $$x_5 + 10 = x_4$$

From my understanding, if we look at first equation, there are twenty particles going to the $1$ and they can split in two directions. So if you add up $x_1$ and $x_2$, they should equal twenty as it is impossible to go higher than that.

Even if I am correctly analyzing the first equation, I don't understand the rest of the equations that the book gives. For example, how does $x_3 + 20 = x_4$? What do $x_3$ and $20$ have to do with $x_4$?

Any help would be appreciated. Thank you!

$\endgroup$
5
$\begingroup$

I rewrote the equations to make it more clear:

$$\begin{array}{rlcl} \text{(node)} & \sum\text{outgoing} &=& \sum\text{incoming} \\[6pt] \hline (1) & x_1 + x_2 &=& 20 \\ (2) & x_3 + 20 &=& x_4 \\ (3) & 10 + 10 &=& x_2 + x_3 \\ (4) & x_1 + 10 &=& x_5 \\ (5) & x_4 &=& 10 + x_5 \\ \end{array}$$

The numbers in parentheses on the left correspond to the nodes in your network. The left side of each equation is the sum of the outgoing arrows at that node. The right side of each equation is the sum of the incoming arrows at that node.

As Johanna noted in the other answer, this is known as Kirchoff's (current) law. It is used in circuit analysis in electrical engineering: the incoming current at a node is equal to the the outgoing current. It is also seen in graph theory when studying flows. In particular, nowhere-zero flows (where no arrows have a "$0$" for their value) are closely related to graph coloring.

$\endgroup$
  • 1
    $\begingroup$ Thank you very much! This makes so much more sense now. You and Johanna are amazing! $\endgroup$ – o.o Feb 1 '15 at 4:40
4
$\begingroup$

The equations are found using Kirchoff's law: the sum of the values going in has to equal the sum of the values going out at each vertex. For vertex $2$, you have $20$ and $x_3$ particles going out, so $20 +x_3$ has to equal what is going into the vertex, namely $x_4$. Hence that vertex gives you the equation $x_3 + 20 = x_4$. Then they do the exact same analysis to each vertex to get each of the equations. Does it make more sense now?

$\endgroup$
  • 1
    $\begingroup$ Thank you so much! Really easy now that you and Snowball explained it. It makes perfect sense. $\endgroup$ – o.o Feb 1 '15 at 4:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.