グラフ理論の基礎と応用
わたしたちの生活を支える、コンピュータ、通信ネットワーク、ソフトウエア、携帯電話、鉄道・道路網、電力送信システムなど、現代技術の成果物は非常に複雑である。そのため、そこで何らかの問題が生じた場合に、どのようにその問題の本質を見極め、適切な対策を取っていくべきかを考えることは、非常に困難となっている。その解決方法のひとつとして、グラフ理論を応用することは有効な手段となる。グラフ理論では、通信ネットワークや集積回路といった非常に複雑なシステムを、グラフのシンプルな表現方法を用いて表すことで、余分な情報を取り去り、本質のみを表現することを可能とするからである。
本書では、数学的な厳密さ、正しさよりは、情報工学、知能工学、通信・ネットワーク工学などでの利用において特に重要と思われる概念を選び、なるべく読者に直感的に伝えられるように配慮している。情報系工学の学生、技術者、研究者にとって、グラフ理論は、システム、現象、制度などを視覚的に表現し、分析するための道具である。本書ではその点を重視し、グラフ理論の考え方や手段を学び、様々な問題への活かし方を学べるよう解説されている。
本書では、数学的な厳密さ、正しさよりは、情報工学、知能工学、通信・ネットワーク工学などでの利用において特に重要と思われる概念を選び、なるべく読者に直感的に伝えられるように配慮している。情報系工学の学生、技術者、研究者にとって、グラフ理論は、システム、現象、制度などを視覚的に表現し、分析するための道具である。本書ではその点を重視し、グラフ理論の考え方や手段を学び、様々な問題への活かし方を学べるよう解説されている。
第1章 数学的基礎
1.1 集合
1.2 写像または関数
1.3 関係
1.4 フロアとシーリング
1.5 論理と命題
1.6 証明論法
第2章 グラフに関する諸定義と基本的性質
2.1 グラフとは
2.2 グラフの使用例
2.3 部分グラフ
2.4 隣接，接続，同形
2.5 点次数
2.6 ウォーク，トレイル，パス，連結性，サイクル
2.7 非サイクル的グラフ，木
2.8 辺や点の除去，ブロック
2.9 いくつかの特徴をもつグラフ
2.10 グラフと行列表現
第3章 グラフの諸性質と最短路問題
3.1 パス・サイクル・ウォークに関する性質
3.2 2部グラフとサイクル
3.3 単純グラフの最大辺数と最小辺数
3.4 有向非サイクル的グラフと位相的順序
3.5 最短路問題を解くダイクストラ法
第4章 巡回性
4.1 オイラーサーキット
4.2 オイラーグラフの特徴付け
4.3 オイラーサーキットの検出
4.4 有向オイラーサーキット
4.5 中国人郵便配達問題への応用
4.6 ハミルトングラフ
4.7 ハミルトンサイクルをもつための十分条件
4.8 トーナメント
4.9 巡回セールスマン問題
第5章 木
5.1 木の特徴
5.2 全域木
5.3 根付き木
第6章 グラフの平面性
6.1 平面的グラフと非平面的グラフ
6.2 グラフの平面性と回路設計への応用
6.3 平面描画における面とオイラーの公式
6.4 平面性の特徴付け
6.5 幾何学的双対
6.6 外平面的グラフ
第7章 グラフの彩色問題
7.1 点彩色問題
7.2 辺彩色問題
7.3 染色多項式
7.4 彩色アルゴリズム
7.5 彩色問題の応用
第8章 ネットワークフロー
8.1 ネットワークとフロー
8.2 最大フロー最小カットの定理
第9章 グラフの連結性
9.1 連結度と辺連結度
9.2 メンガーの定理
1.1 集合
1.2 写像または関数
1.3 関係
1.4 フロアとシーリング
1.5 論理と命題
1.6 証明論法
第2章 グラフに関する諸定義と基本的性質
2.1 グラフとは
2.2 グラフの使用例
2.3 部分グラフ
2.4 隣接，接続，同形
2.5 点次数
2.6 ウォーク，トレイル，パス，連結性，サイクル
2.7 非サイクル的グラフ，木
2.8 辺や点の除去，ブロック
2.9 いくつかの特徴をもつグラフ
2.10 グラフと行列表現
第3章 グラフの諸性質と最短路問題
3.1 パス・サイクル・ウォークに関する性質
3.2 2部グラフとサイクル
3.3 単純グラフの最大辺数と最小辺数
3.4 有向非サイクル的グラフと位相的順序
3.5 最短路問題を解くダイクストラ法
第4章 巡回性
4.1 オイラーサーキット
4.2 オイラーグラフの特徴付け
4.3 オイラーサーキットの検出
4.4 有向オイラーサーキット
4.5 中国人郵便配達問題への応用
4.6 ハミルトングラフ
4.7 ハミルトンサイクルをもつための十分条件
4.8 トーナメント
4.9 巡回セールスマン問題
第5章 木
5.1 木の特徴
5.2 全域木
5.3 根付き木
第6章 グラフの平面性
6.1 平面的グラフと非平面的グラフ
6.2 グラフの平面性と回路設計への応用
6.3 平面描画における面とオイラーの公式
6.4 平面性の特徴付け
6.5 幾何学的双対
6.6 外平面的グラフ
第7章 グラフの彩色問題
7.1 点彩色問題
7.2 辺彩色問題
7.3 染色多項式
7.4 彩色アルゴリズム
7.5 彩色問題の応用
第8章 ネットワークフロー
8.1 ネットワークとフロー
8.2 最大フロー最小カットの定理
第9章 グラフの連結性
9.1 連結度と辺連結度
9.2 メンガーの定理
