1. HOME
  2. 電気・情報関連(入門)
  3. 研究情報(登録番号2002)

グラフアルゴリズムの革新とアルゴリズム工学への展開

道路地図や鉄道網などのように「もののつながり」を表したものをネットワークやグラフと言います.そこでは,交差点や駅は「点」として,交差点間の道路,駅間の線路は「線」として描かれます.グラフとは,線でつながれた点の集まりです.点をいくつか置き,いくつかの2点の組を選んで線で結べば,いくらでもいろんなグラフが得られます.あらかじめグラフに共通する数学的性質を見つけておくのがグラフ理論という学問の目的です.
現在 (2013年3月)のJRの鉄道網をグラフと見て,つながりの性質の一例を紹介します.いま札幌駅と東京駅の間はJRの列車を乗り継いで行き来可能ですね.もし,どこかの隣り合う2駅間の区間が不通となったとき,札幌駅と東京駅の間が行き来できなくなるでしょうか.答えは,津軽海峡線の2駅間,例えば,木古内と知内の駅間が不通になると,もはや札幌,東京間は鉄路で行き来できなくなります.それは,路線図を見たらすぐ分かるように,札幌-東京間のどのような経路も木古内と知内間を通るためです.では今度は,東京駅と京都駅の間で行き来ができなくなるためには,何か所の区間が不通にならないといけないでしょうか.例えば,次の4か所が不通になると東京-京都間の鉄路は絶たれます.東海道新幹線の豊橋,三河安城の駅間,東海道本線の蒲郡,三河塩津の駅間,中央本線の大桑,野尻の駅間,北陸本線の黒部,魚津の駅間.これら4区間を取り除くと,路線図全体が東京側と京都側に分離してしまいます.つまり,東京-京都間のどのような経路もこれら4区間のいずれかを通らなければなりません.一方で,どの3か所を不通にしても東京-京都間がまだ行き来可能であることは分かりますか.それを示すには,東京-京都間の乗り継ぎ経路を4本,互いに区間を共有しないように選ぶことができればよく,例えば,① 東海道新幹線:東京-京都,② 東海道本線・関西本線・奈良線: 東京-名古屋-木津-京都,③ 中央本線・太多線・高山本線・琵琶湖線: 東京-新宿-塩尻-多治見-美濃太田-岐阜-米原-京都,④ 長野新幹線・信越本線・湖西線: 長野-直江津-近江塩津-京都 の4経路は,互いに区間を共有していない意味で独立です.ですから,不通区間が3か所なら①~④の4経路のうちいずれか一つは生き残ります.
いまあるグラフにおいて,選んだ二つの点 A, B の間に経路がなくなるように何本かの線を取り除いたとき,そのような線の除き方をその2点A, B間のカットと言います.一方で A, Bの間で線を共有しないように経路の集まりを選ぶとき,そのような経路の選び方をA, B間のフローと言います.上で見たようにJRの路線グラフで,東京-京都間のカットのうち線の本数が一番少ない値は4で,東京-京都間のフローのうち経路の本数が一番多い値は4です.実はどんなグラフにおいても,同じ2点間ではカットの線の本数の最小値とフローの経路の最大値が同じになることが数学の定理として知られています.
近年,線の本数が最小のカットを求める問題は,データの解析など様々な応用分野に現れていますが,線の選び方をしらみつぶしで調べていたのではスーパーコンピュータを使っても手におえないことがあります.そこで,効率の良いアルゴリズム(正しく答えを見つけ出す計算手順)の設計が重要になってきます.これまで,本数が最小のカットは,経路数最大のフローを作るアルゴリズムを利用して求められてきましたが,私たちの研究ではフローの考えを使わずに直接,本数最小のカットを求めることのできる新しいアルゴリズムを発見することができました.このアルゴリズムは簡単にコンピュータ上で実装でき,答えを求める計算も速いという優れた特徴があります.さらに私たちはこのアルゴリズムを作る元になったグラフの分解に関する性質を使って,グラフのつながりに関する他の問題を効率よく解くアルゴリズムを数多く開発しました.
私たちの研究で発見された本数最小のカットを求めるアルゴリズムは,その新しい特徴から,いまでは離散最適化分野の代表的な教科書において標準的解法として紹介され,世界中の大学・大学院で教えられています.
以上のような新しいグラフアルゴリズムの発見に対して2010年,電子情報通信学会は業績賞を贈りました.



さらに詳しく知りたい読者は「専門向け」のページもご覧ください。


関連する研究を検索

分野のカテゴリ

情報処理
(情報処理理論)

関連する出来事

データなし

世の中の出来事

2010
東北新幹線が全線開業する。
2010
上海万博が開催される。

Webページ

データなし

博物館等収蔵品

データなし

キーワード

グラフアルゴリズム、グラフの森分解、離散最適化
Page Top