・グラフの質問                         りらひい氏

 電験の勉強で電気回路について時々考えるのですが、キルヒホッフの電圧則について、
少し気になっていることがあるので質問します。

 連結グラフGがある。Gの各エッジは左右が定義されている。Gの各エッジは変数を一つ持
つ。Gの中のそれぞれの閉道について、次のような等式が成り立つとする。

 閉道を一周するようにたどるとき、

 左辺=左から右に通るエッジの変数の和

 右辺=右から左に通るエッジの変数の和

 このとき、独立な等式の数はいくつあるか。

 Gが平面的グラフの場合は次のようになりそうな気がします。

 平面グラフに書き換えて、エッジに囲まれた領域(面)の数と等しくなる。

  オイラーの公式より、エッジの数−ノードの数+1。

 平面的グラフではない場合でも、「エッジの数−ノードの数+1」となるのかどうか知りたい
です。

 わたしはグラフ理論に関してはさっぱりなので、回答をもらっても理解できるかどうかは未
知数ですが、もしわかる方がいればよろしくお願いします。


 DD++さんからのコメントです。(平成30年12月31日付け)

  エッジの数−ノードの数+1

 これでよいことがオイラーの公式の証明と同様にして示されると思います。

 ざっくりいえば、エッジを(全体が連結であることを保つように)1つ取り除いたときに、それ
が閉路に含まれるものであってもそうでなくても、

  「独立な等式の数−エッジの数+ノードの数」

という量は保存します。エッジを取り除き続けて、最終的にエッジが1つになったとき、この値
は 0-1+2=1 となりますので、最初から 独立な等式の数−エッジの数+ノードの数 =1 だった
こと、つまり、

  独立な等式の数= エッジの数−ノードの数+1

であったことがわかります。


 りらひいさんからのコメントです。(平成30年12月31日付け)

 なるほど、確かにざっくりとそんな感じでいけそうですね。以前からちょこっともやもやして
いたので、すっきりしました。DD++さん、ありがとうございます。

 現実世界で普通の線形回路を組んだときに、あるひとつの状態になるのは当然のことだと
思えるのですが、物理の法則を使った計算の世界で、ひとつの解が求まるのは自明なことな
のかと考えていました。

 今回の質問の回答により、未知数の数と独立な等式の数(キルヒホッフの法則+オームの
法則)が一致することがわかり、個人的に結構納得することができたのでよかったです。



                         投稿一覧に戻る