小特集 1. グラフアルゴリズムの最先端

電子情報通信学会 - IEICE会誌 試し読みサイト
Vol.101 No.3 (2018/3) 目次へ

前の記事へ次の記事へ


グラフアルゴリズムの最先端

小特集 1.

グラフアルゴリズムの最先端

Frontiers of Graph Algorithms

来嶋秀治

来嶋秀治 正員 九州大学大学院システム情報科学研究院情報学部門

Shuji KIJIMA, Member (Graduate School of Information Science and Electrical Engineering, Kyushu University, Fukuoka-shi, 819-0395 Japan).

電子情報通信学会誌 Vol.101 No.3 pp.246-247 2018年3月

©電子情報通信学会2018

1.グ  ラ  フ

 グラフといっても,折れ線グラフや円グラフではない.点と線の数学である.

 グラフmathは頂点(vertex)の集合mathと頂点を結ぶ辺(edge)の集合mathから成る.辺は頂点と頂点が直接つながっていることを表し,すなわち,グラフは関係性を抽象化したものである.例えば,鉄道の路線図,電気回路,通信網,あるいは化学反応系,進化系統樹,感染症の伝搬モデル,地域コミュニティやSNSから国家連携まで様々な社会ネットワーク,企業取引や物流などの経済ネットワーク,因果関係を記述するベイジアンネットワーク,工程表などの依存関係,インターネットやスーパコンピュータなどの計算機ネットワークなど,工学,自然科学,医学,人文科学etc.現実世界の様々な関係性を記述する道具としてグラフは現れる.

 昨今の計算機の発達ともあいまって,関係性の情報処理の需要は高まる一方である.その核心技術たるグラフアルゴリズムは,今や学術のみならず現代社会に普遍的に不可欠と言えよう.

2.計算機科学略史

 19世紀末,集合の自己言及に関するパラドックスなどの奇妙な現象が発見され,19世紀後半から20世紀前半にかけて数学の厳密化が進んだ.ヒルベルトは数学の正当性を証明する一大計画を打ち立て,1900年の国際数学者会議では20世紀の数学が取り組むべき課題(いわゆるヒルベルトの23の問題)の一つとして算術の公理化と無矛盾性の証明を挙げている.ヒルベルト計画への挑戦もあって,数学の公理化は20世紀に成熟を見せる.しかし,ヒルベルトの計画自体は1931年のゲーデルの不完全性定理によって頓挫し,軌道修正を余儀なくされた.


続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。


続きを読む(PDF)   バックナンバーを購入する    入会登録


  

電子情報通信学会 - IEICE会誌はモバイルでお読みいただけます。

電子情報通信学会誌 会誌アプリのお知らせ

電子情報通信学会 - IEICE会誌アプリをダウンロード

  Google Play で手に入れよう

本サイトでは会誌記事の一部を試し読み用として提供しています。