全域木の個数に関するキルヒホフの法則

540

全域木とは連結グラフの部分グラフですべての頂点を共有するものをいう。グラフによってはきれいに求めることができる。それについていくつかの結果を述べたい。
　連結グラフ $G$ に対し、その全域木の個数を $| G |$ と書くことにする。

定義いろいろ

抵抗器

連結グラフ $G$ は $2$ つ以上の頂点をもつとする。 $G$ の異なる $2$ 点 $p, q$ に対し、この $2$ 点を付随させて考えたものを抵抗器と呼び $A = (G, p, q)$ みたいに書く。なぜ $2$ 点を取り出して考えるのかは後でわかる。

値

抵抗器 $A = (G, p, q)$ の値 $v a l (A) = (α, β)$ とは、 $G$ の全域木の個数 $α = | G |$ と、 $G$ の全域部分グラフで $p$ を含む木と $q$ を含む木の互いに頂点を共有しない合併になっているものの個数 $β$ の組とする。 $β$ はまた、 $G$ において $p$ と $q$ を同一視して得られるグラフの全域木の個数に等しい。

抵抗器

抵抗器の例

逆

抵抗器 $A = (G, p, q)$ について $p$ と $q$ を入れ替えたものを $A^{'} = (G, q, p)$ と書く。当然のごとく、 $v a l (A) = v a l (A^{'})$ である。

直列

