理工学部Faculty of Science and Engineering

インターネット、電子回路網、通信網、輸送網などの位相幾何学的構造（グラフ構造）を有する情報システムの効率的な設計・運用・解析には、ネットワーク理論とアルゴリズムの基礎と効率的なデータ構造に基づくグラフ・ネットワークアルゴリズムが極めて有用である。ここでは、アルゴリズムの基礎と効率的なデータ構造に基づいて、代表的なグラフ・ネットワークアルゴリズムおよびその基礎となる理論を講義する。

効率的なネットワークの設計・運用・解析に必要なネットワーク理論とグラフ・ネットワークアルゴリズムがテーマである。目標は、ネットワーク上での様々な問題の定式化、定式化した問題に対する解法、それらの解法を効率的に実行するアルゴリズム、それらのアルゴリズムを実際にプログラミングするためのデータ構造を理解して利用できるようになることである。

ディプロマポリシーのうち、「DP1」と「DP2」と「DP4」に関連

日本語 / Japanese

講義形式で授業は進行するが、必要に応じて演習・課題を行う。課題に対しては、適宜講評する。演習・課題は学期末試験の対策になる。さらに、講義で説明したアルゴリズムのコードをPC上で実行することを通して、アルゴリズムの理解を深める。

なし / No

なし / No

※各回の授業形態は予定です。教員の指示に従ってください。

第1回：グラフの基礎概念

グラフに関する基本的な用語と概念を解説する。

第2回：グラフ・ネットワーク表現のデータ構造

ネットワークの基礎構造であるグラフをコンピューター内で効率的に処理するためのデータ構造を、そのために必要とする記憶領域を含めて解説する。

第3回：グラフとネットワークの探索アルゴリズム（１）

グラフとネットワークの様々な問題を効率的に処理するための下準備となる、探索アルゴリズムについて解説する。具体的には、第2回の講義で用いたデータ構造を用いて、有向グラフに対する深さ優先探索と幅優先探索を解説する。

第4回：グラフとネットワークの探索アルゴリズム（２）

無向グラフに対する深さ優先探索と幅優先探索を解説する。さらに、グラフの様々な性質を調べるための、深さ優先探索と幅優先探索の応用例を解説する。

第5回：トポロジカルソートと最短パスと最長パス

グラフやネットワーク問題の代表的な問題である最短パス問題と最長パス問題を取り上げる。そこで、有向閉路のないグラフに対して、ネットワークの頂点に、どの辺においても、始点のラベルが終点のラベルより小さくなるように頂点にラベルをつける（トポロジカルソートと呼ばれる）。このトポロジカルソートは、ネットワーク探索アルゴリズムで効率的にできる。そしてそのラベルの小さい順に計算して、ネットワークの最短パスと最長パスを効率的に求めるアルゴリズムを解説する。

第6回：オイラーグラフと一筆書き

グラフやネットワーク問題の代表的な問題であるオイラーグラフ（一筆書き可能グラフ）の特徴付けを与え、その特徴付けと第2-4回の講義で説明したデータ構造と探索アルゴリズムを用いて、効率的な一筆書きアルゴリズムを解説する。

第7回：最短パスとダイクストラ法

カーナビや乗り換え経路案内等のシステムで用いられているネットワークの最短パス問題を取り上げる。第5回の講義では、有向閉路のないグラフに対しての最短パスを取り上げたが、ここで取り上げている最短パス問題では、より一般的な有向閉路が存在することもあるネットワークを対象としている。そして、負の長さの辺のないネットワークに対する代表的な最短パスアルゴリズムのダイクストラ法を解説する。さらに、そのアルゴリズムを高速化するデータ構造についても解説する。

第8回：全点間の最短パスと動的計画法

ネットワークのすべての２点間の最短パスを効率的に求める全点間の最短パス問題を取り上げる。そして、効率的なアルゴリズムの代表的な設計手法である動的計画法に基づいて、全点間の最短パス問題を効率的に求めるアルゴリズムを解説する。

第9回：最小全点木とグリーディ法

通信ネットワークや送電線ネットワークでの代表的な問題である最小全点木問題に対して、その特徴付けを与え、それと効率的アルゴリズムの代表的設計手法のグリーディ法に基づいて、ネットワークの最小全点木を効率的に求めるアルゴリズムを解説する。さらに、そのアルゴリズムを高速化するデータ構造についても解説する。

第10回：最大フローと最小カットとフォード-ファルカーソンのアルゴリズム

道路交通網やインターネットや水道網で問題になる流れ（フロー）の問題を取り上げる。ネットワークの回線（辺、パイプ）に容量（単位時間当たりに流せる最大流量）が付随するとき、ネットワーク内で要求されるフローをできるだけ多くする問題（最大フロー問題）とその限界（最小カット問題）を解説する。そして、それらを効率的に解決するフォード-ファルカーソンのアルゴリズムを解説する。

第11回：ディニッツの最大フローアルゴリズム

第10回の講義で取り上げた最大フローと最小カットに対するフォード-ファルカーソンのアルゴリズムをより高速化する、ディニッツの最大フローアルゴリズムを解説する。これは、第3回の講義で与えた深さ優先探索と幅優先探索を用いて実装できることも解説する。

第12回：最大フローアルゴリズムの応用

ネットワークの様々な問題が最大フローと最小カットを用いて定式化できることを解説する。これに基づいて、最大フローと最小カットを求めるアルゴリズムは、ネットワークで起こる多くの問題に広く応用できることを、具体的な例を取り上げて解説する。

第13回：最小費用フローアルゴリズムとダイクストラ法の適用

ネットワークの各回線に容量のみならず、使用コストが付随するときのフローの問題である、最小費用フロー問題を取り上げる。これは、最短パス問題や最大フロー問題を一般化した問題で、その意味では、多岐にわたる応用を有するものである。ここでは、最短パスを求めるダイクストラ法に基づいて、最小費用フロー問題を解くアルゴリズムを解説する。

第14回：試験・まとめと解説

理解度の確認をする。

【本授業の準備・復習等の授業時間外学習は、4時間を標準とする】講義で解説するアルゴリズムとその基礎となる理論は、プログラミングを通して初めて細部まで理解することができる。積極的にプログラミングし、ネットワークアルゴリズムとその基礎理論を修得してほしい。

浅野孝夫：「グラフ・ネットワークアルゴリズムの基礎：数理とCプログラム」（近代科学社）、2017。

浅野孝夫：「アルゴリズムの基礎とデータ構造：数理とCプログラム」（近代科学社）。
J.Kleinberg and E. Tardos 著（浅野孝夫、浅野泰仁、他、訳）：「アルゴリズムデザイン」（共立出版）。
浅野孝夫、今井浩:「計算とアルゴリズム」（オーム社）。
浅野孝夫：「情報の構造（上）データ構造とグラフアルゴリズム (情報数学セミナー) 」（日本評論社）。
浅野孝夫：「情報の構造（下）ネットワークアルゴリズムとデータ構造 (情報数学セミナー) 」（日本評論社）。
浅野孝夫：「離散数学：グラフ・束・デザイン・離散確率」（サイエンス社）。

学期末試験の成績(100%)によって評価する。

ソースコードの説明を増やす。

必要に応じて、貸与ノートパソコンを利用する。