ページ作者 堀江伸一
グラフ理論
木構造に関する雑題
この雑記ではグラフ理論の雑題を例に素朴な発想でもグラフ理論の問題を解ける場合があることを提示したい。
難しい理屈よりコロンブスの卵的発想が重要な時もあるという感じの話です。
問題
辺が重み付き（コスト）であらわされた木構造が与えられ点にa0～anまでの番号が振られている。
i<jとなる全ての組みでf(ai,aj)となる組の計を求めよ。
fはaiとajを最短編でつなげた時途中にある最大重みの辺の値を返すとする。
この問題は何を聞いているのか？
まず具体的な図で説明してみよう。
ｆはどんな関数なのか？
例えば２つの点を繋げこれを適当にa0,a1とすると
部屋a0とa1を繋げる最短ルートは赤線の通りで、途中にある辺のコストは8,10,6、10が最も大きいのでa0とa1を繋げるコストは10と計算しこれをf(a0,a1)=10とあらわす。
これを全ての２つの点で試した場合の合計値を求めよという問題になっている。
手ごろなグラフ理論の演習問題です。
まず最初に考えつくのは全ての２点間を繋げてそれを数える方法である。
青線の経路がf(a0,a3)=3 赤線の経路がf(a0,a1)=10 黄色線の経路がf(a0,a2)=7,灰色線の経路がf(a1,a2)=10
とこれを続け全ての場合を試して足していく方法である。
グラフが小さいうちはこれでも間に合うが少しグラフが大きくなると次のような問題が生じる。
あるaiからスタートするとき上図のような視点となるが自分より番号の大きな点がどの方向にあるかわからない。
点の数が10万個などと多くなると、10万＾２/2というかなり途方もない数を検証する必要がありコンピュータに解かせても大変。
この素朴すぎる方法ではどうも大変そうだとわかる。
ここで視点を変えてみよう。
ある２点間を繋ぐ経路のｆを決定できる辺はどれか？
ある辺に着目した時、その辺がｆのコストを決定できる経路の集合はどうなるか？
この視点変更一つ出来ると計算が非常に楽になる。
何やら難しそうに見えるが、図を見ながら解説を読めば理解できるはずなので図で説明してみよう。
まずは一番ｆ(ai,aj)が一番小さくなる経路とは何かを考えてみる。
これでもわかりづらいので全部の辺をいったん切除して、辺の重みの小さい辺から復旧していくと考えると。
この問題はとても綺麗に解ける。
図で確認していってみよう。
説明が短くなるように8の重みの辺を5に変えて説明する。
この図から辺を削除してコストの低い方から繋げ直してみよう。
そうするとこの問題の計算が楽に終わることがわかる。
まず重み２のうち赤と青を繋げた。
この繋げた２点はどちらも隣同士だし、これよりコストの高い辺を通ることはない。
よってf(a4,a0)=f(a7,a8)=2であると確定する。
ここまでで合計コスト4となる。
a0とa4を繋げる。
するとa4,a0とa5の間の経路に２より高いコストがないことが判明する。
f(a0,a5)=f(a4,a5)=2が判明した。
この時の計算は
赤線の片方の先にあるつながっている部屋数*もう片方の先にある部屋数*繋げた辺のコストとなる。
またコストの低い方から繋げているのでa0、a4,a5以外の点がこれら３点にコスト２以下で経路を繋げる方法はない。
次にコストの小さい経路を繋げる。
小さい方から繋げているのでa0,a4,a5,a3とそれ以外の点を繋げる経路は３より低い経路でつながることはないということは明白である。
コストの小さい方から繋げているのですからa0,a4,a5からa3へ向かうコストの３つは３よりコストが高くなることはない
この接続では9=3(赤線の片方の先にある部屋数)*1（赤線の片方の先にある部屋数）*3（辺の重み）のコストがかかると判明しました。
問題は次の接続。
a0,a4,a5,a3とa7,a8を繋げる経路のコストは必ずコスト5の辺を通らないといけない。
よってf（ai,,,aj）はどれか一つを選ぶとして。
どの組み合わせでもコスト5であると判明する。
よって
40＝赤線の片方にある部屋数4*赤線のもう片方にある部屋数２*経路のコスト5
がこの辺でコストが決定される経路全てを網羅したものだと判明しました。
重要なのはa0,a4,a3,a5の２つを選んで結ぶ経路の組み合わせも、a7,a8を繋げたコストの組み合わせもここまでの時点で全部計算が終わっている。
またこの計算の結果a0,a4,a5,a3,a7,a8のうち２点を繋げる経路も計算が終わったことになる点です。
黒線でつながってる部分内部の経路は全部計算が終わっているという部分が重要です。
この手順を繰り返し全ての線をコストの低い方から繋げていき計算したコストを足し合わせると最終的に全ての２点間のコストを求めたこととおなじとなります。
最後の辺を繋げた時、最後の辺の片方の先にある点は全部計算が終わっているし反対側も同じ。
そして最後を繋げた時のコストを計算し終わると全ての経路のコストが計算されているというわけです。
この方法の利点は点の数が数十万個以上になったときコンピュータに解かせても非常に効率よく計算できる方法です。
プログラマはこういう問題をユニオン木や優先順位付きキューという概念を使って上記の計算を実行させます。
どうだろうか？
一見難しく見える問題も視点を変えれば簡単に解ける場合があるということをお分かり頂けたと思う。
このグラフの問題に限らず問題に挑戦するときは色々な視点から挑戦する。
この精神を養ってほしい。
最後に
私の要領を得ない説明をお読み頂きありがとうございました。
多分わかりづらい点も多々あると思います。
そういう点があればご指摘ください。
最終更新：2013年08月23日 16:26
