Graphs and networks

Five wires join four points. Watch current circle round each loop while every junction stays in balance.

A small network

A graph is a set of points, the nodes, joined by lines, the edges. The picture has 4 nodes and 5 edges. Think of the edges as wires, pipes or roads, and the nodes as the junctions where they meet.

Each edge gets an arrow, chosen once and never changed. The arrow does not say which way anything flows. It only fixes a sign: a flow along the arrow counts as positive, and a flow against it as negative. The first loop in the picture runs against the arrow of edge 3, so edge 3 gets $-1$.

The incidence matrix

Write the graph as a matrix with one row per edge and one column per node. In each row, put $-1$ in the column of the node the edge leaves, $+1$ in the column of the node it enters, and 0 elsewhere. This is the incidence matrix:

Row 1 is edge 1, from node 1 to node 2; row 5 is edge 5, from node 3 to node 4. With $m=5$ edges and $n=4$ nodes, $\mathbf{A}$ is $5\times4$.

Potentials in, differences out

Give each node a number $x_q$, its potential: a voltage in a circuit, a pressure in pipes, a height in a landscape. The vector $\mathbf{x}$ has one entry per node, so it is an input of $\mathbf{A}$. Each row of $\mathbf{A}\mathbf{x}$ is the potential at the head of an edge minus the potential at its tail:

With potentials $\mathbf{x}=(0,1,3,4)$ the differences are $(1,2,3,4,1)$.

What does $\mathbf{A}$ erase? Only differences reach the output, so raising every potential by the same amount changes nothing. The null space is the line of $(1,1,1,1)$: equal potentials, no differences, nothing flows. For a graph in one connected piece, that is the whole null space, so $\dim N(\mathbf{A})=1$ and the rank is $r=n-1=3$.

Loops

Now put a current $y_k$ on each edge, positive along its arrow. The vector $\mathbf{y}$ has one entry per edge, so it lives on the output side of $\mathbf{A}$.

Multiply by the transpose. Column $q$ of $\mathbf{A}$ has $+1$ for the edges that enter node $q$ and $-1$ for those that leave it, so entry $q$ of $\mathbf{A}^\top\mathbf{y}$ is the current flowing into node $q$ minus the current flowing out. Kirchhoff’s current law says that, with nothing fed in from outside, these are equal at every node:

So the currents that can flow on their own are exactly the left null space $N(\mathbf{A}^\top)$, from The four fundamental subspaces. Its dimension is $m-r=5-3=2$, and the two loop currents of the picture are a basis: $(1,1,-1,0,0)$ round nodes 1, 2, 3, and $(0,0,1,-1,1)$ round nodes 1, 3, 4. Every current that balances at every node is a mix of these two loops.

The same vectors carry the other law. Read $(1,1,-1,0,0)$ as weights on the rows: row 1 plus row 2 minus row 3 is the zero row. So for any potentials, the differences round that loop add up to zero: here $1+2-3=0$. That is Kirchhoff’s voltage law. It is the right angle of the four subspaces page: a left null vector is perpendicular to every output $\mathbf{A}\mathbf{x}$.

Counting

Put the two dimensions together. The null space gives $r=n-1$, and the loops are $m-r$ of them:

Rearranged, this is Euler’s count for a connected graph:

Here $4-5+2=1$. Add a sixth edge and you add one loop; add a node with one edge to reach it and you add no loop.

A resistor network

Make every edge a resistor. Its conductance $g_k$ is one over its resistance, in siemens, and the matrix $\mathbf{G}=\mathrm{diag}(g_1,\dots,g_5)$ holds them on its diagonal.

Current flows from high potential to low, and Ohm’s law says how much: conductance times the drop. Measured along the edge arrows, the drop is tail minus head, which is $-\mathbf{A}\mathbf{x}$. So on this page

Now feed currents in from outside, $b_q$ amperes into node $q$. At each node, what flows out along the edges equals what is fed in. Flow out is $-\mathbf{A}^\top\mathbf{y}$, so $-\mathbf{A}^\top\mathbf{y}=\mathbf{b}$, and with Ohm’s law:

The matrix $\mathbf{K}=\mathbf{A}^\top\mathbf{G}\mathbf{A}$ is $n\times n$, one row per node. It has the same null space as $\mathbf{A}$: raising every potential changes no current. So fix one potential first, which an engineer calls grounding a node: set its potential to 0, and drop its row and column.

With every resistor 1 Ω, $\mathbf{G}=\mathbf{I}$ and $\mathbf{K}=\mathbf{A}^\top\mathbf{A}$:

Each diagonal entry counts the edges at a node, and each $-1$ marks a pair of nodes joined by an edge.

Worked example

Feed 1 A into node 1 and take it out at node 4, which is grounded: $x_4=0$. So $\mathbf{b}=(1,0,0)$ for nodes 1 to 3. Drop row and column 4 of $\mathbf{K}$:

The solution is $x_1=0.625$, $x_2=0.5$ and $x_3=0.375$ volts. The currents along the arrows are then

Check each node:

• Node 1: edges 1, 3 and 4 leave it, carrying $0.125+0.25+0.625=1$ A, the current fed in.
• Node 2: 0.125 A arrives on edge 1 and leaves on edge 2.
• Node 3: $0.125+0.25=0.375$ A arrives on edges 2 and 3 and leaves on edge 5.
• Node 4: $0.625+0.375=1$ A arrives, and leaves through the ground.

Node 1 sits at 0.625 V while 1 A flows to node 4, so the network behaves like a single resistor of $0.625\,\Omega$ between those two nodes. Most of the current, 0.625 A, takes the direct edge 4.

Predict before you check: by which edge does most current leave node 1? Edge 4, the direct one.

Where you’ll meet this

Circuit simulators. A simulator reads a list of components and the nodes they join, builds $\mathbf{A}^\top\mathbf{G}\mathbf{A}$ from it, grounds one node and solves for every potential. This is called nodal analysis, and it is the matrix of this page, built from a list instead of by hand.

Pipes, roads and power grids. Water in pipes, cars on roads and power on a grid obey the same two laws: what enters a junction leaves it, and a flow is driven by a difference in pressure, demand or voltage. The same matrix appears with new names for $\mathbf{x}$ and $\mathbf{y}$.

Grouping points. With unit conductances, $\mathbf{A}^\top\mathbf{A}$ is called the graph Laplacian. Methods that sort the members of a network into tightly linked groups, such as communities of friends, start from it.

Reference card