抵抗器 $A_{1} = (G_{1}, p_{1}, q_{1}), A_{2} = (G_{2}, p_{2}, q_{2})$ について、それらの直列というのは、 $q_{1}$ と $p_{2}$ を同一視してできる連結グラフを $G$ と書くときの $A = (G, p_{1}, q_{2})$ のことをいう。 $A = A_{1} ⊥ A_{2}$ のように書く。結合律：
$(A_{1} ⊥ A_{2}) ⊥ A_{3} = A_{1} ⊥ (A_{2} ⊥ A_{3})$
が成り立つし、逆について、
$(A_{1} ⊥ A_{2})^{'} = A_{2}^{'} ⊥ A_{1}^{'}$
も明らか。

直列

直列の例

直列の値

$A_{1} = (G_{1}, p_{1}, q_{1}), A_{2} = (G_{2}, p_{2}, q_{2})$ について、それらの値を
$v a l (A_{1}) = (α_{1}, β_{1}), v a l (A_{2}) = (α_{2}, β_{2})$
とするとき、直列について、
$v a l (A_{1} ⊥ A_{2}) = (α_{1} α_{2}, α_{1} β_{2} + β_{1} α_{2}) .$

直列の値

並列

抵抗器 $A_{1} = (G_{1}, p_{1}, q_{1}), A_{2} = (G_{2}, p_{2}, q_{2})$ について、それらの並列というのは、 $p_{1}$ と $p_{2}$ を同一視し、 $q_{1}$ と $q_{2}$ を同一視してできる連結グラフを $G$ とするときの $A = (G, p 1 = p 2, q 1 = q 2)$ のことをいう。 $A = A_{1} ∥ A_{2}$ のように書く。次は容易に知られる：
$(A_{1} ∥ A_{2}) ∥ A_{3} = A_{1} ∥ (A_{2} ∥ A_{3}) .$
$(A_{1} ∥ A_{2})^{'} = A_{1}^{'} ∥ A_{2}^{'} .$
$A_{1} ∥ A_{2} = A_{2} ∥ A_{1} .$

並列

並列の例

並列の値

$A_{1} = (G_{1}, p_{1}, q_{1}), A_{2} = (G_{2}, p_{2}, q_{2})$ について、それらの値を
$v a l (A_{1}) = (α_{1}, β_{1}), v a l (A_{2}) = (α_{2}, β_{2})$
とするとき、並列について、
$v a l (A_{1} ∥ A_{2}) = (α_{1} β_{2} + β_{1} α_{2}, β_{1} β_{2}) .$

並列の値

リンク

抵抗器 $A_{i} = (G_{i}, p_{i}, q_{i}) (i = 1, 2, \dots, n)$ があるとき、 $q 1$ と $p 2$ , $q 2$ と $p 3$ , $\dots$ , $q_{n - 1}$ と $p_{n}$ , $q_{n}$ と $p_{1}$ という風に輪を作るようにしてつないでできる連結グラフを $G = l i n k (A_{1}, A_{2}, \dots, A_{n})$ と書く。

リンクの値

抵抗器 $A_{i} = (G_{i}, p_{i}, q_{i}) (i = 1, 2, \dots, n)$ があるとき、それらの値を
$v a l (A_{i}) = (α_{i}, β_{i})$
として、リンクの全域木の個数は、
$| l i n k (A_{1}, A_{2}, \dots, A_{n}) | = α_{1} \dots α_{n} (\frac{β_{1}}{α_{1}} + \dots + \frac{β_{n}}{α_{n}})$
で与えられる。特に、リンクを作るときの $A_{i}$ たちの順序を入れ替えたり、構成する抵抗器の一部を逆で取り替えたりしても、出来上がるリンクの全域木の個数は変化しない。

リンクの値

以下のリンクでは $4$ つの $(4, 3)$ を組み合わせているので、
$4 \cdot 4 \cdot 4 \cdot 4 \cdot (\frac{3}{4} \times 4) = 768$
が求める全域木の個数になる。
g7f6dftg

次がある意味で主定理になる。

全域木の個数に関するキルヒホフの法則

抵抗器 $A = (G, p, q)$ を取る。 $G$ のすべての辺を $1 Ω$ の抵抗とみなし、 $p$ を入力、 $q$ を出力として電流を流すことを考える。すなわち各辺を重み付きの矢印とし、 $p$ と $q$ 以外のすべての点で流出量の総和が等しくなるよう、また任意のサイクルで矢印に沿った重みの和（逆方向の場合はマイナス）が $0$ になるようにこれを用意するとき、 $p$ 及び $q$ での流出量の絶対値 $I$ （電流の入力の値に当たる感じ）と $p$ から $q$ へ辺に沿って重みを足した和の値（逆方向の場合はマイナス）の絶対値 $V$ （こちらは電圧に当たる、すべての抵抗は $1 Ω$ ）、及び $A$ の値 $v a l (A) = (α, β)$ について、
$\frac{V}{I} = \frac{β}{α}$
が成立する。なお、 $V$ と $I$ の比は一意的に決まる。特に、
$β = α \times \frac{V}{I}$
であるから、 $α, I, V$ から $β$ を計算することができる。

例を出した方が分かりやすい。

全域木の個数に関するキルヒホフの法則

キルヒホフ～

これらを使って次のグラフの全域木の個数を求めてみる。
格子
いわゆる格子である。これの実際の値は、サイクル行列定理を使えば即座に出せるが、抵抗器の考え方で地道に迫ることでその裏付けがしたい。

ステップ１

ステップ1
普通の正方形型グラフを用意する。全域木の個数は $4.$ 図のように $p, q$ を設定すると値は $(4, 4)$ となり、直列して $(16, 32)$ を得る。

ステップ2

ステップ2
単純に辺をつけ足しても全域木の個数は変わらないので（自明）、左のグラフもまた全域木の個数は $16$ である。これを回路にする。電流が $4$ で電圧が $14$ みたいになるので、繋げた場合の全域木の個数は、
$16 \cdot \frac{14}{4} = 56.$
こうしてまず右のグラフの全域木の個数 $56$ を得る。

ステップ3

こうしてできた連結グラフの2点を左の図のように取り、値で $β$ の方を法則に従って出すと $80$ になる。抵抗器の値が $(56, 80)$ になるので、リンクを作ると右のグラフの全域木の個数が $56 \cdot 80 \cdot 2$ になる。これはそのままの方がいい。
g6t65fr56

ステップ4

やはり辺をつけ足しても全域木の個数は変わらないので（片方の点が孤立していればOK）、左のようにすると $α$ がさっき求めた $56 \cdot 80 \cdot 2$ になる。で、抵抗計算・・図で青の所に $1$ をおき、赤の所を文字でおき、法則を満たすように数を埋めていくと最後に1次方程式を解いて赤の所が $1 / 4$ になる。だからこんな風になる。そして $β$ の計算も、
$56 \cdot 80 \cdot 2 \cdot \frac{134}{40} = 56 \cdot 4 \cdot 134.$
r4t43t r4t43t

ステップ5（終了）

次の回路の抵抗を計算する。
fg54y546y
青い矢印を $1$ と置いたうえで赤い矢印を文字でおくとそれが $1 / 3$ と出るのでそれで分かる感じ。そこまで難しくない。 $α$ の方はさっき出した $56 \cdot 4 \cdot 134$ であるから、つないだものについては次のようになる：
$56 \cdot 4 \cdot 134 \cdot \frac{224}{67} = 56 \cdot 8 \cdot 224 = 100352.$
ゆえに、求める全域木の個数は100352個である。

サイクル行列による求め方（検算）

$I$ は $3$ 次単位行列、 $O$ は $3$ 次ゼロ行列とする。平面グラフのサイクル行列定理とは、各サイクルを添え字とし、対角成分にサイクルを構成する辺の数をプラスで、非対角成分にサイクル同士の共有辺の個数をマイナスでかいたものである。これの行列式が全域木の個数を与える。問題のグラフの場合、
$d = | \begin{array}{ccc} A & - I & O \\ - I & A & - I \\ O & - I & A \end{array} | . ただし、 A = | \begin{array}{ccc} 4 & - 1 & 0 \\ - 1 & 4 & - 1 \\ 0 & - 1 & 4 \end{array} |$
で与えられる $d$ を計算すればいい。
$\begin{aligned} d & = | A^{3} - 2 A | = | A | | A - \sqrt{2} I | | A + \sqrt{2} I | \\ = 4 \cdot (4 - \sqrt{2}) (4 + \sqrt{2}) (4 - \sqrt{2}) (4 - 2 \sqrt{2}) \cdot 4 \cdot 4 \cdot (4 + \sqrt{2}) (4 + 2 \sqrt{2}) \\ = 4^{3} \cdot (4^{2} - 2)^{2} \cdot (4^{2} - 8) \\ = 64 \cdot 14^{2} \cdot 8 \\ = 100352. \end{aligned}$
同じ値になった。

おわりに

自分で見つけたので参考文献とかはないです。シュプリンガーさんのグラフ理論かなんかの本でそれっぽい紹介があったかもしれないです。全域木の個数が分かるだけだし適用も小さいものに限られる地味な定理なので注目度は低いと思います。キルヒホフの証明は有限版のラプラシアンとか定義してやったような気がするんですけど忘れました。
　直列と並列について。抵抗器の値から $β / α$ として比を作ると、合成した場合の値が抵抗の値の直列並列での計算結果に一致しているのは興味深いです。
$\frac{β}{α} = \frac{β_{1}}{α_{1}} + \frac{β_{2}}{α_{2}} . (直列) \frac{α}{β} = \frac{α_{1}}{β_{1}} + \frac{α_{2}}{β_{2}} . (並列)$

投稿日：2020年11月22日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

黒狐

5065

数学ちょっと好きです！

他の人のコメント

コメントはありません。

読み込み中

黒狐

全域木の個数に関するキルヒホフの法則