上 |
第1章 基礎的な準備 1 |
1.1 いくつかの問題 2 |
1.2 数と集合-表記 8 |
1.3 数学的帰納法と他の証明 17 |
1.4 関数 26 |
1.5 関係 33 |
1.6 同値関係 37 |
1.7 順序集合 41 |
第2章 組合せ的数え上げ 49 |
2.1 関数と部分集合 49 |
2.2 置換と階乗 54 |
2.3 二項係数 58 |
2.4 評価-入門編 67 |
2.5 評価-階乗関係 75 |
2.6 評価-二項係数 83 |
2.7 包除原理 88 |
2.8 クローク係嬢の問題 93 |
第3章 グラフ理論入門 99 |
3.1 グラフの概念-同型 99 |
3.2 部分グラフ、連結成分、隣接行列 107 |
3.3 次数列 114 |
3.4 オイラー・グラフ 120 |
3.5 オイラー回路を求めるアルゴリズム 126 |
3.6 オイラー有向グラフ 130 |
3.7 2-連結性 135 |
第4章 木 143 |
4.1 木の定義と特徴づけ 143 |
4.2 木の同型 150 |
4.3 グラフの全域木 156 |
4.4 最小全域木問題 161 |
4.5 ヤルニークとボルーフカのアルゴリズム 167 |
第5章 グラフを平面に描く 173 |
5.1 平面や曲面の上の描画 173 |
5.2 平面的グラフの中の閉路 181 |
5.3 オイラーの公式 187 |
5.4 地図の色分け-四色定理 197 |
演習問題のヒント 209 |
参考文献 223 |
索引 229 |
下 |
第6章 2通りに教える 1 |
6.1 偶奇性の議論 1 |
6.2 シュぺルナー定理と独立集合族 11 |
6.3 極値グラフ理論の結果 18 |
第7章 全域木の総数 23 |
7.1 結果 23 |
7.2 次数列を用いた証明 24 |
7.3 脊椎動物を用いた証明 26 |
7.4 ブリューファー・コードを用いた証明 29 |
7.5 行列式を用いた証明 31 |
第8章 有限射影平面 41 |
8.1 定義と基本的性質 41 |
8.2 有限射影平面の存在 51 |
8.3 直交するラテン方陣 55 |
8.4 組合せ的な応用 59 |
第9章 確率と確率的証明 63 |
9.1 数え上げによる証明 63 |
9.2 有限確率空間 70 |
9.3 確率変数とその期待値 80 |
9.4 いくつかの応用 85 |
第10章 母関数 95 |
10.1 多項式の組合せ的な応用 95 |
10.2 ベキ級数を用いた計算 99 |
10.3 フィボナッチ数列と黄金比 110 |
10.4 二進木 117 |
10.5 サイコロを振る 121 |
10.6 ランダム・ウォーク 122 |
10.7 整数の分割 125 |
第11章 線形代数の応用 133 |
11.1 ブロック・デザイン 133 |
11.2 フィッシャーの不等式 139 |
11.3 完全二部グラフによる被覆 142 |
11.4 グラフのサイクル空間 145 |
11.5 循環流と切断-サイクル空間の再登場 150 |
11.6 確率的チェック 154 |
付録 代数学からの準備 165 |
演習問題のヒント 173 |
参考文献 185 |
索引 191 |