第３０回助教の会

2014年度初回の助教の会では，数理２研の小林が発表しました．開始以来だんだんと長文になってきていたこのブログですが，担当者の負担が大きいこともあり，本年度から本人が書く形式にすることになりました．今後ともよろしくお願いします．

さて，今回は「円板形領域損傷モデルにおける 最大流最小カット定理と高速アルゴリズム」というタイトルで発表いたしました．ネットワークの信頼性の指標として用いられる「グラフの連結度」は，グラフ理論や最適化の分野で盛んに研究されています．連結度は，「何本の辺（点）を取り除くとグラフが連結でなくなるか？」を表す量であり，辺や点を取り除くことは，ネットワークにおいてリンクやノードが故障することを意味しています．

今回は，道路網のように平面上に埋め込まれているグラフを考えます．そして，個々のリンクやノードの故障を考える代わりに，自然災害や事故のように，損傷が地理的な広がりを持った領域で起こるモデルを考えています．具体的には，損傷がおこる領域は円板形で表され，損傷がおこるとその領域内のリンクやノードがすべて使えなくなるという設定です．

このモデルにおいて，いくつの損傷が起こると連結性が壊れるかを求める問題（最小カット問題）と，その双対にあたる問題（最大流問題）を扱ったのが今回の発表の内容です．本研究では，これらの問題に対して，最大最小定理を与え，高速なアルゴリズムを構築しています．

同じ内容で講演したものがこのページにありますので，興味のある方はご覧下さい．

数理第二研究室 小林佑輔