出版社内容情報
本書は、グラフ理論を初めて学ぶ読者を対象に、基礎から応用までを体系的に解説した入門的な教科書である。グラフ理論は18世紀に始まった学問でありながら、コンピュータの発展に伴いここ数十年で急速に応用範囲が広がってきた。本書はその背景を踏まえ、現代の情報科学やシステム解析に不可欠な基礎知識を、数式や抽象概念に偏らず、わかりやすい言葉と具体的な例を用いて解説している。
第1章では集合や写像といった予備知識を短くまとめ、第2章以降でグラフ理論を本格的に導入する。木、オイラー路、ハミルトン路、平面グラフ、彩色問題など、授業で扱う標準的テーマを段階的に解説し、第9章では最短経路、マッチング、数え上げといった応用的話題にもふれる。無向グラフに加えて有向グラフも扱い、近年の応用に対応できるバランスのとれた内容となっている点も特長である。
各章末には、計算問題と証明問題からなる練習問題を掲載した。計算問題は一定の思考を要するものを中心とし、単なる作業に終わらないよう工夫している。証明問題は論理的思考力の育成を意識し、基本的で重要な課題を厳選した。巻末には解答を掲載し、自習にも利用できるよう配慮している。高等数学の知識を前提としないため、専門外の学生や数学に不安をもつ学習者でも無理なく取り組める。
本書を通じて、読者はグラフ理論の基本的な枠組みと考え方を身につけ、情報科学や工学の幅広い分野に応用できる基礎力を養うことができる。授業の主教材としても活用できる実践的なテキストである。
【目次】
第1章 数学的準備
1.1 集合
1.2 集合演算
1.3 写像
1.4 関係
第2章 グラフ
2.1 グラフとは
2.2 有向グラフ
2.3 経路と閉路と成分
2.4 頂点の次数
2.5 部分グラフと完全グラフと2部グラフ
2.6 隣接行列
第3章 木
3.1 木の定義と性質
3.2 全域木と同型グラフ
3.3 完全グラフの全域木の総数
3.4 最小全域木
第4章 正則グラフ
4.1 無向正則グラフ
4.2 超立方体グラフ
4.3 グラフの直径
4.4 有向正則グラフ
第5章 オイラーグラフ
5.1 一筆書き
5.2 一筆書きの描き方
5.3 フラーリーのアルゴリズムの正当性
5.4 グラフ理論のはじまり
5.5 有向グラフでのオイラー閉路
5.6 一筆書きの応用
第6章 ハミルトングラフ
6.1 ハミルトン経路
6.2 オーレの定理
6.3 巡回セールスマン問題
第7章 グラフの平面性
7.1 平面的グラフ
7.2 クラトフスキーの定理
7.3 ワーグナーの定理
7.4 平面グラフに関するオイラーの公式
7.5 平面グラフの面の次数
7.6 単純平面的グラフの特徴
第8章 グラフの彩色
8.1 グラフの彩色数
8.2 ブルックスの定理の証明
8.3 ウェルシュ・パウウェルアルゴリズム
8.4 平面的グラフの彩色
8.5 辺彩色
8.6 ビジングの定理
第9章 グラフ理論の様々な応用
9.1 最短経路問題
9.2 グラフの数え上げ
9.3 マッチング問題
練習問題の略解
参考文献
索引
目次
第１章 数学的準備
第２章 グラフ
第３章 木
第４章 正則グラフ
第５章 オイラーグラフ
第６章 ハミルトングラフ
第７章 グラフの平面性
第８章 グラフの彩色
第９章 グラフ理論のさまざまな応用
著者等紹介
平博順［タイラヒロトシ］
１９９４年東京大学理学部卒業。専門：機械学習、自然言語処理。現在、大阪工業大学情報科学部教授、博士（工学）
地嵜頌子［チサキショウコ］
２０１６年東京理科大学大学院理工学研究科情報科学専攻博士課程修了。専門：離散数学。現在、大阪工業大学情報科学部講師、博士（理学）
一森哲男［イチモリテツオ］
１９８２年大阪大学大学院工学研究科博士後期課程修了。専門：数理計画法、アルゴリズム論。現在、大阪工業大学名誉教授、工学博士（本データはこの書籍が刊行された当時に掲載されていたものです）
※書籍に掲載されている著者及び編者、訳者、監修者、イラストレーターなどの紹介情報です。
