『例題で学ぶグラフ理論』
https://m.media-amazon.com/images/I/41h7K72SHRL._SY425_.jpg
2013-11-26
安藤清 著
土屋守正 著
松井泰子 著
つまずいたら例題を解こう! 工学系・情報系のための入門テキスト~
人や情報のつながりをモデル化し,それらを最適に制御・設計するための理論として,
工学や情報科学に欠かせない数学となった「グラフ理論」.
本書は,初めてグラフ理論に触れる理工系の読者のためのテキストです.
定理等の厳密な証明はおこなわず,実問題でよく応用される各種の「アルゴリズム」に重点をおいて解説.
グラフ理論特有のややこしい概念を具体例に即して納得できるよう,
定理やアルゴリズムには必ず例題をつけることで,他書にはない分かりやすさを実現しました.
【目次】
第1章 グラフの基礎概念
1.1 グラフ理論とは
1.2 基本的な定義
1.3 次数
1.4 隣接行列
1.5 道と閉路
演習問題1
第2章 木と探索アルゴリズム
2.1 木とは
2.2 木と最小全域木
2.3 根付き木とBFS(幅優先探索)アルゴリズム
2.4 向き付けとDFS(深さ優先探索)アルゴリズム
2.5 重み最小の経路
演習問題2
第3章 周遊性
3.1 オイラーグラフとハミルトングラフについて
3.2 オイラーグラフと郵便配達員問題
3.3 ハミルトングラフと巡回セールスマン問題
演習問題3
第4章 ネットワークフローと最大流問題
4.1 ネットワークとは
4.2 ネットワークの基礎概念
4.3 最大流アルゴリズム
演習問題4
第5章 マッチング
5.1 マッチングとは
5.2 最大マッチング
5.3 2部グラフのマッチング
演習問題5
第6章 平面的グラフ
6.1 幾何学的にグラフを捉える
6.2 平面的グラフ
6.3 多面体グラフと厚さ
演習問題6
演習問題解答