線形代数 · 第12回 · 動画2 · インタラクティブ教材

一つの行列でつながる：キルヒホッフの法則、ループ電流、オイラーの公式

I重要な公式

公式 名称 説明
Aij=−1A_{ij} = -1（出発点）、+1+1（到着点）、00（それ以外） 接続行列の規則 各行に −1-1 と +1+1 が1つずつ
A⊤y=0A^\top y = 0 キルヒホッフの電流則 どの節点でも電流が釣り合う
rank(A)=n−1\text{rank}(A) = n - 1 階数（連結グラフ） 節点の個数より1小さい
n−m+ℓ=1n - m + \ell = 1 オイラーの公式 節点の数 −- 辺の数 ++ 独立なループの数 =1= 1

II可視化1 — グラフ ↔ 接続行列

各辺は行列の1つの行になります。出発点に −1-1、到着点に +1+1、それ以外は 00 です。

💡 e1e_1 の行と e2e_2 の行の和から e3e_3 の行を引くと 0 になります。閉じたループ 1→2→3→11 \to 2 \to 3 \to 1 があるために、接続行列のこれらの行は一次従属になるのです。

III可視化2 — ループ電流はキルヒホッフの電流則を満たす

y=a ループ1+b ループ2y = a\,\text{ループ}_1 + b\,\text{ループ}_2 がどんな組み合わせでも、すべての節点で電流が釣り合います。つまり A⊤y=0A^\top y = 0 です。

💡 基底となる電流 (1,1,−1,0,0)(1,1,{-1},0,0) と (0,0,1,−1,1)(0,0,1,{-1},1) は A⊤A^\top の零空間を張ります。その次元は独立なループの個数 ℓ=2\ell = 2 に等しくなります。

IV可視化3 — なぜ n−m+ℓ=1n - m + \ell = 1 なのか

辺を全域木の辺（n−1n-1 本）と ℓ\ell 本のループの辺に分けると、交互に足し引きした数はいつも 11 に行き着きます。

V確認クイズ

問1

動画のグラフでは、辺 3 は節点 1 から節点 3 へ向かいます。接続行列 AA の3行目（辺 3）、2列目（節点 2）の成分はいくつですか。

✅ 正解です！ 節点 2 は辺 3 の端点ではないので、成分は 0 です。

❌ 惜しい！ −1 が入るのは出発点の列、+1 が入るのは到着点の列だけです。それ以外の成分はすべて 0 です。

解答を見る

解答：

辺 3 は節点 1 から節点 3 へ向かいます。接続行列の規則により：

  • 1列目（出発点）：−1-1
  • 3列目（到着点）：+1+1
  • それ以外の列：00

AA の3行目：[−1,  0,  1,  0][-1, \; 0, \; 1, \; 0]

節点 2 は辺 3 の端点ではないので、(3行目, 2列目) の成分は 0 です。

問2

正しいか誤りか：節点が nn 個の連結グラフでは、その接続行列 AA の階数は nn（節点の個数）に等しい。

✅ 正解です！ 階数は n − 1 です。A の列を足し合わせるとつねに 0 になるので、従属関係が必ず1つあるからです。

❌ 惜しい！ A の列をすべて足し合わせるとどうなるか、考えてみましょう。

解答を見る

解答：

誤り。階数は n−1n - 1 であり、nn ではありません。

AA のどの行も、成分の和は 0 です（−1-1 と +1+1 が1つずつ）。つまり AA の列を足し合わせると、つねに零ベクトルになります。これは一次従属の関係です。したがって、列空間の次元は高々 n−1n - 1 です。

連結グラフでは、階数はちょうど n−1n - 1 です。零空間 N(A)N(A) の次元は 1 で、定数ベクトル (1,1,…,1)(1, 1, \ldots, 1) で張られます。これは「接地」で決める基準電位の自由度を表しています。

問3

ある連結グラフには節点が 6 個、辺が 10 本あります。独立なループはいくつありますか。

✅ 正解です！ ℓ = m − n + 1 = 10 − 6 + 1 = 5 で、独立なループは 5 つです。

❌ 惜しい！ 公式 ℓ = m − n + 1 を当てはめましょう。

解答を見る

解答：

節点が nn 個、辺が mm 本の連結グラフでは、独立なループの個数は次のとおりです。

ℓ=m−n+1\ell = m - n + 1

n=6n = 6、m=10m = 10 を代入すると：

ℓ=10−6+1=5\ell = 10 - 6 + 1 = 5

なぜでしょうか。全域木は n−1=5n - 1 = 5 本の辺を使います。残りの 10−5=510 - 5 = 5 本の辺は、木に戻すたびにそれぞれちょうど1つの独立なループをつくります。この個数は dim⁡N(A⊤)=m−r=m−(n−1)\dim N(A^\top) = m - r = m - (n-1) に等しくなります。

問4

動画の接続行列では、1行目は [−1,1,0,0][-1, 1, 0, 0]（辺 1→2）、2行目は [0,−1,1,0][0, -1, 1, 0]（辺 2→3）です。この2つの和は3行目 [−1,0,1,0][-1, 0, 1, 0]（辺 1→3）に等しくなります。この一次従属の関係は、グラフの何を表していますか。

✅ 正解です！ 行の従属関係「1行目 + 2行目 = 3行目」は、グラフの閉じた三角形のループ 1→2→3→1 にそのまま対応しています。

❌ 惜しい！ 辺 1、続けて辺 2 をたどると、辺 3 だけで行くのと同じ場所に着きます。これが何を意味するか考えてみましょう。

解答を見る

解答：

1行目 + 2行目 = 3行目 は、辺 1（1→21 \to 2）に続いて辺 2（2→32 \to 3）をたどると、辺 3（1→31 \to 3）と同じ行き先に着くことを意味します。辺 3 を逆向きにたどれば、閉じたループ 1→2→3→11 \to 2 \to 3 \to 1 ができます。

グラフの閉じたループは、どれも接続行列の対応する行の間に一次従属の関係を生みます。これが、グラフの位相幾何学と線形代数を結ぶ基本的なつながりです。

一般に、行の独立な従属関係の個数は m−(n−1)m - (n-1) で、独立なループの個数とちょうど一致します。

正解数：0 / 4