Take the 2-minute tour ×

I need to calculate resistance in an electrical grid.
Grid is a graph. Edges of a graph are resistors. How calculate resistance between any two vertexes for arbitrary graph?
I know Kirchoff law and Ohm law. I can calculate resistance between any points for given grid, but not for arbitrary. Is there programs to solve this problem?
Actually, my goal is to write algorithm that calculate resistance for arbitrary graph.
Any help is appreciated.

share|improve this question
Related: The “Nerd Sniping” problem. Generalizations? (arbitrary points in the infinite, uniform, rectangular array. –  dmckee Jan 8 '12 at 23:26
add comment

2 Answers

up vote 3 down vote accepted

You can connect a unit current source between these two vertices. Then you can solve the circuit using nodal analysis, in essence:

  • Setting the potential of one arbitrary vertex to zero.
  • Applying Kirchhoff's Current Law at each vertex to get a relationship between edge currents.
  • Applying Ohm's Law to express each edge current in terms of the potential of the vertices at its ends.

Following this procedure you will end up with a system of linear equations that, when solved, will give you the potential at all vertices. The potential difference between the two vertices where the current source is connected will be the resistance between them by definition.

Edit 1/9 - Example

Let's suppose we have the following circuit:

enter image description here

and we want the resistance between the nodes (vertices) $A$ and $D$. Connecting a unit current source between them and applying the KCL we get:

enter image description here

$({\rm A})\quad -I_{AB}-I_{AC}+1=0$

$({\rm B})\quad I_{AB}-I_{BC}-I_{BD}=0$

$({\rm C})\quad I_{AC}+I_{BC}-I_{CD}=0$

$({\rm D})\quad I_{BD}+I_{CD}-1=0$

If we express the currents in terms of the node potentials we get the following system of equations:

$({\rm A})\quad -\frac{1}{3}(V_A-V_B)-\frac{1}{2}(V_A-V_C)=-1$

$({\rm B})\quad \frac{1}{3}(V_A-V_B)-\frac{1}{6}(V_B-V_C)-\frac{1}{4}(V_B-V_D)=0$

$({\rm C})\quad \frac{1}{2}(V_A-V_C)+\frac{1}{6}(V_B-V_C)-\frac{1}{5}(V_C-V_D)=0$

$({\rm D})\quad \frac{1}{4}(V_B-V_D)+\frac{1}{5}(V_C-V_D)=1$

Arbitrarily setting $V_C$ to zero and reordering:

$({\rm A})\quad (-\frac{1}{3}-\frac{1}{2})V_A+\frac{1}{3}V_B =-1$

$({\rm B})\quad \frac{1}{3}V_A+(-\frac{1}{3}-\frac{1}{6}-\frac{1}{4})V_B+\frac{1}{4}V_D=0$

$({\rm C})\quad \frac{1}{2} V_A+\frac{1}{6}V_B+\frac{1}{5}V_D=0$

$({\rm D})\quad \frac{1}{4}V_B+(-\frac{1}{4}-\frac{1}{5})V_D=1$

The system has 3 unknowns and 4 equations, but it's not overdetermined because each equation is equivalent to the sum of the other three. Throwing away one of the equations and solving the system we get the following node potentials:

$V_A = \frac{46}{43}$

$V_B = -\frac{14}{43}$

$V_D = -\frac{310}{129}$

As the unit current is being injected at the node $A$, the resistance will be given by $V_A-V_D$:

$R_{AD}=\frac{V_A-V_D}{1} = \frac{46}{43} + \frac{310}{129} = \frac{448}{129} \approx 3.47$

share|improve this answer
add comment

While mmc's answer is correct, the result of applying Kirchhoff's laws is that you get the Graph Laplacian problem.

Given a graph G with each edge E_i given a resistance R_i, the weighted graph Laplacian is given by considering the operation on functions which takes $\phi(V)$ to

$$ \nabla^2 \phi = \sum_{<W,V>} {1\over R_i} (\phi(W)-\phi(V)) $$

Where the sum extends over all W which are graph neighbors of V. This graph Laplacian then can be solved with discrete delta-function (kronecker delta) sources. The interpretation of the Laplacian is that $\phi$ is the voltage at each point, the Laplacian is summing the currents entering each node (with sign) and setting it to zero.

If you force a certain current into one node and extract the same current at another node, you are solving the equation

$$ \nabla^2 \phi = \delta_{V,V_1} - \delta_{V,V_2} $$

The solution gives the electrostatic potential configuration for all the nerd-sniping problems. For finite graphs, this is a matrix inversion. For infinite homogenous graphs with a translation symmetry, you can reduce the translation invariant directions by Fourier transforms, which allows you to solve any homognenous grid. For general graphs, you study the graph Laplacian, which is related to the random walk on the same graph, which has many bounds on the eigenvalues, which give you the asymptotic behavior of the potential in nearly all the cases of interest.

share|improve this answer
add comment

Your Answer


