2
$\begingroup$

I want to compute the resistance function r(p,q) between any two vertices of a fairly complicated graph. This resistance function is the one in Admissible pairing on a curve by Shouwu Zhang, section 3 page 179.

The graph is too complicated and merely applying series and parallel reductions I am getting nowhere. Can one direct me to a good reference for circuit reductions on metrized graphs?

$\endgroup$
3
$\begingroup$

In general, you shouldn't expect to be able to compute the effective resistance of an electrical circuit using only series and parallel reductions; the class of graphs (called series-parallel graphs) for which this can be done is quite special. There are other transformations for computing resistances such as star-triangle / delta-Y transformations but similar comments hold.

However, resistance computations for metrized graphs are really not so bad. They always boil down to solving a linear system of equations involving the Laplacian matrix of a weighted graph which models the metrized graph. This expository paper of Baker and Faber seems to be a good reference; see Theorem 4 for the relation between the Laplacian operator of a metrized graph and the Laplacian matrix of a weighted graph model.

Since the two points you care about are vertices of the metrized graph, you can proceed as follows. First, write down the Laplacian matrix for a weighted graph model of your metrized graph with the same vertex set $V$ (see Definition 7 of Baker and Faber). This is a symmetric $|V|\times|V|$ matrix $Q$. Let $\delta_j$ be the $|V|$-dimensional vector whose components are all zero except for the $j$th component, which is 1. Then it is possible to find a vector $v$ such that:

$$Qv=\delta_p-\delta_q.$$

(Note that $Q$ is not invertible, so $v$ is only defined up to addition of scalar multiples of the vector $(1,1,1,\dots,1)$).

The effective resistance you want is $r(p,q)=v_p-v_q$; note that this difference is well-defined even if $v$ is not.

You can derive this formally from the properties of $r(p,q)$ (see e.g. section 6 of Baker and Faber), but I wrote it down using the following physical intuition: suppose one unit of current is injected at $p$ ($+\delta_p$) and removed at $q$ ($-\delta_q$), then the effective resistance is equal to the potential difference between $p$ and $q$.

One way to compute $r(p,q)$ without worrying about the kernel of $Q$ is to delete any row and column of $Q$ to get a matrix $\tilde Q$ (now with full rank $|V|-1$) and delete the corresponding rows of $\delta_p,\delta_q$ to get vectors $\tilde\delta_p,\tilde\delta_q$. Then there is a unique solution to

$$\tilde Q\tilde v=\tilde\delta_p-\tilde\delta_q,$$

(throw this into your favorite computer algebra / numerical linear algebra program) and $\tilde v_p-\tilde v_q$ is the effective resistance you want.

$\endgroup$
  • $\begingroup$ Is this method of deleting a row and column of $Q$ to produce an invertible matrix $\tilde{Q}$ also useful for finding the Moore-Penrose inverse of $Q$? This may be a naive question so I apologise in advance. $\endgroup$ – Chitrabhanu Jan 16 '18 at 10:56
  • $\begingroup$ @Chitrabhanu I'm not sure exactly what you have in mind, but I suppose the Moore-Penrose inverse can be used to compute an orthogonal projection operator onto the orthogonal complement of the kernel of $Q$. Deleting a row and column is applying a different projection operator so I don't think it can be used in the way you're asking. $\endgroup$ – j.c. Jan 16 '18 at 13:16
  • $\begingroup$ Thanks @j.c. for helpful answer. Can you give some reference for the row and column deletion method that you outlined above? $\endgroup$ – debargha Jan 17 '18 at 14:52
  • $\begingroup$ @debargha It's not hard to see that extending $\tilde v$ to $v$ by adding a zero in the deleted component results in a solution to $Qv=\delta_p-\delta_q$, but you can also see for instance the paragraph after Kirchhoff's Voltage Law on page 15 of these notes by David G Wagner math.uwaterloo.ca/~dgwagner/Networks.pdf . $\endgroup$ – j.c. Jan 17 '18 at 19:37
  • $\begingroup$ @j.c. thanks a lot for a prompt reply. This is really helpful. $\endgroup$ – debargha Jan 18 '18 at 4:37

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.