第8回 グラフ理論の基礎¶
この回の位置づけ
シラバス（電気回路II）：線形回路の解析①（配布資料）。グラフ理論の基礎を学ぶ。
必要な準備：電気回路I 第5回のキルヒホッフの法則
この回の目標：回路をグラフとして表し、木と補木を選んで、独立な方程式がいくつ必要かを数えられる。
なぜグラフを考えるのか¶
電気回路I 第5回で、キルヒホッフの法則から連立方程式を立てました。網目が 2 つの回路では、どの閉路で式を立てればよいかは見ればわかりました。しかし回路が大きくなると、閉路の選び方は何通りもあり、次の疑問が生じます。
- 式を何本立てれば足りるのか。
- どの閉路を選べば、余分な式や足りない式が出ないのか。
この疑問に、素子の種類や値を見ずに、つながり方だけ から答える方法がグラフ理論です。
回路からグラフへ¶
回路の各素子を 1 本の線に置きかえ、つながり方だけを残した図を グラフ と呼びます。路線図が、駅の間の距離や線路の曲がり方を省いて、どの駅とどの駅がつながっているかだけを示しているのと同じです。
- 節点：線が集まる点（駅）
- 枝：節点と節点を結ぶ線（駅間の線路）
節点の数を \(n\)、枝の数を \(b\) と書きます。
木と補木¶
グラフから何本かの枝を選び、次の 2 つの条件を満たすようにしたものを 木 と呼びます。
- すべての節点が、選んだ枝でつながっている。
- 選んだ枝だけでは、閉路が 1 つもできない。
すべての駅を行き来できる状態を保ちながら、遠回りの経路がなくなるまで線路を取り除いた路線網にあたります。名前のとおり、枝分かれはあっても輪のない形です。
木に選ばれなかった枝の集まりを 補木 と呼び、その 1 本 1 本を リンク（補木の枝）と呼びます。
上のグラフは、ブリッジ回路（節点 4、枝 6）のつながり方です。チェックボックスで枝を選び、木になる組み合わせを探してください。木の選び方は 1 通りではありませんが、木の枝の数は必ず同じになります。
木の枝が \(n - 1\) 本になるのは、節点を 1 個ずつつないでいくと考えるとわかります。最初の 1 個に、残りの \(n - 1\) 個を 1 本ずつの枝でつないでいけば、全部がつながり、輪はできません。
基本閉路¶
木には閉路がありません。そこへ補木の枝を 1 本だけ戻すと、閉路がちょうど 1 つ できます。この閉路を、その補木の枝に対する 基本閉路 と呼びます。
補木の枝は \(b - n + 1\) 本あるので、基本閉路も \(b - n + 1\) 個できます。それぞれの基本閉路は、ほかの基本閉路には含まれない枝（自分を作った補木の枝）を必ず 1 本含んでいます。そのため、基本閉路で立てた電圧則の式は、どれもほかの式からは導けません（独立 です）。
必要な式の数
- 独立な 電圧則 の式（閉路の式）：\(b - n + 1\) 本（補木の枝の数）
- 独立な 電流則 の式（節点の式）：\(n - 1\) 本（木の枝の数）
合わせて \(b\) 本で、枝の数と一致します。
シミュレータのグラフでは \(n = 4\)、\(b = 6\) なので、閉路の式が 3 本、節点の式が 3 本です。
節点の式が \(n\) 本ではなく \(n - 1\) 本なのは、\(n\) 個すべての節点で電流則を書くと、全部を足し合わせたときに恒等式になってしまうからです。どの枝の電流も、一方の節点では「出る」、他方の節点では「入る」として 1 回ずつ現れて打ち消し合います。最後の 1 本は、ほかの \(n - 1\) 本から自動的に導かれます。
2 つの解析方法との関係¶
この数え方から、回路方程式の立て方が 2 通りあることがわかります。
| 方法 | 未知数 | 式の数 | 使う法則 | 回 |
|---|---|---|---|---|
| 閉路電流法 | 補木の枝の電流（閉路電流） | \(b - n + 1\) | 電圧則 | 第9回 |
| 節点電圧法 | 基準以外の節点の電位 | \(n - 1\) | 電流則 | 第10回 |
補木の枝の電流をすべて決めると、木の枝の電流は電流則から自動的に決まります。木だけでは電流が循環できないからです。逆に、木の枝の電圧（節点の電位）をすべて決めると、補木の枝の電圧は電圧則から自動的に決まります。
どちらの方法を使うかは、式の数が少ないほうを選ぶのが基本です。\(b - n + 1\) と \(n - 1\) を比べます。
例
節点 3、枝 5 の回路では、閉路の式が \(5 - 3 + 1 = 3\) 本、節点の式が \(3 - 1 = 2\) 本です。節点電圧法のほうが未知数が少なくなります。
カットセット¶
木の枝を 1 本切ると、木は 2 つの部分に分かれます。このとき、2 つの部分をまたいでいる枝の集まり（切った木の枝 1 本と、何本かの補木の枝）を 基本カットセット と呼びます。この枝の集まりを通って一方から他方へ流れる電流の合計は 0 でなければなりません。これは電流則を、1 つの節点ではなく節点のかたまりに広げたものです。
基本カットセットは木の枝の数だけ、つまり \(n - 1\) 個あり、独立な電流則の式の数と一致します。基本閉路と基本カットセットは、補木と木に対応する、対になった概念です。
まとめ¶
- グラフは、回路のつながり方だけを節点と枝で表したもの。
- 木は、すべての節点をつなぎ、閉路を含まない枝の集まり。枝の数は \(n - 1\)。
- 補木の枝 1 本ごとに基本閉路が 1 つ決まる。独立な閉路の式は \(b - n + 1\) 本。
- 独立な節点の式は \(n - 1\) 本。