概要
たとえばこのような回路が与えられたとき、合成抵抗を求めるには、簡単な計算で求められるはずです。並列の部分は1/(1/R+1/R)=R/2で、直列のRと合わせることでR+R/2=3R/2となります。
次、
こんな感じになると今までの並列直列戦法ではうまくいきません。
まあでも立方体の場合はまだ良心的です。各辺に流れる電流を記録してみると、対称性からちゃんと計算できるので、こうなります。
Iの電流を流すと、RI/3+RI/6+RI/3=5R/6 Iの電位差が生じるので、結局5R/6の大きさの抵抗でもいいということなので、合成抵抗は5R/6となります。
ただ、今回はたまたま立方体に対称性があったから解けたのですが、一般のグラフのときでも解けるようなアドホックじゃない方法はあるのでしょうか？
問題設定
N頂点M辺の連結無向グラフがある。頂点には1からNまでの番号がついている。
また、各辺は大きさRの抵抗となっている。
頂点1と頂点Nで端子を結んだときの合成抵抗を求めよ
理論
こういう場合に使うのはキルヒホッフの法則です。
つまり、
・閉路を見たときに電位差の和は0
・分岐点を見たときに、入ってくる電流＝出ていく電流
です。
つまり、各辺ごとに流れる電流を変数として連立方程式を作って解けばOK
…としたいところですが、変数の数はMあります。また、プログラムを組むとき、「閉路の電位差の和=0」の部分の処理が面倒です。
なので、以下の方法にします。
閉路を見たときに電位差は0となっているため、各頂点に対して電位を定義することができます。これは辺ごとに見て、流れる電流×抵抗値の和を追跡すれば良いわけです。で、キルヒホッフの第2法則より、どのような経路で電位を計算しても最終結果がおなじになることが保証されているので問題ないわけです（電流の向きが追跡する向きと逆なら、電流の値に-1をかければOK）
で、$V_1,...,V_N$を拡頂点の電位の値とします。
こうして、$u\to v$の辺があったときはその辺に$u\to v$方向に大きさ$\dfrac{V_v-V_u}{R}$の電流が流れると考えればOKというわけです。そうすれば電位の値をどのように設定してもキルヒホッフの第2法則は確実にクリアできるようになっています。
で、実際の電位の値がどうなっているかについては、キルヒホッフの第1法則を使います。
頂点$u$をみたとき、$u$に隣接する辺の集合を$G_u$とします。
このとき、$u$に入ってくる電流-$u$から出ていく電流は、
$\sum_{v\in G_u} \dfrac{V_u-V_v}{R}$
となっています。これが0になる...と言いたいところですが、頂点1とNだけは例外でIと-Iになります。
百聞は一見にしかず
例題を示しましょう
こんなグラフがあったとしたら
$$\begin{pmatrix}2& -1& 0& -1& 0& 0\\-1& 3& -1& 0& -1& 0\\0& -1& 2& 0& 0& -1\\-1& 0& 0& 2& -1& 0\\0& -1& 0& -1& 3& -1\\0& 0& -1& 0& -1& 2&\\\end{pmatrix}\begin{pmatrix}V_1\\V_2\\V_3\\V_4\\V_5\\V_6\\\end{pmatrix}=\begin{pmatrix}1\\0\\0\\0\\0\\-1\\\end{pmatrix}$$
という連立方程式を解けば良いです。
ところで、この行列は一般に正則とはなりません。なぜなら右から($1,1,\ldots,1)^\top$を掛けると0になるからです。
ですが、恐らくですが、グラフが連結ならば連立方程式の解は一応存在します。解を求めるには
$$\begin{pmatrix}2& -1& 0& -1& 0& 0&1\\-1& 3& -1& 0& -1& 0& 0\\0& -1& 2& 0& 0& -1& 0\\-1& 0& 0& 2& -1& 0& 0\\0& -1& 0& -1& 3& -1& 0\\0& 0& -1& 0& -1& 2& -1\\\end{pmatrix}$$
のrrefを求めればOKです。
これはラプラシアン行列というものを基本として、一番右の列に1列値を追加したN行N+1列の行列となっています。
これを数式処理ソフトなどで計算すると
$$\begin{pmatrix}1& 0& 0& 0& 0& -1& 7/5\\0& 1& 0& 0& 0& -1& 4/5\\0& 0& 1& 0& 0& -1& 2/5\\0& 0& 0& 1& 0& -1& 1\\0& 0& 0& 0& 1& -1& 3/5\\0& 0& 0& 0& 0& 0& 0\\\end{pmatrix}$$
みたいな形になります。左からN列がこのような形になっていたらOKです。このとき一番右の列を見ると、i行目は頂点$V_i$と頂点$V_N$の電位差の値となっています。当然$V_N$から$V_N$への電位差は0なので、一番右の列の一番下の行は0となっている。
で、$V_1$から$V_N$へ電気を流したときの合成抵抗は行列の一番右上の値となっています。つまりこの例の場合だと$7R/5$というわけです。
この手法は一般のグラフに対しても適用することができます。
ソースコード
rrefを計算してくれるコードはそこら中に転がっているのでそれを使います。
例としてsympyにはrrefを計算してくれる関数があるみたいなのでそれに丸投げします。
gist04f592a5927e7833ca67c9e1e880003c
実行例
立方体のグラフの場合、こうなります
[ [1, 0, 0, 0, 0, 0, 0, -1, 5/6], [0, 1, 0, 0, 0, 0, 0, -1, 1/2], [0, 0, 1, 0, 0, 0, 0, -1, 1/2], [0, 0, 0, 1, 0, 0, 0, -1, 1/3], [0, 0, 0, 0, 1, 0, 0, -1, 1/2], [0, 0, 0, 0, 0, 1, 0, -1, 1/3], [0, 0, 0, 0, 0, 0, 1, -1, 1/3], [0, 0, 0, 0, 0, 0, 0, 0, 0]]
i xor jが2べきのときに辺が繋がっている状態だと思ってください。
ただ、行列の各成分は1からNに電流を流したときの頂点iと頂点Nの電位差となっているため、iとNを端子で結んだときの合成抵抗になってないことに注意してください。
立方体の同一平面上の対角線を端子にした場合だとこうなります。
ここで、入出力端子を変更するには一番右の列を変えればOKです。
G=[[1, 2, 4], [0, 3, 5], [3, 0, 6], [2, 1, 7], [5, 6, 0], [4, 7, 1], [7, 4, 2], [6, 5, 3]]
行列
[3, -1, -1, 0, -1, 0, 0, 0, 1]
[-1, 3, 0, -1, 0, -1, 0, 0, 0]
[-1, 0, 3, -1, 0, 0, -1, 0, 0]
[0, -1, -1, 3, 0, 0, 0, -1, -1]
[-1, 0, 0, 0, 3, -1, -1, 0, 0]
[0, -1, 0, 0, -1, 3, 0, -1, 0]
[0, 0, -1, 0, -1, 0, 3, -1, 0]
[0, 0, 0, -1, 0, -1, -1, 3, 0]
rref
[
[1, 0, 0, 0, 0, 0, 0, -1, 1/2],
[0, 1, 0, 0, 0, 0, 0, -1, 1/8],
[0, 0, 1, 0, 0, 0, 0, -1, 1/8],
[0, 0, 0, 1, 0, 0, 0, -1, -1/4],
[0, 0, 0, 0, 1, 0, 0, -1, 1/4],
[0, 0, 0, 0, 0, 1, 0, -1, 1/8],
[0, 0, 0, 0, 0, 0, 1, -1, 1/8],
[0, 0, 0, 0, 0, 0, 0, 0, 0]]
3/4
一番右の列を調整すると入力端子と出力端子を変更することができます。
このときの合成抵抗はA(N,in)-A(N,out)で計算できるので、A(8,0)-A(8,3)=1/2-(-1/4)=3/4となり、合成抵抗は3R/4となります。
FAQ
このプログラムは抵抗値の比が有理数の時しか使えないのでは？
その場合では、係数を調整すればOK
キルヒホッフの第1法則のところが
$$\sum_{v\in G_u} \dfrac{V_v-V_u}{R_{u,v}}=0$$
なので、$(u,u)$成分は$\sum_{v\in G_u}\dfrac{1}{R_{u,v}}$で、$(u,v)$成分は$-\dfrac{1}{R_{u,v}}$であるような行列に対して同様の連立方程式を解けばOKです。
2Ωの抵抗を再現するには1Ωの抵抗を2個直列に繋ぐことで一応再現できますが頂点数が増えます。（他にも有理数に対して適切なグラフを埋め込むことでなんとかできなくもないですが…）係数が有理数の場合でも行列のサイズを削減できて計算量を減らすことができます。
多重辺・自己ループでもいける？
一応行けます。例えばこの記事の最初で出てきた回路の場合、
G=[[1,1],[0,0,2],[1]]
とすればOKです。
自己ループも同じようなノリでいけなくはないですが…正直意味は無いと思います。
なぜならば、自己ループは両端の電位差がないため電流が流れません。なのであってもなくても全体の結果には影響しません。
計算量は？
この記事で上げたソースコードの場合、rrefを計算するところがボトルネックになっているのでそこに完全に依存しきってます
まあガウスの消去法なので計算量は多項式$O(N^3)$だと思います。
sympyって遅いのでしょうか？あまり使ったこと無いのでわかりませんごめんなさい
