グラフ理論

さまざまな具体例を通して、本講義で扱う「グラフ」とは何であるかを伝える。また、グラフ理論を用いてキューブパズルの問題が解けることを紹介する。

集合や写像の記法や概念について確認した上で、集合を用いたグラフの数学的な定義について、単純グラフの場合に限定して述べる。

今後重要な役割を果たす特別なグラフ（完全グラフ・二部グラフ等）について紹介する。また、ループや多重辺を持つグラフ（一般グラフ）の定義の仕方についても紹介する。

「一筆書き」をテーマに、グラフ理論のきっかけとなった「ケーニヒスベルクの橋の問題」を扱う。小道・道・閉路や次数などの基本的な概念について述べたのち、オイラーによる解法を紹介する。

グラフに関連する代表的な最適化問題である「巡回セールスマン問題」について扱う。巡回セールスマン問題がNP困難であることについて解説するほか、代表的な解法について述べる。

重み付きグラフの2頂点を結ぶ最短経路を求めるアルゴリズムである「ダイクストラ法」について、そのアルゴリズムや計算方法を紹介する。

グラフ理論における「木」の定義や応用例を紹介する。また、木構造に格納されたデータを探索するアルゴリズムについて紹介する。

平面上に描くことができるグラフについての性質、特にオイラーの多面体定理との関係について議論する。

グラフの別表現である「隣接行列」を紹介する。隣接行列の積や固有値がグラフの性質をどのように反映させるのかについて述べる。

「任意の平面地図は高々4色で塗り分けられる」という4色問題に関して、その歴史やグラフ理論に基づいた定式化について述べる。また、応用として基地局配置問題やスケジューリング問題との関係について述べる。

4色問題について理論的に議論する。4色問題の一歩手前である5色定理について、その証明を紹介する。

辺に向きがついたグラフ（有向グラフ）とその上を流れるネットワークフローについて定義する。PERT図や電気回路、インターネット等の具体例を交えて、まずは定義の直感的な理解を目指す。

主定理「最大フロー最小カット定理」や、最大フローを求めるアルゴリズムである「フォード・ファルカーソンのアルゴリズム」を紹介する。後者が実は主定理の証明のキーになっていることについて触れる。

二部グラフの完全マッチングが存在する必要十分条件である「ホールの結婚定理」とその証明を紹介する。後半では実はマッチングがネットワークフローと関係があることについて述べる。

実社会における巨大なグラフの例であるWorld Wide Web (Web) の持つ性質を議論する。また一般に、このような巨大なグラフ（複雑ネットワーク）の持つ性質や、これらを抽象化したモデルについて紹介する。