メンガーのふるい

 辺と節に値があるグラフを表にするとSQLで扱えて便利なことがある.今回はメンガーのふるいを紹介したい.「メンガーのスポンジ」や「メンガーの定理」で有名なメンガーに因んだ計算方法である.
 まず,下図のようなグラフモデルがあるとする.

 このグラフですべての節を通るもっとも高い値を得られる経路を求めたい.ただし,値の求め方は,到着した節の値に対し通った辺の値を掛けるものとする.E×Vである.メンガーのふるいはこのような条件だけでなく,多様な条件を設定することができる汎用的な方法であると加えて述べておきたい.

 節の値と辺の値,そして計算用の列を上図のように表にする.次に,節と辺の接続を下図のように数値で入れる.値は先ほど述べた条件のE×Vである.

 まず,行と列を眺めて,数が2つしか入っていない行や列を見つけたら,線でつないでしまおう.今回はすべての行があてはまるので下図のようになる.

 次に,計算用のS列の値が大きい順にみていく.大きい同士で接続したいので,下図のように線を引く.

 これをS列の値が大きい順に繰り返す.

 ここで,2通りの経路を踏むことはしない条件だったので,複数通りの経路を引けたところは,大きいことが確定したところから削除して整理する.




 最後に経路が1通りの閉路に定まったら,それが求めたい経路だ.

 グラフではこのような経路だったことになる.2つの辺を通らないことが判断できた.

 このように,メンガーのふるいで条件に最適な経路を,グラフの上でなく表の上で計算して確実に求めることができる.臨機応変に条件を細かく変更することも難しくない.工事中で通過できない辺は予め表に入れなければよいし,ほかにも「通過必須の辺」「節の通過はどの節も1回のみ」「辺の値の和が最大になる経路」といった条件でもメンガーのふるいで計算できる.さまざまなグラフで試してほしいと思う.次回はメンガーのふるいをSQLで扱う方法について(予定).