グラフ・ネットワーク・組合せ論

藤重 悟　（著）

(工系数学講座１８巻，共立出版)　(２００２年４月初版)

　目次

第1章　グラフ

1.1　グラフの定義

1.2　グラフの表現

1.2.1　グラフの行列表現　
1.2.2　リスト表現

1.3　特殊なグラフ

1.4　グラフ探索

1.4.1　ＤＦＳ(Depth-First Search)　
1.4.2　ＢＦＳ(Breadth-First Search)

1.5　連結性

1.5.1　連結性　
1.5.2　２連結性　
1.5.3　３連結性　
1.5.4　強連結性

1.6　グラフとマトロイド

1.7　グラフに関するその他の概念

練習問題

第2章　ネットワーク

2.1　木と道

2.1.1　最小木問題　
2.1.2　最短路問題

2.2　フローとカット

2.2.1　２端子フロー　
2.2.2　循環フロー　
2.2.3　フローの同符号分解　
2.2.4　無向ネットワークの最小カット

2.3　最小費用フロー

2.3.1　最小費用フローの特徴づけ　
2.3.2　最小費用フロー問題に対するアルゴリズム　
2.3.3　ＰＥＲＴ・ＣＰＭ

2.4　マッチングと被覆

2.4.1　最大マッチング・最小被覆定理　
2.4.2　Dulmage-Mendelsohn 分解　
2.4.3　枝彩色問題　
2.4.4　安定マッチング　
2.4.5　割当問題

2.5　その他のネットワーク最適化問題

2.5.1　一般グラフのマッチング　
2.5.2　多品種フロー・一般化フロー・動的フロー

練習問題

第3章　組合せ論・トポロジー

3.1　数え上げ

3.1.1　順列と組合せ　
3.1.2　Stirling 数　
3.1.3　母関数　
3.1.4　ふるいの公式と集合関数

3.2　反転公式

3.2.1　２項反転公式・Stirlingの反転公式　
3.2.2　Möbiusの反転公式

3.3　凸多面体と組合せ論

3.3.1　凸多面体　
3.3.2　順列・置換と整凸多面体　
3.3.3　マトロイド多面体

3.4　複体と単体分割

3.4.1　単体と複体　
3.4.2　単体分割　
3.4.3　単体近似

3.5　複体のホモロジー

3.5.1　加群の基本定理　
3.5.2　ホモロジー群　
3.5.3　位相的不変量

練習問題

文献ノート

練習問題略解

索引