グラフ理論

現在のコンピュータが扱うシステムは年々巨大化してきており、その設計や解析にグラフ理論は必要不可欠なものとなってきている。本書はコンピュータサイエンスやさまざまなシステムを学ぶ人々に必須の内容をわかり易く解説している。また、すべての練習問題は内容を理解するのに役立つ問題を取り上げた。 第1章 数学的準備 ・集合 ・集合演算 ・写像 ・関係 第2章 グラフ ・グラフとは ・有向グラフ ・経路と閉路と成分 ・頂点の次数 ・部分グラフと完全グラフと2部グラフ 第3章 木 ・木の定義と性質 ・全域木と同型グラフ ・完全グラフの全域木の総数 第4章 正則グラフ ・無向正則グラフ ・超立方体グラフ ・グラフの直径 ・有向正則グラフ 第5章 オイラーグラフ ・一筆書き ・一筆書きの描き方 ・フラーリーのアルゴリズムの正当化 ・グラフ理論のはじまり ・有向グラフでのオイラー閉路 ・一筆書きの応用 第6章 グラフの平面性 ・平面的グラフ ・クラトフスキーの定理 ・平面グラフに関するオイラーの公式 ・平面グラフの面の次数 ・単純平面的グラフの特徴 第7章 グラフの彩色 ・グラフの彩色数 ・ブルックスの定理の証明 ・平面的グラフの彩色 ・辺彩色 ・ビジングの定理 練習問題の解答